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