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 .. 58 59 60 61 62 63 < 64 > 65 66 67 68 69 70 .. 156 >> Next For instance, let the linear program associated with spp have an optimal solution of the form
=ai0+T ielLSJ
ieJ
where I and J are the basic and nonbasic index sets respectively (i.e. for i e J, dio = 0 and a,, = 0 for i ^ j, alt = -1 for i = j), and let
I *< = 1
jeO
be one of the constraints of spp, such that QV0, where Q' = (i e Q | 0 < djo < 1}. Note that this equality is satisfied by the current solution, so it cannot be used as a cut. However, the logical condition that it
Set PartitioningŚA Survey
173
expresses, namely that exactly one of the variables xr j e Q, must be one, and all the others zero, i.e.
V
(xi = l, ? xh=o|
' ieO-(i) >
is violated by the current solution and can be used to generate a cut.
Let (T = (o-i) be a q-vector, where q = |Q|, such that O^Scr^l, VieQ. If the numbers <T;, 1 Ś ^ are used to take convex combinations of the two equations within each member of the above disjunction, the latter becomes
V
ieO
(l-o-i)x,+o-,( ? = ?
VeQ-li) > -1
Consider now the family of relaxations of Pr whose members are of the form convF(cr), for some crłRq such that O^Oj *?l, ieO, where
F(cr) =
teF"
x, = ai0 + Y. Biji-tj), ie/nQ
ieJ
\$3* 0, jeJ,
V
ieQ
(l-cT^Xj +<Ti( ? xh) = l-Oj
L VeQ-W > -1 .
The family of cuts defined in the next theorem is from Balas (1974a). The fact that it represents the family of those facets of conv F(<r) which cut off the current solution follows from Theorem 4.5 of Balas (1974b).
Theorem 7.18 For every creRq such that 0^o-i =? 1, Vi e Q, the unique facet of conv F(cr) which cuts off the solution tj =0, je J, is
where
X ^(er)*,[3=1
jeJ
a,(cr) = max((r, ? aK, -ayKl-Ojo)-1 /eJ.
>sQ ' heO '
These cuts are computationally not expensive, and one has some freedom in choosing the parameters er, so as to make the cut stronger in one direction or another. A very convenient choice of the parameters, which makes the cut particularly easy to compute, is cr{ = (1 Ś ai0), Vi e Q, which yields
a;= ? ahj-min 0^,(1-Oio)ō'.
heQ ieO
Note that this cut is likely to have some negative entries, since the coefficients ahj of the current simplex tableau are of arbitrary signs.
174
Egon Balas and Manfrea vV. Padberg
Another disjunctive cut, computationally even cheaper, yet of considerable strength, is the following.
Theorem 7.19 (Balas, 1976) Let Q and Q' be as in Theorem 7.17, but ij, i2e Q', and
Then the inequality
S, = {jeJ
*? Oi,0 J
X ½jtj 3╗ 1
S2 = J-S!.
is a valid cut, with
fa;, Ś 1 dj )
max 1 Śr---, >
l aäo aijo J
f*d ~
I aäo d,a() J
f^i, max
1─,Ņ 1 ?h0 a^Q J J
{?^, max{^^,%zl]| lai20 I <^,0 <h20 æ J
max
mm
jsQDSj j e Q Ž S2 /efAQJnS, je(J\Q)nSz.
? F =d,0+ X ½./(ōI/) ie/nQ
je/
(eR" ╬ ╦\ j eJ
( I ? x^O
ä 60, ) \eQ, '
This cut can be shown to be a strengthening of the (unique) facet of conv F' which cuts off the current solution, where
F =
and where Qk ={ifc}U(Q nSk), k = 1,2.
In choosing ij and i2, it is reasonable to give preference to the pair with the largest number of negative coefficients in both rows; this yields a cut with at least that number of negative coefficients.
Each of the above two cutting planes can further be strengthened at a reasonable computational cost by using the integrality constraints on the nonbasic variables, via the procedure of Balas and Jeroslow (1975). Whether strengthened or not, these cutting planes can be used in the context of a simplex-based dual cutting plane algorithm of the type to be discussed in Section 7.3.2, in the same way as the Gomory cuts are used. Since the above cuts use the structure of the set partitioning polytope, their use can be expected to enhance the convergence rate of the algorithm.
Set PartitioningŚA Survey
175
In the next section we discuss a different class of valid inequalities, which are all-integer and unrelated to any solution to the linear programming relaxation of spp.
7.2.4 Other Valid Inequalities
In this section we discuss the class of valid inequalities introduced by Balas (1975c). These inequalities are derived from the logical implications of the set partitioning constraints, and they often dominate some facet of the set packing polytope, and thus cut off one or more vertices of the latter. The results of this section are from the above-mentioned paper.
As before, let P, be the set partitioning polytope, Pr the set packing polytope, and let M and N be the row and column index sets of A = (a,,). Denote
M(k) = {i e M | alk = 1}
N(i) = {j ł N aiy = 1} and for keN, ieM(k), let
N(k, i)={(ieN(i) | ahak = 0}.
Theorem 7.20 For every keN and ieM(k), the inequality
(a) xk- I x,½0
jeN(k, i)
is satisfied by all x e Pv Further, every nonzero vertex of PIt not contained in Pr, is cut off by at least one inequality (a); each such inequality cuts off some xePj Ś P,.
Remark 7.6 The number of inequalities of the above form is
I |M(k)|.
kłN
Theorem 7.21 For every keN, ieM(k), and Q(k, i)c N(k, i), the
inequality
(0) xk- X
/ eO(fc.i)
is valid if and only if x e vert P,, xk = 1 implies x, = 0, V; e N(k i)Ś Q(k, i). Previous << 1 .. 58 59 60 61 62 63 < 64 > 65 66 67 68 69 70 .. 156 >> Next 