# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

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

Exercise 2 Suppose that a set-covering constraint is imposed in zero-one variables xk, i.e.

Xj + .-. + XpSsl (2.154)

where the relevant tableau rows (possibly filled out with unit rows) are given by

Xk = ak0+ ? aki(-tj). (2.155)

JE-f

Derive a disjunctive cut that makes the current solution infeasible if all

^kO^ 1-

Exercise 3 (The strengthened principle of intersection/convexity cuts, as applied to polyhedra: from Balas, 1974a; Glover 1975) Suppose that,

relative to some concept of feasibility, there is no feasible solution which

satisfies all the inequalities

r

X aijXySSOio i = l,...,p (2.156)

1 = 1

in which every aio>0. The variables x = (x,,. .., xr) are nonnegative. Show that the inequality

r

X max {Oij/Oiojx, 2* 1 (2.157)

1=1 *

is valid.

The Theory of Cutting-Planes 65

Exercise 4 (Principle of intersection/convexity cuts for polyhedra: Balas, 1971; Glover, 1973; Young, 1971) With hypotheses as in Exercise 3, let A., 3= 0 denote the intersection of the positive x,-axis with the set of solutions to (2.156), with A, =oo if there is no intersection.

Show that the inequality

ix^Uk^l (2.158)

ii

is valid, interpreting l/c = 0.

Exercise 5 (Balas, 1974a) Suppose that the constraint

3xj+4x2 +8X3+4X4 + IIX5 = 15 (2.159)

holds, in zero-one variables xk, and that the tableau rows read as in (2.155). Using the fact that a10 = 0.7, a20 = 0.3, and a40 = 0.8, derive a disjunctive cut which makes the current solution infeasible.

Exercise 6 (Balas and Jeroslow, 1975) Suppose that the constraints

1 7, ^ 2, . 3. ,5. . 11, ,

*i 6 "*"6 6 6 6 g

*2 = 7 + 7 (_b)+7(_?2) + 7(_t3)_7(_t4)+7(_t5) (2.160)

6 6 6 6 6 6

*3 = 7 _7(-fi) +7H2)-7(-?4> -7(-?s)

6 6 6 6 6 6

are imposed on the binary (i.e. zero or one) variables x x2, x3 which are also restrained by the set-covering row

Xi + x2 + x3s=l. (2.161)

First, note that, by Exercise 2 above, the inequality

2 2 3 1 5

- +-f2 + -t2 + -f4+-t5 5= 1 (2.162)

is valid. Then apply Principle sdc, with the d(h) suitably chosen, to obtain the strengthened cut

12 3 11

-- ti+- t2 + - t3+- t4-- t53=l. (2.163)

(Hint: if properly done, you will find that b(,) dM = 1 for i = 1,2, 3.)

Exercise 7 (A cut for Gomorys group problem: Gomory, 1965) Show

that the inequality

0.83^+1.1612+1.2313^1 (2.164)

66 Robert Jeroslow

is valid, relative to the constraint set

3.7r1+9.3f3 + 1.5r3 =0.5 (mod 1)

(grp) 2.2fj +0.5t2+ 1.2f3 = 0.9 (mod 1)

h, h, *3^0, integer.

(Hint: use Principle mcs with T and M suitably chosen, and the functions Fj derived from disjunctive considerations. Always chose the easiest multipliers. Example 3 revisited is relevant.)

Exercise 8 Prove Principle sdc by subadditive means. You may use all results from Part 1 and 2 and Appendices.

Solutions

Solutions to the exercises follow. Several exercises have alternate solutions; we give only one.

Exercise 1 We rewrite (2.152) as the disjunctive requirement either

X yfc+i.jfj ~ yfc+i.o

or l? (2.165)

X ykjj = yfco- 1-

j'eJ

We obtain the cut

? maxjAjyk+u, AaykjItj^minjAiyk+^o, A2(yk.0-1)}. (2.166)

ieJ

Since (2.152) does not hold for i = k, we have yk+1,o>0 and yk,0< 1. Hence we may chose multipliers X.x = llyk+1-0, A2 = l/(yk,o_ 1). anc* the right-hand side in (2.166) becomes unity.

Many other choices of the multipliers make the right-hand side positive, and all these are acceptable.

Exercise 2 We deduce that at least one of the following inequalities hold:

X (-ak,)r, 3* i-ako- (2.167k)

j'eJ

Dividing both sides in (2.167k) by (l-ako)>0, we conclude that the cut X max { uk,7{l - ak0)}fj ^ 1 (2.168)

j'eJ fc

holds.

The Theory of Cutting-Planes

67

When (2.154) is a set-partitioning constraint, i.e. equality holds in (2.154), stronger cuts are possible; see Balas (1974a).

Exercise 3 For any feasible solution, at least one of the inequalities

r

X OiiXi^Oia (2.169,)

i = l

holds for some i = 1,.. ., p. Divide (2.159;) by a^X), and (2.157) follows, by Principle DC.

Exercise 4 One easily computes

Af =

00 if =s 0 for all i

.min {Oi0/aj; | a*, >0} if ait > 0 for some i

therefore

1M>|

lr

0

if a,, =? 0 for all i

Lmax {djj/Oio | Oif > 0} if atj > 0 for some i.

I

From (2.171), and the fact that

max {Oy/flio | aif > 0} = max {Oj,/^0>

(2.170)

(2.171)

(2.172)

if aj(>0 for some i, we see that (2.158) is a weakening of (2.157), hence valid.

Note that, if all a,, =s 0, so that the jth positive coordinate axis lies completely in the set of solutions to (2.156), then the fth coefficient is nonpositive, and usually negative, in (2.157), while it is zero in (2.158). This can provide a strict strengthening of (2.158). However, when the )th positive coordinate axis has a finite intersection value A,, the )th intercepts in (2.157) and (2.158) are the same.

This derivation of (2.158) shows that the linear independence assumptions of the earlier arguments in Balas (1971) were not needed. Also, in (2.156), one can delete inequalities which do not intersect the solutions to (2.156) at a point with x positive (i.e. in all coordinates), since that will not change the intersection of the solutions to (2.156) with the x 2=0 (see Jeroslow, 1974b, Section 3). This can further strengthen (2.158).

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