in black and white
Main menu
Share a book About us Home
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics

Combinatorial Optimization - Cristofides N.

Cristofides N. Combinatorial Optimization - Wiley publishing , 2012. - 212 p.
Download (direct link): сombinatorialoptimi2012.pdf
Previous << 1 .. 15 16 17 18 19 20 < 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
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
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.
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.)
Previous << 1 .. 15 16 17 18 19 20 < 21 > 22 23 24 25 26 27 .. 156 >> Next