Integer Linear Programming (ILP)

Integer linear programming (ILP) is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. It’s a special case of LP, where the solution space is the set of integers. ILPs are used in optimization, resource allocation, etc.

Formulation of an ILP

When both the objective function and constraints are linear, but the search space is restricted to the integers $\Z$, the optimization problem is said to be an ILP. The general form of an ILP is given as follows:

where $c \in \R^d$, $A \in \R^{m \times d}$, and $b \in \R^m$.

As an example, consider the knapsack problem, where the task is to pack a set of $N$ items with different weights and values into a sack with a limited capacity $C$ so that the total value of the packed items is maximized. The objective for the knapsack problem can be written as follows:

where $x_i \in \{0,1\}$ is a binary variable representing whether the $i^{th}$ item is selected or not, $v_i=\{1,5,10$ ...