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