Integer Linear Programming

Definition

Integer Linear Programming

Integer linear programming is the optimisation problem with fixed input $A\in {\mathbb{Z}}^{m\times n}$, $b\in {\mathbb{Z}}^m$, $c\in {\mathbb{Z}}^n$:

$$\underset{x\in {\mathbb{Z}}^n}{\max }\underset{{\sum }_{j=1}^n{c}_j{x}_j}{\underbrace{c^{\top }x}}\text{subject to}\underset{{\sum }_{j=1}^n{a}_{ij}{x}_j\le b_i\text{for each }i}{\underbrace{Ax\le b}}.$$

Choose a feasible vector $x$ satisfying the linear inequalities; $c_j$ scores each unit of $x_j$. This is linear programming restricted to integer-valued variables.

Columns correspond to variables; rows correspond to constraints.

Decision Version

The decision version additionally receives a target $t\in \mathbb{Z}$ and asks

$$\exists x\in {\mathbb{Z}}^n:Ax\le b\wedge c^{\top }x\ge t.$$

Modelling Conventions

Both constraints and objective must be linear; terms such as $x_i{x}_j$ belong to the broader integer programming setting. Replace equalities by two opposing inequalities, and convert minimisation to maximisation by negating the objective.

Intuition

Constraints say allowed; the objective says best

During one ILP instance, $A$, $b$, and $c$ stay fixed while the solver chooses $x$:

$$\underset{\text{fixed input}}{\underbrace{A,b,c}}\underset{\text{chosen solution}}{\underbrace{x}}.$$

The two expressions answer different questions:

$$\begin{array}{rl}Ax\le b& \text{asks whether }x\text{ is allowed},\\ c^{\top }x& \text{measures how good }x\text{ is}.\end{array}$$

In the example below, $x$ and $y$ can represent quantities of two products. The constraints describe which production plans fit the available resources. Many plans may be feasible, so $c=(3,2)$ assigns profits of $3$ and $2$ per unit and tells the solver which feasible plan is best. Without $c$, the model could only ask whether some feasible plan exists. If only feasibility matters, one may set $c=0$.

Example

A two-variable ILP

Consider

$$\begin{array}{rl}\max & 3x+2y\\ \text{subject to}& x+y\le 4,\\ & x\le 2,\\ & x,y\in {\mathbb{Z}}_{\ge 0}.\end{array}$$

The optimal solution is $(x,y)=(2,2)$ with objective value $10$. Hence the decision version answers yes for target $t=10$ and no for target $t=11$.

Why the objective coefficients matter

Keep the same constraints. Both $(2,2)$ and $(0,4)$ are feasible, but changing $c$ reverses which one is better:

$$\begin{array}{rl}c=(3,2):& 10=3\cdot 2+2\cdot 2>3\cdot 0+2\cdot 4=8,\\ c=(1,4):& 16=1\cdot 0+4\cdot 4>1\cdot 2+4\cdot 2=10.\end{array}$$

Thus, $c=(3,2)$ selects $(2,2)$, whereas $c=(1,4)$ selects $(0,4)$. The feasible set has not changed; only the meaning of “best” has changed.