# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**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 PartitioningA 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 crRq 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 ao aijo J

f*d ~

I ao 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 PartitioningA 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)|.

kN

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).

**64**> 65 66 67 68 69 70 .. 156 >> Next