# Integer Programming

##### Basic Concepts

In a general integer programming or 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.
##### 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.