# Mixed Integer Programming

## Overview

A mixed-integer program is the minimization or maximization of a
linear function subject to linear constraints. More explicitly,
a mixed-integer program with n variables and m constraints has the form:
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.
## Application Domains

Mixed integer programs can be used to formulate just about any
discrete optimization problem. They are heavily used in practice for
solving problems in transportation and manufacturing: airline crew
scheduling, vehicle routing, production planning, etc. Michael
Trick's Operations
Research Page contains pointers to many web sites on operations
research in general, including math programming, specific methods, and
specific problems or problem areas. The following are good journals
to look at for technical papers applying integer programming: Operations
Research,
Mathematical Programming Series A and B, and SIAM Journal on
Optimization .
## Software

Commercial code includes IBM's Optimization Subroutine Library OSL, CPLEX, and XPRESS-MP by Dash. The University of
Karlsruhe has a list of 23
commerical solvers (as of 3/97), with some comparison information.
Compass Modeling Solutions,
provides an AMPL (AT&T
Mathematical Programming Language interface to some commercial
solvers. There are other modeling languages, sometimes provided
with the MIP package.

## 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.
Linear Programming FAQ

A Tutorial on Integer Programming

Global Optimization Survey - Main Page

Sandia National Laboratories

This page maintained by wehart@cs.sandia.gov
Last modified: March 10, 1997