Branch and Bound
Although a number of algorithms have been proposed for the integer linear programming
problem, the branch-and-bound technique is used in almost all of the software in
our survey. This technique has proven to be reasonably efficient on practical problems,
and it has the added advantage that it solves continuous linear programs as subproblems,
that is, linear programming problems without integer restrictions.
The branch-and-bound technique can be outlined in simple terms. An enumeration tree
of continuous linear programs is formed, in which each problem has the same constraints
and objective as (1.1) except for some additional bounds on
certain components of 
. At the
root of this tree is the problem (1.1) with the requirement 
removed. The solution to this root
problem will not, in general, have all integer components. We now choose some noninteger
solution component 
and define 
to be the integer part of , that is, 
. This gives rise to two subproblems.
The left-child problem has the additional constraint 
, whereas in the right-child problem we impose 
. This branching process can
be carried out recursively; each of the two new problems will give rise to two more
problems when we branch on one of the noninteger components of their solution. It follows
from this construction that the enumeration tree is binary.
Eventually, after enough new bounds are placed on the variables, integer solutions are obtained.
The value 
of 
for the best integer solution found so far is
retained and used as a basis for pruning the tree. If the continuous problem at one of the
nodes of the tree has a final objective value greater than 
, so do all of its descendants, since they have smaller
feasible regions and hence even larger optimal objective values. The branch emanating from
such a node cannot give rise to a better integer solution than the one obtained so far, so
we consider it no further; that is, we prune it. Pruning also occurs when we have added so
many new bounds to some continuous problem that its feasible region disappears altogether.
The preferred strategy for solving the node problems in the enumeration tree is of the
depth-first type: When two child nodes are generated from the current node, we choose one
of these two children as the next problem to solve. One reason for using this strategy is
that on practical problems the optimal solution usually occurs deep in the tree. There is
also a computational advantage: If the dual simplex algorithm is used to solve the linear
program at each node, the solution of the child problem can be found by a simple update to
the basis matrix factorization obtained at the parent node. The linear algebra costs are
trivial.
Two important questions remain: How do we select the noninteger component 
on which to branch, and how do we
choose the next problem to solve if the branch we are currently working on is pruned? The
answer to both questions depends on maintaining a lower bound 
on the objective value for the continuous linear program
at node 
, and an estimate 
of the objective value of the best
integer solution for the problem at node . Both values can be calculated
when the problem at node is generated as the child of another problem. After the current
branch has reached a dead end, there are two common strategies for selecting the next
problem: Choose the one for which 
is least or choose the one for which 
is least. Other strategies use some criterion function
that combines 
, 
, and 
.
In many codes, the user is allowed to specify a branching order to guide the
choice of components on which to branch. By the nature of the problem, some components of may be more
significant than others; the algorithms can use this knowledge to make branching decisions
that lead to the solution more quickly. In the absence of such an ordering, the degradations
in the objective value are estimated by forcing each component in turn to its next highest
or next lowest integer. The branching variable is often chosen to be the one for which the
degradation is greatest.
The CPLEX, FortLP, LAMPS, LINDO, MIP III, OSL, and PC-PROG packages use the
branch-and-bound technique to solve mixed-integer linear programs. The NAG Fortran Library (Chapter H)
contains a branch-and-bound subroutine, and also an earlier implementation of a cutting
plane algorithm due to Gomory. (The latter code is scheduled for removal from the library
in the near future.) GAMS interfaces
with a number of mixed-integer linear programming solvers, and even with a mixed-integer
nonlinear programming solver. LINDO
has two other front-end systems: LINGO
provides a modeling interface to it, while What'sBest! provides a
variety of spreadsheet interfaces.
The CPLEX integer
programming system can be used either as a stand-alone system or as a subroutine that is
called from the user's code. CPLEX
also implements a branch-and-cut strategy, in which the bounds on optimal
objective values are tightened by adding additional inequality constraints
to the problem. The matrix 
and vector 
are chosen so that all integer vectors satisfying the
original constraints 
, 
, also satisfy . These extra constraints (cuts)
have the effect of reducing the size of the set of real vectors that is being considered
at each node.
The Q01SUBS
package contains routines to solve the quadratic zero-one programming problem
where 
may be indefinite,
while the QAPP package solves the
assignment problem with a quadratic objective. Both algorithms use a branch-and-bound
methodology similar to the techniques described above.
Up To:
Integer Programming
[ OTC Home Page | NEOS Guide | NEOS Server
| Optimization Tree ]
Updated 28 March 1996