# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

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

A ternary relation can be detected in an inequality

1 = 1

if there are three distinct indices, j, k, I in {1,..., n}, such that

kjl+kJ+kil>b?

but

kil + kkkb* kyl + kikb? kiJ+kikb?-

In this case every XeS must satisfy

x^'xp-xr1 = o. (4.5)

If ] <k<l, we shall denote such a felation by

O', aiy; fc, aifc; I, au) (4.6)

and the set of all ternary relations obtained in this way will be denoted by T. The following remarks are immediate:

Rl. If x, = (i.e. 0, au; 0, l)e R*) then (4.6) can be omitted.

R2. If x, = <* (i.e. (j, atj0, l)e R*) then (4.6) reduces to the order relation (fc, aik; I, da).

R3. If 0, ; fc, dtik)e R* then (4.6) can be omitted.

R4. If (j, OLiifc, aik)e R* holds, then (4.6) reduces to the order relation

(j, , 1, n;,j ).

R5. If (j, a; fc, aik; I, aa) and (j, ; fc, a,k; I, dit) hold, then both can be

replaced by the order relation (j, ; fc, aifc). Similar rules apply if the

role of j is played by k or by I, etc.

Hence the knowledge of R and of T leads to the construction of R' (with RcR'cR) and of T'(^T); the repeated application of this idea may be very efficient in constructing a large subset of R.

4.1.5 Second Example

Consider the system

6XJ + 8X2 + 6X3 x4 4x5 + 3x6^1

2xj 6x2 5 x3 + 2x4 + 5 x5 + 4x6 =s 2 -7xt x2 +4x4 -3x60

2x2 +2x5 + x6==4

A Partial Order in the Solution Space of Bivalent Programs

with

X,{0, 1} (/ = 1,

Rewriting the system as

6x1 + 8x2 + 6x3 + x4 + 4x5 + 3x612 2x1 + 6x2 + 5x3 + 2x4 + 5x5 +4x6=s 11 7x3 + x2 + 4x4 + 3x6*?ll

2x2 +2x5 + x64

we get for R* the following set of order relations

x^x2 x2=Sx1 x2*?x3 x3*?x2.

R*( = tc(R*)) is of type 4, and no conclusion can be drawn. Let us construct T:

obtained from the first constraint

obtained from the second constraint

obtained from the third constraint

obtained from the fourth constraint

(2,1 4,0 5,0)

(2,1 5,0 6,1)

(1,0 3,1 4,0)

(1,0 3, 1 5,0)

(1,0 3,1 6,1)

(1,0 5,0 6,1)

.(3,1 5,0 6,1)

'(1,0 2,0 3,0)

(1,0 2,0 5,1)

(1,0 2,0 6,1)

(1,0 3,0 5,1)

(2,0 3,0 4, 1)

(2,0 3,0 5,1)

< (2,0 3,0 6, 1)

(2,0 4,1 5,1)

(2,0 4,1 6, 1)

(2,0 5,1 6, 1)

(3,0 4,1 5, 1)

.(3,0 5,1 6, 1)

f(l,0 ; 2,0 ,4, 1)

1(1, 0 ,4,1 6, 0)

(2,1; 5,1; 6,1).

100 Peter L. Hammer and Sang Nguyen

Now

(1,0,2,0) and (1,0; 2,0; 3,0) give (1,0; 3,1) (by R4)

(1,0; 2,0) and (1, 0; 2, 0; 5, 1) give (1, 0; 5, 0) (by R4)

(1,0; 2,0) and (1, 0; 2, 0; 6,1) give (1,0; 6,0) (by R4)

(1,0; 2,0) and (1, 0; 2, 0; 4,1) give (1,0; 4,0) (by R4)

(1,0; 3,1) and (1,0; 3,1; 4,0) give (1,0; 4,1) (by R4)

but

(1,0; 4,0) and (1,0; 4,1) give (1,0; 0,1)

or

xt = l.

Hence R* becomes now

(2,1; 3,0) (3,1; 2,0)

and T becomes

(2,1; 4,0; 5,0) (2,1; 5,0; 6, 1) (3,1; 5,0; 6,1)

(2, 0; 3, 0; 4, 1) (2, 0; 3, 0; 5, 1) (2,0; 3,0; 6,1)

o of 5,1) (2,0; 4,1; 6,1) (2,0; 5,1; 6,1)

(3,0; 4,1; 5,1) (3,0; 5,1; 6, 1) (2,1; 5,1; 6,1).

(2,1; 5,0 6,1) and (2,1; 5,1; 6, 1) give (2,1; 6, 0) (by R5)

(2,0; 5,1 6,1) and (2,1; 5,1; 6, 1) give (5,1; 6,0) (by R5)

(2,1 6, 0) and (2,0; 3,0; 6,1) give (3, 0; 6, 0) (by R4)

(2,1 6,0) and (2,0; 4,1; 6,1) give (4,1; 6, 0) (by R4)

(2,1 6, 0) and (2, 0; 5,1; 6,1) give (5,1; 6,0) (by R4)

(5,1 6,0) and (3,1; 5,0; 6, 1) give (3,1; 6,0) (by R4).

But now (3,0; 6,0) and (3,1; 6,0) give respectively (6,1; 3,1) and (6,1; 3, 0), implying (6,1; 0,1), or simply

x6 = 0.

The introduction of x6 = 0 into R leaves it unchanged, while T reduces to (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).

No further conclusions can be drawn from here, and the system reduces to

8x2 + 6x3+ x4 + 4x512 6x2 + 5x3 + 2x4 + 5x5 11 x2, x3, x4e{0,1} Xj = l x6 = 0

A Partial Order in the Solution Space of Bivalent Programs

101

(the other two constraints are redundant).

4.2 Solving Bivalent Programs

The ideas of Section 4.1 can be used for the solution of 0-1 programs. They are not sufficient in themselves to solve such problems, butif combined with other procedurescan lead with remarkable efficiency to the solution. Given a linear bivalent program:

n

maximize ? a0,x( (4.7)

p = i

subject to

t, = (4.8)

J = 1

x,e{0,1} (/ = 1,. .., n) (4.9)

(where, without any loss of generality, we may assume that all aO| 3*0, and with almost no loss of generality that all a0, are integers), the order relations discussed in Section 4.1 can lead to: (A) recognition of infeasibility, (B) determination of values for certain variables, (C) reduction of the size of the problem due to condensations x = x?, etc. The list is unfortunately to be completed by: (D) no obvious conclusion.

In this last situation it seems advisable to solve the linear program P': max (4.7) subject to (4.8) and to

0=?Xj *? 1 0 = 1,..., n). (4.10)

Let an optimal solution to this problem be (?,,..., ?) and let the optimal value of (4.7) be ?. If the integer part [?] of ? is denoted by z, then we may add the constraint

n

I a0|x,z (4.11)

i = i

to (4.8). The resulting order relations and ternary relations can be added to R* and to T respectively, having as possible effect the reduction to one of the situations A, B, or C.

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