### 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

- Bioengineering: Metabolic Engineering Problem
- Puzzles: The Abbott's Window
- Puzzles: Rogo
- Supply Chain: Bar Crawl Optimization
- Supply Chain: Cutting Stock Problem

## 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

- Optimization Online Integer Programming area