# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**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 + x3l (4.19)

with

0x,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 Geoffrions 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.

**36**> 37 38 39 40 41 42 .. 156 >> Next