T
minimize c x
subject to A x = b
1 1
A x <= b
2 2
l <= x <= u for i = 1 ... n
i i i
x_j integer for all j in D which is a subset of {1...n},
where A is a m x n matrix, A is an m x n matrix, m + m = m.
1 1 2 2 1 2
If all the variables can be rational (the set D is empty), this is a
linear programming problem, which can be solved in polynomial time.
In practice linear programs can be solved efficiently for
reasonable-sized problems, or even for big problems with special
structure. However when some or all of the variables must be integer,
corresponding to pure integer and mixed integer programming
respectively, the problem becomes NP-complete (formally intractible).
For the sake of this discussion, assume that all variables must be integral. The general methods can be easily extended to the mixed-integer case.
Branch and Bound
The most widely used method for solving integer
programs is branch and bound. Subproblems are created by restricting
the range of the integer variables. For binary variables, there are
only two possible restrictions: setting the variable to 0, or setting
the variable to 1. More generally, a variable with lower bound l and
upper bound u will be divided into two problems with ranges l to q and
q+1 to u respectively. Lower bounds are provided by the
linear-programming relaxation to the problem: keep the objective
function and all constraints, but relax the integrality restrictions
to derive a linear program. If the optimal solution to a relaxed
problem is (coincidentally) integral, it is an optimal solution to the
subproblem, and the value can be used to terminate searches of
subproblems whose lower bound is higher. See the branch and bound section of this
survey for more details on how lower bounds, upper bounds, and
branching interact.
Branch and Cut
For branch and cut, the lower bound is again provided by the
linear-programming (LP) relaxation of the integer program. The
optimal solution to this linear program is at a corner of the polytope
which represents the feasible region (the set of all variable settings
which satisfy the constraints). If the optimal solution to the LP is
not integral, this algorithm searches for a constraint which is
violated by this solution, but is not violated by any optimal integer
solutions. This constraint is called a cutting plane. When this
constraint is added to the LP, the old optimal solution is no longer
valid, and so the new optimal will be different, potentially providing
a better lower bound. Cutting planes are iteratively until either an
integral solution is found or it becomes impossible or too expensive
to find another cutting plane. In the latter case, a tradional branch
operation is performed and the search for cutting planes continues on
the subproblems.
Branch and Price
This is essentially branch and bound combined with column generation.
This method is used to solve integer programs where there are too many
variables to represent the problem explicitly. Thus only the active set
of variables are maintained and columns are generated as needed during
the solution of the linear program. Column generation techniques are
problem specific and can interact with branching decisions.
References
Just about any Operations Research book will give an introduction to mixed-integer
programming. A particularly good one is George L. Nemhauser and Laurence A. Wolsey,
Integer and Combinatorial Optimization, John Wiley & Sons, New York, 1988.
Miscellaneous Links
MIPLIB is a library of pure and mixed integer programming problems from real
applications.
A Tutorial on Integer Programming