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 .. 20 21 22 23 24 25 < 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).
Previous << 1 .. 20 21 22 23 24 25 < 26 > 27 28 29 30 31 32 .. 156 >> Next