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 .. 21 22 23 24 25 26 < 27 > 28 29 30 31 32 33 .. 156 >> Next Exercise 5 Clearly, one cannot have x1 = x2=x4 = 0 in (2.159). Hence Xj + x2 + x4^ 1, and Exercise 2 applies.
Exercise 6 By logic, either t^l or x32l or x3=51, i.e. either
68 Robert Jeroslow
or
/c\ 111114
or
(Sa) h~lt2+h+6u+6t5^l
giving b(n = 5/6, b(2) = 4/6, b<3) = 3/6, and f = 3.
Since always Xj, x2, x3s=0 we similarly obtain in Principle sdc that d<l) = -1/6, d<2) = Ś2/6, d<3) = -3/6. Therefore f>(h)-d<h) = l for h = 1,2,3. From (2.134), a valid cut is
X f max {A(h)(a0h) + nh)}W min A(h)f>(h) (2.173)
j-l \h =1.2,3 / H = 1,2,3
whenever the nh are integer (possibly negative) with n1 + n2 + ti3s=0, and the A(h)3=0 are nonnegative scalars. Take, for instance, A(1) = 6/5, A<2> = 6/4, A(3) = 6/3, so that all A(h)f>(M = 1. Then with n1=n2 = n3 = 0 we obtain the usual disjunctive cut
- ti+-t2 + -t3 + -t4 + -ts3'1 (2.174)
which is (2.162).
Let us now pick (hj, n2, rt3) to improve the coefficient 2/3 of in (2.174),
if possible. Using (n1; n2, n3) = (1, 0, Ś1) will improve the coefficient, and
that coefficient becomes
max
as noted in (2.163).
To improve the coefficient of t4, which is 1/3 in (2.162), note that (nl, n2, n3) = (1, 0, -1) gives a coefficient of
max
as noted in (2.163).
For an algorithm that finds the best (nt, n2, n3) in problems of this type, see Balas and Jeroslow (1975) from which the above example is drawn.
Exercise 7 View the constraints (grp) as
+ (2.175)
Vfljl-' '^23-'
The Theory of Cutting-Planes 69
with
z, and z2 integer } (2.176)
and au = 3.7, a12 = 9.3, etc. Now
\a21/ \?22' \?23/1
is an integer point (z,, z2)n, hence one of the following four possibilit?s must hold:
z, ^ 0 and z2^0 (2.177a)
z,3= 0 and z2½-l (2.177b)
z,=s-l and z23=0 (2.177c)
z,=?-l and z2½-l. (2.177d)
Hence one of the following four systems holds:
aut3 +a12t2 +a13t3^0.5 and a2, t, + a22t2-I-a23t3ss 0.9
(2.178a)
a^t^a^ + a^t^O.5 and (Śa^)^+ (Śa22)f2 + (Śu23)*3=^0-l
(2.178b)
(Śa j i)fj + (Śfl,2)f2 + (Śa. j 3) t3 ^ 0.5 and a23t1 + a.22t2-^ a23t3^ 0.9
(2.178c)
(-an)b + (-½12)^2 + (~al3)t3^0.5 and (-a21)f, + (~a22)t2 + (-a23)t3 s= 0.1.
(2.178d)
By Principle dc, (2.122) is always valid where
Fj((½ä v2),T) = max {(½,/0.5) + (vJO.9), (½,/0.5) - (u2/0.1),
- (?t/0.5) + (u2/0.9), -(½,/0.5) - (½2/0.1)} (2.179a)
and
77ä = 1. (2.179b)
We then apply Principle mcs to obtain that the jth cut coefficient in (2.123) can be taken to be
OK:))
^IL )) + l )) (2.180)
i2j /
for any choice of integers z, and z2, and we therefore pick z, in an advantageous manner. We chose z, to be either the negative of the integer part LsJ ░( aa OT io be Ś (LajjJ+l), depending on which choice makes (2.180) smallest among these four possibilit?s.
70
Robert Jeroslow
For each one of the four possibilities, it is easy to identify which one of the four terms in the maximum of (2.179a) gives the value of this maximum. In detail:
= ua/0.5 + u2/0.9 (2.181a)
= (l-t?!)/0.5 + t?2/0.9 (2.181b)
= u1/0.5+(l-u2)/0.1 (2.181c)
= (1 ~ t?a)/0.5 + (1 Ś y2)/0.1 (2.181d)
CHLT1))
'Vw vlu2j + i +1
'\W \Lu2J + i
where x abbreviates the fractional part of the number x, i.e. x = x Ś[xj. Therefore, the /th intercept can be taken to be the best of these, i.e. to be
min {th/0.5 + u2/0.9, (1 Ś UjVO.5 + u2/0.9,
vJO.5 + (1 -1?2)/0.1, (1 - uJ/0.5 + (1 - y2)/0.1} (2.182)
since that would provide a weakening of (2.123). For example, the coefficient of fi will be (rounding up for validity):
min {0.7/0.5 + 0.2/0.9, 0.3/0.5 +0.2/0.9,
0.7/0.5 -I-0.8/0.1, 0.3/0.5 + 0.8/0.1} = 0.83 (2.183)
In the same manner, the other cut coefficients in (2.164) can be calculated.
Exercise 8 We modify and continue the subadditive derivation of Principle dc in equations (2.140)-(2.143). Again we consider Principle bmip in Appendix 2.3, using equation (2.97) there, where we see that the matrices A and C of (2.97) are empty, i.e. there are only the (nonnegative) integer variables x = (xl7..., xs) and we rename s to r.
We set
B =
,(i)
, <?>
(2.140')
in (2.97), with t = |H|, and put S as in (2.141). Again we use the function G of (2.142), which we saw was subadditive. Next we define a new function Q by
Q((u(1),..., u'0)07) = inf G((u(1),..., v(,y)a+ m) (2.184)
m ł M
The Theory of Cutting-Planes
71
where M is as defined in (2.135b) of the proof of Principle sdc. By Exercise Id of Appendix (2.1) (with G of Id being =0, H of Id set to G of (2.142), K =real space, P = ŚM), we see that Q of (2.184) is subadditive.
Note that Q(b<k)), where blk) is the fcth column of B in (2.140'), does indeed provide the fcth coefficient of the cut in (2.134). It remains only to verify the constant term of (2.134), and then appeal to the cut-form (2.198) from Appendix 2.3.
We have
inf {Q((u(1),..., vM) | (va\ .... vM) e S}
= inf {G((ea),..., o'T + m) | (e(1\ . .., vM) e S}
= inf {G((½a),. .., i/T) | (u(1\ ., v(0) e S}
= inf {kÖbÖ} (2.143')
heH
as desired. The crucial third equality in (2.143') is due to the fact that (u(I),..., t>(0)eS and meM implies (ua),. .., u<0) + meS, by exactly the reasoning as in the proof of Principle sdc. Previous << 1 .. 21 22 23 24 25 26 < 27 > 28 29 30 31 32 33 .. 156 >> Next 