# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

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

Finheness

In general the finiteness of branch and bound algorithms for milps based on (1.13) is assured. The only assumption needed to guarantee finiteness is that there exist finite upper bounds L( on x, for all j e I. If the problem has a

12

Robert S. Garfinkel

process. Another representation of the same tree has been proposed, by Forrest, Hirst, and Tomlin (1974), which seems somewhat more informative. The same problem is illustrated with this tree in Figure 1.3. The heavy solid line shows the path to the optimal solution and the heavy dashed line the path to the first integer solution. Light solid lines show paths to other integer solutions and light dotted lines to noninteger nodes which are fathomed.

1.7 Pseudo Costs

Pseudo costs have often been found to be more accurate indicators of the relative importance of the variables than are their original costs. The purpose of pseudo costs is to estimate the change in objective function value caused by forcing a variable which is currently fractional to be integer. The concept is much the same as that of the penalties introduced in Section 1.4. However, the latter only give local information since they are concerned only with the next dual simplex iteration. Pseudo costs attempt to forecast the change when the variable goes all the way to integrality. Pseudo costs are also not based on local information. They assume that the effect on the objective function associated with changing a variable in a particular direction remains constant throughout the tree. Although there is no theoretical reason to justify this assumption, it has been discovered empirically to be the rule rather than the exception. Pseudo costs are used by codes 5, 6,1, and 10.

Let the up (down) pseudo costs of x, be denoted by CY (Cf). In general these values are unknown at the beginning of the enumeration process. They can be estimated by the user, or perhaps by the original costs of the variables. They can also be estimated by performing small experiments (Gauthier and Ribiere, 1977) previous to the enumeration process. As the enumeration proceeds these estimates can be updated every time a variable is driven to integrality.

The formula used by Gauthier and Ribiere (1977) to calculate CY and Cf is based on Figure 1.4. Assume that node k has been partitioned based on x i I and note that at nodes k +1 and k+2, x, will be integer valued. We then take

^k + l ' /.0

and (1.15)

<-.U_ ~Zk+2

' 1 ~fi0 '

Note that Cf and CY are both nonnegative.

Based on (1.15) we may estimate a bound on the objective value of the

Branch and Bounu. Methods for Integer Programming 13

*i = Uo} Xr-U ol+1

Figure 1.4

best descendent of node k by

Ek = zk - I min {CP/io, CH( 1 - fi0)}. (1.16)

ieT

The formula (1.11) assumes independence of the variables x, and their corresponding penalties. It can be used in the branching process, as we shall see in the next section.

1.8 Branching

By branching we will mean the decision as to what to do next. At any stage the options available are:

(a) Solve the relaxed lp at some node k;

(b) Calculate penalties at some node k;

(c) Select a node k and partition Sk;

(d) Attempt to achieve a better lower bound z (see Section 1.9).

At any stage in the enumeration process, the set of nodes which are candidates to be node k in (a-c) above are referred to as the live (waiting) nodes. These are nodes which have been neither fathomed nor partitioned. Termination of the entire enumeration process occurs when this set is empty.

Node selection rules (choice of which unfathomed node to investigate) are less standard than partitioning rules. Sketches of a number of possible rules are given in this section.

The ultimate objective is to solve the problem in as short a time as possible. Solution time is itself a function of the final tree size as well as the amount of computation done at each node of the tree. For the moment,

14

RoberrS. Garfinkel

focusing only on the tree size, a rule which in some sense guarantees a smallest tree is branch to the greatest upper bound (). That is, examine next that node for which zk is greatest over all live nodes.

Disadvantages associated with the rule include the possible problems involved in jumping around the tree from one node to another. Data describing various nodes including the current basis inverse may have to be shifted from internal to external computer storage. Another disadvantage is that there is no initial push to locate a good feasible solution. Thus termination short of optimality because of time limitations may leave the user without a good solution, and the fathoming test (1.3) may not be powerful in the early stages of the enumeration.

A strategy which attempts to overcome these disadvantages is the lifo strategy in which the next node investigated is one of the successors of the current node if either is unfathomed. The lifo strategy alleviates some of the storage problems and also strives to find a feasible solution quickly. On the other hand, it may discover a number of inferior solutions which could otherwise have been fathomed by a strategy.

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