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 .. 29 30 31 32 33 34 < 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 -3x6¨0
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 + 3x6¨12 2x1 + 6x2 + 5x3 + 2x4 + 5x5 +4x6=s 11 7x3 + x2 + 4x4 + 3x6*?ll
2x2 +2x5 + x6¨4
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 + 4x5¨12 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, butif combined with other procedurescan 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. Previous << 1 .. 29 30 31 32 33 34 < 35 > 36 37 38 39 40 41 .. 156 >> Next 