Ugrás a tartalomhoz

 

Conflict graphs in implicit enumeration

  • Metaadatok
Tartalom: http://real.mtak.hu/66733/
Archívum: MTA Könyvtár
Gyűjtemény: Status = Published

Type = Article
Cím:
Conflict graphs in implicit enumeration
Létrehozó:
SzabĂł, SĂĄndor
Kiadó:
AkadĂŠmiai KiadĂł
Dátum:
2012
info:eu-repo/date/embargoEnd/2032-01-31
Téma:
TA Engineering (General). Civil engineering (General) / ĂĄltalĂĄnos mĂŠrnĂśki tudomĂĄnyok
Tartalmi leírás:
A zero-one linear program is a global discrete optimization problem. Namely, it is a linear programming problem with zero-one variables. The real relaxation of a zero-one program is again a continuous linear programming problem. Simply, the zero-one variables are replaced by continuous variables varying between zero and one independently of each other. If the real relaxation, as a continuous problem, solved with the simplex method happens to have a zero-one optimal solution, then this particular solution is also an optimal solution of the original zero-one programming problem. Suppose that x<sub>1</sub>,…,x<sub>n</sub> are all the variables of a given zero-one linear programming problem. For convenience we introduce further variables y<sub>1</sub>,…,y<sub>n</sub> defined by y<sub>1</sub>=1−x<sub>1</sub>,…, y<sub>n</sub>=1−x<sub>n</sub> respectively. For a unified notation the variables x<sub>1</sub>,…,x<sub>n</sub> and y<sub>1</sub>,…, y<sub>n</sub> together will be denoted by z<sub>1</sub>,…,z<sub>2n</sub>. These variables will play the roles the nodes of the conflict graph Г associated with the given zero-one linear programming problem. Fixing the variables z<sub>i</sub> and z<sub>j</sub> both to be equal to one simultaneously reduces the number of variables in the problem. If the new smaller optimization problem does not have any feasible solution, then the nodes z<sub>i</sub> and z<sub>j</sub> will be connected by an edge in the graph Γ. The graph Γ simply records that there is a conflict between the assignments z<sub>i</sub> =1 and z<sub>j</sub> =1 which explains the name conflict graph. In other words the non-directed edge between the nodes z<sub>i</sub> and z<sub>j</sub> codes the fact that the inequality z<sub>i</sub>+z<sub>j</sub>≤1holds. The conflict graph was designed to generate additional constraints the so-called valid inequalities or cuts in order to expedite the solution of the zero-one linear program via its real relaxation. This particular solution strategy is aptly named the branch and cut method. It will be shown that the conflict graph besides its intended use can also be applied in another solution technique the method of implicit enumeration. We will illustrate by examples that the conflict graph provides us with rules to prune the search tree that are not offered by the commonly applied pruning rules. In addition the computations involved can easily be organized into a highly parallel computational scheme.
Nyelv:
magyar
Típus:
Article
PeerReviewed
info:eu-repo/semantics/article
Formátum:
text
Azonosító:
SzabĂł, SĂĄndor (2012) Conflict graphs in implicit enumeration. Pollack Periodica, 7 (Supple). pp. 145-156. ISSN 1788-1994
Kapcsolat:
https://doi.org/10.1556/Pollack.7.2012.S.14
Létrehozó:
info:eu-repo/semantics/embargoedAccess