# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**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 {kb} (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.

**27**> 28 29 30 31 32 33 .. 156 >> Next