Integer Linear Programming

Contents

Back to Discrete Optimization

Basic Concepts

In a general integer linear programming problem, we seek to minimize a linear cost function over all \(n\)-dimensional vectors \(x\) subject to a set of linear equality and inequality constraints as well as integrality restrictions on some or all of the variables in \(x\).

\[\begin{array}{llll}
\mbox{min} & c^Tx & & \\
\mbox{s.t.} & Ax & = & b \\
& x & \geq & 0 \\
& x & \in & Z^n
\end{array}
\]

  • If only some of the variables \(x_i \in x\) are restricted to take on integer values (and some are allowed to take on real values), then the problem is called a mixed integer linear programming (MILP) problem. If the objective function and/or constraints are nonlinear functions, then the problem is called a mixed integer nonlinear programming problem (MINLP).
  • If all of the variables \(x_i \in x\) are restricted to take on integer values, then the problem is called a pure integer programming problem.
  • If all of the variables \(x_i \in x\) are restricted to take on binary values (0 or 1), then the problem is called a binary optimization problem, which is a special case of a pure integer programming problem.

We use the term MIP to refer to any kind of integer linear programming problem; the other kinds can be viewed as special cases. MIP, in turn, is a particular member of the class of discrete optimization problems. In fact, the problem of determining whether a MIP has an objective value less than a given target is a member of the class of \(\mathcal{NP}\)-Complete problems. Since any \(\mathcal{NP}\)-Complete problem is reducible to any other, virtually any combinatorial problem of interest can be handled in principle by solving some equivalent MIP.

Software Resources

  • Mixed Integer Linear Programming Solvers available on the NEOS Server
  • A. Lodi and J. T. Linderoth. (2011) "MILP Software," Encyclopedia for Operations Research and Management Science, Wiley, pp. 3239-3248.
  • J. T. Linderoth and T. K. Ralphs. (2005) "Noncommercial Software for Mixed-Integer Linear Programming," in Integer Programming: Theory and Practice, Karlof, J., Ed., CRC Press, pp. 253-303.

Test Problems

Case Studies

NEOS Guide Case Studies

References

Textbooks

  • G.L. Nemhauser and L.A. Wolsey. (1988) Integer and Combinatorial Optimization, John Wiley & Sons, New York.
  • A. Schrijver. (1984) Linear and Integer Programming, John Wiley & Sons, New York.
  • L.A. Wolsey. (1998) Integer Programming, John Wiley & Sons, New York.

Journal Publications and Technical Reports