# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

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

We saw in Part 1 of this chapter that Principle ip can account for all valid cuts (cp) for (n>). Is there an analogous ‘adequacy theorem’ for Principle dc, relative to a suitable constraint set?

In fact there is, under certain hypotheses. Rather than give the most general statement possible, we cite here one frequently-realized hypothesis from which an adequacy result can be derived.

A Converse to Principle dc (Blair and Jeroslow 1976) Suppose that, for each heH, there is some choice of d(h) for which the set

is both nonempty and bounded, and suppose that H is finite.

Then all valid cutting-planes for the set S = UkshI-* I (Sh) holds} occur as weakenings of cuts (dc).

This converse is useful, since often in the systems (Sh) we have Ah = [K | Mh]tr, where the matrix Mh varies with heH, but K does not, and it is known that {x3s0 | Kx^d*} is bounded and nonempty for some d*. Then by taking any x*e{x5*0 \ Kx^d*}, it is easy to see that (x5*0| Kxs^d*, Mhx 2s Mhx*} is bounded and nonempty, thus verifying the hypothesis of the Converse with dlh) = (d*, Mhx*). For instance, often the system ? Kx 2s d contains all the constraints of the linear relaxation of a bounded integer program, while constraints Mhx c are implied by certain values of the integer variables.

(dc)

{X2*0| A(h)x^d(h)}

(2.131)

The Theory of Cutting-Planes

55

As a corollary to this Converse, one obtains all valid cuts to a consistent and bounded integer program (rp) as weakenings of (dc), by using as the systems (Sh) the following

(Sh)' Ax = b x = h

as heH varies over all integer points which may possibly solve Ah = b. By a ‘bounded’ program (ip), we mean that {x s=0 | Ax = b} is a bounded set, and from bounds for this set the index set H of (Sh)' can be determined. To obtain this corollary, in the Converse one sets

r a-

-A 7.

(2.132)

(viewing the equalities Ax = b as Ax s b and (— A)x 3= — b), and one can use

(2.133)

J(h) _

Bl

where x* is any solution to Ax* = b, x*3=0.

We remark that a Converse is also valid if each system (Sh) is consistent (Balas, 1975).

When hypotheses are lacking, it is possible for Principle dc to fail to provide all valid cuts. For instance, if either (— l)xt>— 1 or Ox, ^ 1 holds, then one obtains only the common weakening Ox, 5?0, which is worthless. Since 0x^1 is impossible, we know that 0=?x,«l; yet here Principle dc has thrown away information.

A version of Principle dc is also available for H finite, when the variables x are integer-constrained; it is obtained by combining Principle dc with Principle MCS.

Principle sdc (Balas and Jeroslow, 1975) Suppose that at least one system (Sh) holds, and that in addition there are ‘lower bounds\ i.e. all the systems

(*) A(h)x 3= d,h) x^O

hold, where dh^bh is a suitable vector. Finally, suppose that x is to be an integer vector, and let a<Jh) denote the jth column of A(fo. Then the inequality

f r I

X min max{A(h)(a°'h) + nh(bCh) — d(K)))} all nh are integer and ]T nh^Q

i = i

L heH

h =1

minkhb(h) (2.134)

heH

is valid.

56

Robert Jeroslow

Proof In Principle mcs, put

T = {(u(1),.. ., u<0) | all n<h)^ d(h) and at least one u(h) is 2sf>¹)}

(2.135a)

Now note that (2.138) implies that at least one system (Sw) holds. For if till nh =0 in (2.135b) then Axe T and at least one (Sh) holds; while if some nh^0 then at least one nh,5* 1 and then (Sh~) holds. Therefore (2.138) guarantees the validity of the cuts (dc).

Let a°h> denote the jth column of A(h) for j = 1,..., r and h = 1,..., t. Then we write (dc) as

and so the strengthened cut (2.123), for (2.139) taken as (2.122) is (2.134). That is, in Principle mcs we take Fj(a0)) = maxhEH\<h)a°h), where a1" is the ;th column of A, so that a0)tr = (a°1)tr, a(,2)tI,..., a00*1), f = |H|.

We give an application of Principle sdc as Exercise 6 in Appendix 2.4.

The disjunctive cut (dc), (2.139), can also be obtained by subadditive methods. First of all, by the Converse to Principle (bmip), there is a subadditive collection which yields a strengthening of (2.139). In this case, we can actually give an explicit representation for this subadditive collection, as follows.

In (2.97) of Part 1, we view that the matrices A and B are empty, i.e. there

(2.135b)

where t = \H\. Also4 set

A(1) A = •

Then the information we have can be represented as

Ax e T

(2.137)

which we now relax to

Ax e T + M.

(2.138)

X max{A(h)a?h)}x, 3=min ?(h)b(h)

(2.139)

j =1 hsH

The Theory of Cutting-Planes

are no binary or integer variables, only continuous ones. We put

f A(l,l

57

C =

(2.140)

with t = |H|, and

S = {(u(1),..., t/0)"1 D¹)?/)<h) for at least one h = 1,. .., t}

(2.141)

where vih) is of the same dimension as b'h\ We also see that the variables x occurring in the systems (Sh) are the variables y of (2.97) of Part 1.

Since there are no binary variables z,, the subadditive collection of Principle bmip reduces to one subadditive function F(0)(-) = G(-) (say), and only quantities G(-) enter in (2.98) of Part 1.

For the key step, we choose A ' 2= 0 for h = 1,. .., t and set

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