# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**23**> 24 25 26 27 28 29 .. 156 >> Next

By Exercises la and lb of Appendix 2.1, G is subadditive. For any scalar

p_3s0, A(>0 (pvih))/p = A(h)u\ and hence using (2.83) of Part 1, we find that G(-) = G(-). Finally, we compute

inf {G((uu),..., u(t') I (tj(1),.. ., D(t)) S}= inf {A(h)6(h1} (2.143)

using A(h)>0 and the fact that u(K>3=b(h> for h = 1,.. ., t.

Combining (2.142), G = G, and (2.143), the cut (2.98) of Part 1 is (2.139), as desired. This completes our derivation of (dc), (2.139), as a subadditive cut.

The derivation of disjunctive cuts by subadditive methods, or subadditive cuts by disjunctive methods, establishes some theoretical interrelations, as was done in Jeroslow (1974a, b, 1977a). It does not provide a new cut and often, as was the case above, simply parallels the earlier proof in a laborious and more complex fashion.

In an Olympian sense, either the disjunctive or subadditive methods provide a complete theory of valid cuts for the bounded integer program (ip), at least after subadditivity is extended from the group problem to (ip). So it would not be enlightening to claim that a subadditive derivation of a cut discovered by disjunctive methods showed that the cut was simply one illustration of subadditive cuts. Indeed, as we saw, subadditive cuts are a special case of disjunctive cuts. Such claims simply obscure the fact that the broad principles of subadditivity, such as Principle ip, are reductions of the

G((um,..., uc0)T) =max{A(h)u(h)}.

(2.142)

58

Robert Jeroslow

question of cutting-planes to that of subadditive functions. The key issue of the subadditive approach is the construction of suitable subadditive functions. The fact that disjunctive reasoning does provide many useful subadditive functions is a recommendation for disjunctive methods.

Analogous to the linear systems (fs) of Appendix 2.2, Balas (1974b) has associated linear systems with the logical constraints of the disjunctive methods, and provided characterizations of the best cuts (facets, etc.) obtainable from the extreme points of these systems, hence of the best cuts for the relaxations represented by these systems. These linear systems are for the unstrengthened disjunctive cuts (dc) and are closely related to branch and bound. They allow one to compute, for example, facets of the convex span of the union given by

(x Ax = b, x 0, X! = 0} U {x | Ax = b, x 3= 0, Xj = 1} (2.144)

in the notation of (rp). In contrast, the relaxations associated with the subadditive methods can obtain information not easily obtained from branch and bound, as we saw in Part 1.

As with the subadditive methods, these relaxations can be taken to be the integer program itself, typically at the cost of (an excessively) large linear system. We note that the linear systems we provided in Jeroslow (1974a), equation (108), simplify to Balas system for the special case of systems (Sh), after certain algebraic manipulations of the type we discuss in Jeroslow (1974a), pp. 77-80 (see Ho, to be published, for details).

In Jeroslow (1974a), we generalized Principle dc by assigning, to every proposition A, a family of cuts cp(A). We used the natural mapping of the lattice of propositions, under the connectives or and and, into the lattice of convex polyhedra. If A is the proposition (S)! v ? v(S), i.e. at least one system (Sh) holds, cp(A) was equal to all weakenings of all disjunctive cuts (dc) for all multipliers Ah ^0. But the assignment was still defined if A had a more complex form, e.g. ((BaC)vD)a? for propositions B, C, D, E, although cp(A) depended on the syntactic form of A as much as its truth. We also assigned a linear system to each proposition A. Details of this co-proposition assignment and results about it are in Jeroslow (1974a, 1977a).

We now turn to a theoretical result in the disjunctive methods, due to Balas, which introduces a distinctly new idea that has been fruitful in obtaining other results and providing an alternate proof for an important result (Blair, 1976a). Balas states his result in terms of bounded systems with facial constraints, and these systems include the binary integer program:

(bip) Az 3= d, Zj =0 or 1 for j = 1,..., r.

The features of (bip) which make it facial are that it can be stated in the

The Theory of Cutting-Planes

59

form:

Az Ssd Q^z^e (2.145a)

with e = (1,..., l)rr a vector of ones, plus the constraints

(or ZjS^l) (2.145b)

and

(-z2s=0 or z23l)

and

(-zrs=0 or zr3l).

Furthermore, in the form (2.145) each inequality zs 3 0, or z, 3 1, appearing in the logical constraints (2.145b), is the opposite of an inequality z, 30, or z, 1, which is implied by the purely linear constraints (2.145a) alone. (In the terminology of Rockafellar (1970), each inequality in (2.145b) provides a face of (2.145a)).

Balas abstracts these features of (bip) to obtain his concept of a facial constraint system, but here we shall content ourselves with stating his result for (bip) alone. Other examples of facial constraints include linear complementarity problems (Cottle and Dantzig, 1968; Eaves, 1971; Jeroslow, 1978) and generalizations of these (Jeroslow, 1978).

**23**> 24 25 26 27 28 29 .. 156 >> Next