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 .. 2 3 < 4 > 5 6 7 8 9 10 .. 156 >> Next

Clearly node k can also be fathomed if (1.2k) is infeasible (Tk = 0) since Sk ? Tk. This can be included as a special case of (1.3) by setting zk =— co when Tk = 0. It also follows directly from (1.3) that if the optimal solution to (1.2k) is in Sk then node k is fathomed.
Loosely speaking, ‘branching’ is nothing more than the process of deciding which node to consider next. By ‘considering’ node k we may mean: solving (1.2k); separating Sk; or possibly attempting to fathom by improving
Branch and Bound Methods for Integer Programming 5
the bound zk. In the next eight sections we elaborate on the ways that these steps may be performed.
1.3 Relaxation (Upper Bounding)
Clearly, to be of any value, (1.2fc) must be considerably easier to solve than (1.1k). 1° fact it is usually the case that the tighter the bound, the harder it is to calculate. The tightest bound would, of course, be achieved by letting (1.2fc) = (, and the easiest calculated would set zk = °°.
By far the most popular choice of relaxation is to let (1.2k) be the linear program (lp) obtained by relaxing the integrality constraint on x in ( This lp relaxation (lpr) satisfies the criterion of relatively easy computability. (Codes 1-11 of Table 1.1 all use this relaxation.) In many cases it also gives a good approximation to the ilp solution. In fact it is demonstrated in Rardin and Lin (1977) that the most important parameter in the success of branch and bound codes for ilp’s is the ‘distance’ from the lp optimum to the milp optimum. Except for the remainder of this section, this chapter will deal exclusively with algorithms based on lpr. However, other relaxations have been proposed and in some cases implemented. Two of these are mentioned below.
Lagrangian relaxation has been proposed for milp algorithms by a number of authors. The reader is referred in particular to Geoffrion (1974) and Shapiro (1971). For milp’s of the form
max cx
Dx ss d
X 3=0, x, integer, j ˆ I,
the lagrangian relaxation is
max cx - A (Ax - b)
Dx =? d (1.5)
X 3s o, Xj integer, j e I
where A. is a nonnegative vector. Here it is assumed that the constraints Dx=sd have a special structure which render (1.5) virtually trivial to solve (see Geoffrion 1974 for some illustrative examples). A branch and bound algorithm based on (1.5) would involve some method for choosing values of the multiplier vector X in order to make (1.5) a tight relaxation.
Another relaxation which has been proposed (see Shapiro 1968) mainly for ilp’s is referred to here as the group-theoretic relaxation. Let the ilp be
represented by
RobertS. Garfinkel
max 2 = y00 - X Vo,*,
x, = yi0~ X yifXji i = 1,.. ., m (1.6)
X; s* 0, integer i = 1,.. ., m Xj 5= 0, integer, j eR
where the elements y,, are the coefficients of the simplex tableau resulting from the solution of lpr. Thus the variables x, are basic and R is the set of nonbasic variables. The relaxation (gtr) results from dropping the nonnegativity restriction on the basic variables. It has been shown by Gomory (1965) that the gtr can be solved as a group knapsack problem.
1.4 Penalties
The concept of penalties in integer programming was introduced by Driebeek (1966) and Beale and Small (1965). An extensive treatment can be found in Tomlin (1970). The development here closely follows that of Garfinkel and Nemhauser (1972a). Penalties are an integral part of codes 1, 4, 7, 10, and 11.
They are introduced directly after the section on relaxation because they can be thought of as a means for attaining better upper bounds. They can also be used in the branching process as will be seen in Section 1.5
Consider an optimal lp solution at any node which has at least one fractional row given by
x\ ~ Yio- X yuxi
vhere i el, yw = [yi0]+fio and fiO>0. Here [yi0] denotes the integer part of ji0. Since x, is required to be integer, either x, =s[yl0] or x, s=[yi0]+ 1. If the xmstraint ^ «[yy0] holds then it can be represented in the simplex tableau
X y.A, ^/<0-
Tie pivot column for the next dual simplex interation will be determined by
Branch and Bound Methods for Integer Programming so that the objective will decrease by the down penalty
Dj= min^^ yt, > 0. (1.7)
fsR Vi;
Of course D, is only a lower bound on the decrease in 2 since additional pivots may be required to obtain feasibility. An up penalty Ut corresponding to the condition Xj55[yi0]+1 can similarly be defined as
Uj = min (fi0 — 1) — y^X). (1.8)
)?« yij
It follows that
Pt =min{l/i, A}
is a valid lower bound on the decrease in 2 incurred while obtaining feasibility.
In the case of ilp’s two other bounds are given below. The first is derived from the simple observation that some nonbasic variable must increase at least to the value one. Thus
P = min y0, (1.9)
is also valid.
The last bound is derived from the cut of the method of integer forms (see Gomory, 1958; Jeroslow, 1977) given by
X o-
The first dual simplex pivot would yield a decrease in z of
Previous << 1 .. 2 3 < 4 > 5 6 7 8 9 10 .. 156 >> Next