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 -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.
Previous << 1 .. 29 30 31 32 33 34 < 35 > 36 37 38 39 40 41 .. 156 >> Next