# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

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

monoid, ?,r=i m(j)xjeM for any integer vector x3=0. Consequently Axe

T + M implies

X (a^ + m^x, = ? nu>x,+ X m0)x; eT+M + M = T + M (2.124)

i=i i=i j=i

(the last equality since M is a monoid), which in turn implies (by the hypothesis)

X f)(a0) + m0))xf>7r0. (2.125)

/ = 1

In brief, AxeT + M implies (2.125) for any arbitrary choice of the m0), hence (2.123).

Note that the infimumover meMin (2.123) need not be computed, since for any meM, the quantity F}(a0) + m) is a valid upper bound on the /th intercept in (2.123).

Example 3 revisited (From Balas, 1974a) If y is an integer variable with tableau row

y = 0.5 +10.5(L) 5(f2) + 3.5(13) (2.116')

then from (2.120) we see that

21fj + 10r2 + 7f35s 1 (2.120')

is a valid cut. If the variables tj are continuous in (2.120'), no real

strengthening of (2.120') is possible. Indeed, (y, tu t2, ?3) = (0, 1/28,0,1/28)

solves (2.116'), makes y integral, and makes (2.120') an equality.

Suppose now that the variables t, are integral in (2.116'). We shall use Principle mcs to strengthen the cut (2.120').

We view (2.116') as

X (-a,)t,e T + M (2.126)

where T = {-0.5}, a1 = 10.5, a2 = -5, a3 = 3.5, and M is the set of integers, which is a monoid. Now (2.126) is of the form (2.121) where A has one row, A = [-a,] (i.e. a(l) = -a, for j e /), and x is the vector of nonbasic variables tj, jeJ. For T held fixed, our reasoning in Example 3 showed that (2.120) is always valid (i.e. tt0= 1 in (2.123)), so in (2.122) we may use

Fj(au)) = max {ajf, -a,/( 1 -/)}. (2.122')

Therefore the /th intercept of the improved cut (2.123) is

inf {max{(Oj-n)//, (-Oj+ n)/(l-f)} | n integer}. (2.127)

The Theory of Cutting-Planes

53

We need only estimate (2.127). Putting n = [a, J, where [a, J is the integer part of af, and at = LaJ +/j, 0^/j <1. we have

max {(a, - n)jf, (-a, + n)j( 1 -/)} = /,//. (2.128a)

Next, putting n = [aj + 1, we have:

max {(a, - n)/f, (a,- + n)/( 1 -/)} = (1 - f )/(l -/). (2.128b)

To get an upper bound on (2.127) we can use any choice of n, hence we use the most favourable, and conclude that the coefficient of l, in a valid cut can be taken to be

min {/,//, (1 /j)/(l /)} (2-129)

(Actually, (2.129) is equal to (2.127).)

Using (2.129), from (2.116') we obtain the cut

t^+0t23-(2.130)

as (2.123). Clearly, (2.130) is stronger than (2.120'). It in fact cuts off the point (0, 1/28, 0, 1/28) that satisfies (2.120').

The cut (2.130), and cuts desired in this manner with M = the integers, are valid for Gomorys group problem (Gomory, 1965), and are in fact among the cuts given in that paper. They are usually associated with the subadditive methods, but can also be derived as a strengthened disjunctive cut; see Exercise 7 in Appendix 2.4 for a similar derivation of another cut for the group problem. Principle mcs was abstracted from a study of Gomorys addition of unit rows in deriving the cuts in Gomory (1963), and its use goes beyond the setting of the group problem (see, for example, Exercise 6, where a cut with negative coefficient is derived by means of this principle.)

A sense in which Principle mcs strengthens disjunctive cuts is as follows. Since a disjunctive cut is based on a logical condition, any branching scheme which imposes this condition makes the cut redundant on each branch. Thus, the cut (2.120') would be redundant if either y 5*0 or y ^ 1 is imposed on the variable y of (2.116') in a branch and bound scheme. However a strengthened disjunctive cut, such as (2.130), often is not redundant after branching ((2.130) is not redundant on the branch i= 0).

If unstrengthened disjunctive inequalities are used in a branch and bound approach, they provide cuts that allow one to estimate penalties (without the cut actually being added), or the cuts can be added explicitly if the branching is done on a different logical condition than the one from which the cut is derived. For instance, in Example 1, if, in addition to the pair (xlt y,) there is a second pair of variables (x2, y2) with x2y2 = 0 desired, one can branch on x2 = 0 versus y2 = 0 and simultaneously add the cut (2.107). The addition of (2.107) recovers some of the benefit to be obtained by branching on xx = 0 versus y, = 0, while one actually branches on a different logical condition.

54

Robert Jeroslow

In order to further discuss the disjunctive methods, we need a precise

statement of the main principle involved, and we provide it next. The proof is omitted, since it proceeds by the considerations we have used in working the examples above.

Principle dc Suppose that at least one of the systems (Sh) holds for some heH, where (Sh) is

and A(h) is an mhx.r matrix and b(h) is an mh x 1 vector.

Then for any 1 x mh vectors A.(h)5=0 of nonnegative multipliers, the inequality

holds, as do any of its weakenings. In (dc), supheH A(h)A(h) denotes that vector whose jth component (j = 1,.. ., r) is suphEH u,-h), and nth) = A(h)A(,1\

(The sups and the inf of (dc) are assumed to exist. Of course, for H finite, as is usually the case, a sup is a maximum and an inf is a minimum.)

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