Books in black and white
 Main menu Share a book About us Home
 Books Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

# Combinatorial Optimization - Cristofides N.

Cristofides N. Combinatorial Optimization - Wiley publishing , 2012. - 212 p.
Download (direct link): čüombinatorialoptimi2012.pdf Previous << 1 .. 30 31 32 33 34 35 < 36 > 37 38 39 40 41 42 .. 156 >> Next Another possibility is to add to the optimal simplex tableau of P' those order relations xf^sx« from R* which are violated by its optimal solution (i.e. for which ?ō>??), as æcutsÆ and to solve the corresponding postoptimization problem. This idea seems to us very promising.
A third possibility is to construct the surrogate constraint of Balas (1969), Geoffrion (1969), or Glover (1968) in order to derive from it new elements of R* and T.
Finally, if none of the above approaches brings us to one of the situations
102
Peter L. Hammer and. Sang Nguyen
A, B, or C, we have to branch, i.e. to select a variable xJo, and examine separately the two subproblems resulting for Xyo = 1 and xJo = 0.
It is to be mentioned that if (xf,. . ., x*) is a solution of P, with X,"=i a0jxf = w*, the inequality
to be satisfied by all those solutions of P which are better than (xf,..., x*)
All the above can be summarized in the following algorithm:
Step I Produce R and I?*; if R* is of type 1, stop; if it is of type 2 or 3, introduce the results in R*, until arriving at a new R* of type 1 or 4. If during this process there was an R* of type 2 or 3, introduce the results in the original system and return to I. Otherwise go to:
Step II Produce T and enlarge R*; if the new R* is strictly larger than the original one, return to I; otherwise go to:
Step III Solve P'. Choose an e (0<e<l), put
the optimum has been found. If (xi,..., x'j is a solution of P but (4.13) does not hold, introduce the new constraint
and enlarge R* and T by the new relations resulting from (4.14); if this is possible return to I. Otherwise go to:
Step IV Add to P' those inequalities (cuts) of R* which are not fulfilled by (?x,..., ?ä) and return to III. If none, go to:
Step V Add to P' a surrogate constraint, and enlarge R* and T by the resulting binary and ternary relations. If this is possible, return to I, otherwise go to:
Step VI Choose a variable x, and examine separately the subproblems where xy = 1 and x, = 0. In the branching process, add the constraint (4.12) if w* is the best known value of the objective function.
n
X (Śa0j)x*=? w* Ś 1
(4.12)
(if any) produces usually many useful new elements of R* and T.
If (xj,. .., x'n) is a solution of P and
X a0ix' = z
(4.13)
i = i
n
X a o,Xy=?z
(4-14)
A Partial Order in the Solution Space of Bivalent Programs 103
Example Maximize:
2x1 + 3x2+3x3 + 5x4 + 5x5 + 6x6 (4.15)
subject to the constraints of the second Example (Section 4.1.5).
Steps I and II were examined in (4.1.5), and gave x1 = 1, x6 = 0, reducing
the system of constraints to
8x2 + 6x3- x4-4x5=?12 (4.16)
-6x2-5x3 + 2x4 + 5x5ss 11 (4.17)
x2, x3, x4e{0, 1} (4.18)
and producing
R* = {(2,1; 3,0); (3,1; 2, 0)}
T = {(2,1; 4, 0; 5, 0); (2, 0; 3, 0;4,1); (2, 0; 3, 0; 5,1);
(2,0; 4, 1; 5,1); (3,0; 4, 1; 5,1)}.
Step III gives now
6 = 1 6=1 6=1 6 = 1-
Choosing e we get X' = (l, 1,1,1) which does not solve the constraints of
P. The corresponding constraint 3x2-t-3x3 + 5x4 + 5x5=sl5 does not enlarge
either R* or T.
Step IV requires the solution of the linear programming problem: maximize (4.15) subject to (4.16), (4.17), and to x2=Sx3, or
x2 + x3½l (4.19)
with
0½x,½l (/ = 2,3,4,5). (4.20)
The optimum of this problem is (1, 0,1, 4/5), the value of the objective function being 12. The corresponding æroundedÆ integer point (1, 0, 1,1) does not satisfy our constraints. The new constraint
3x2 + 3x3 + 5x4 + 5x5=?l2
adds to T the elements (2,1; 4,1; 5,1) and (3,1; 4,1; 5, 1). But (2, 0; 4,1; 5,1) and (2,1; 4, 1; 5,1) produce a new element (4, 1; 5, 0) of R*.
We return to Step TV adding the constraint given by (4, 1; 5, 0):
x4 + x5=sl. (4.21)
Solving (by post-optimization techniques) the resulting linear program (maximize (4.15) subject to (4.16), (4.17), (4.19), (4.20), (4.21)) we find that its optimum
x2 = 0 x3=l x4 = 0 x5 = 1
104
Peter L. Hammer and Sang Nguyen
is integer, and hence the problem is solved. Thus, the optimal solution of P
is (1,0, 1,0, 1,0).
4.3 Computational Experience
A variant of the above described algorithm was programmed in Fortran and test problems were run on a CDC-6600; the version of our algorithm which was coded differs from the one described in the paper in two points.
(PI) Ternary relations were not taken into account;
(P2) The binary relations were only used in order to fix certain variables, or as cuts; however conclusions of the form x, = x, or x, = x, which can be derived from them were not taken into account.
The authors believe that by implementing these two additions (especially the second one), the algorithm could be much improved.
Under its present form the program requires approximately 2(m + 5)2 + 2mn + 12(m + n) +10 000 words. The number of binary relations taken into account was limited to 500, and that of æbinary cutsÆ to 5.
For certain test problems of Petersen (1967) and of Bouvier and Messou-mian (1965), the performance was compared to that of GeoffrionÆs algorithm; the results are given in Table 4.1. A sequence of test problems was generated randomly. All of them involve 15 constraints and the coefficients matrix has a density of 0.25, the coefficients being uniformly distributed between Ś100 and +100. The durations and the numbers of iterations reported in Table 4.2 are the averages for five test problems of the given dimensions. Previous << 1 .. 30 31 32 33 34 35 < 36 > 37 38 39 40 41 42 .. 156 >> Next 