# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

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

P'^min1 fy>0. (1.10)

>eR Jij

Finally, a lower bound (penalty) on the decrease in z is

P* =max IP, max max{Pit P'}1. (I ll)

The penalty calculation (1.11) can be used in a number of ways. The most obvious is to revise the upper bound zk at node k to zk P*. This may result in immediate fathoming of the node. If not, (1.11) can be used to guide the branching, as we will see in Section 1.5.

A limitation of the usefulness of penalty calculations is the common occurrence of dual degeneracy in many milps. For such problems penalties will generally be zero and are therefore not worth calculating. Another more

8

Robert S. Garfinkel

serious drawback of penalties is that they provide information only about the next simplex iteration. In the case where a number of iterations are required to restore primal feasibility, the information contained in the penalties may be very weak. Since penalties are relatively costly to calculate their general usefulness is a matter of question.

1.5 Partitioning

For LP-based branch and bound algorithms the most natural means for separating a problem into subproblems is to introduce a set of contradictory constraints on one of the variables required to be integer. Suppose the relaxed lp has been solved at node k and the solution does not satisfy x, integer, all iel. A variable x,, re/ is chosen which has fractional value. That is, y,0 = [yrnl + fro where /rO>0. The separation strategy originally proposed by Land and Doig (1960) was to separate Sk into the sets

Skn{x|xr=0,(1.12)

where Ur is an upper bound on xr. Clearly (1.8) defines a partition of Sk.

A simplified partitioning rule was introduced by Dakin (1965). In it Sk is partitioned into

Sk n{x | x^M

and (113)

Sk D{x | xrs*[yr0]+l}.

Thus node k has been separated into two successor nodes by appending the contradictory constraints xr *? [yr0] and x, [yr0] +1. Obviously one or other of these constraints must be satisfied by any feasible solution. Rule

(1.13) has the obvious advantage over (1.12) of partitioning Sk into only two subsets and is used by all eleven commercial codes, except in the case of special ordered sets (Section 1.11). Code 1 also allows the possibility of branching on a variable which is currently integer.

Note that the penalties derived in (1.11) may provide for limiting the development of a node. For instance, if for some i, [zk D, ] 5* z but [zk- U-t]^z, then the node can be developed only in the downward direction without a corresponding increase in the tree size. In other words, this would be a forced move. Furthermore, if these conditions hold for more than one variable then these can be simultaneously forced in their appropriate directions without increase in the size of the tree.

If a forced move is not available, and increase in the tree size is therefore necessary, the next important issue is the choice of which fractional variable to choose for (1.13).

This question may be answered in various ways. Here we will discuss the use of priorities and quasi-integer variables, while in Section 1.7 we will

Branch and Bound Methods for Integer Programming

9

incorporate the concept of pseudo costs. Penalties were at one time highly regarded for guidance in branching, but the experience of Forrest, Hirst, and Tomlin (1974) has indicated that they are not reliable for this purpose.

Priorities

A priority structure is an ordering in importance of the set of variables. Priorities are used to choose a variable for partitioning with higher priority variables chosen first. All commercial codes except Code 4 allow for specification of a priority structure.

A number of methods can be used for establishing priorities. In some cases the user may know (or feel) that certain variables are critical and that others are of secondary importance. When the critical variables have integer values it may be that the secondary variables will naturally assume integer values as well. In this case it certainly makes sense to branch first on the high priority variables.

In the absence of prior information, priorities can be set by ordering the variables by cost, or possibly by use of the down and up pseudo costs of xi5 CP, and CP which are defined in Section 1.7. A rule proposed in Benichou et al. (1971) is to partition on that variable which maximizes

min{CP/,0,CP(l-/i0)} (1.14)

over i e I. The quantity (1.14) is an estimate of the minimum decrease in z over the successor nodes, and the rule is based on the hope of creating two nodes which can both be fathomed.

Quasi-Integer Variables

All commercial codes allow the user to specify a tolerance t such that a variable x, is considered integer if max {/l0, 1 /i0} < t. In general t is very small and the rationale is that computer round-off errors may cause a loss of accuracy. On the other hand, codes 1, 5, 6, 7, and 10 allow the specification of a number t*>t such that if max {fl0, 1 ~fio\< (*> then x, is called quasi-integer. Such variables may be considered computationally less important than those which are more seriously fractional. Branching may be restricted to the other variables in the hope that those which are quasi-integer will become integer-valued in the process.

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