# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**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) = (l.lk), 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 (l.lk). 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 ilps 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 milps of the form

max cx

(1-4)

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 ilps is referred to here as the group-theoretic relaxation. Let the ilp be

6

represented by

RobertS. Garfinkel

max 2 = y00 - X Vo,*,

|?R

x, = yi0~ X yifXji i = 1,.. ., m (1.6)

j'eR

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

jeR

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

is

X y.A, ^/<0-

ieR

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

7

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 ilps 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)

,eR

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-

leR

The first dual simplex pivot would yield a decrease in z of

**4**> 5 6 7 8 9 10 .. 156 >> Next