Integer Linear Programming¶

Definition¶

An integer linear program (ILP) is a linear optimization model in which some or all decision variables must take integer values. The linear objective and functional constraints are retained, with restrictions such as $x_j\in\mathbb{Z}$ added to the specified variables.

Interpretation¶

An integer linear program is an LP with the extra requirement that some variables take whole-number values. Integrality represents indivisible decisions, such as numbers of buses, and also allows yes-or-no choices and logical conditions to be modelled. It changes the feasible set and can make the problem substantially harder to solve.

$A feasible polygon with its integer points as dots, the LP optimum at a fractional corner with value 13, and the integer optimum (3, 1) with value 11.$

The dashed polygon is the feasible region of the LP; once both variables must be integers, only the dots are feasible. The LP optimum $(3.5,1.25)$ with $z=13$ is not a dot, and the best dot is $(3,1)$ with $z=11$ $11$ . This point lies strictly inside the polygon, so the optimum of an integer program need not be a corner point of the LP region.

Change the objective and compare the LP optimum with the best feasible lattice point.

Dropping the integrality requirement gives a relaxation: it allows more points, so for maximization its optimum is an upper bound on the integer optimum, $11\le13$ here, as in the optimization bounds. Rounding the LP optimum is no reliable shortcut: rounding $(3.5,1.25)$ to $(4,1)$ violates $x_1\le3.5$ $3.5$ , and in other problems a rounded point can be feasible but not optimal.

The bus scheduling model and the project selection model are integer programs of this kind. An exact method for them, branch-and-bound, works with a sequence of such relaxations.

Key Results¶

Pure integer programs require all decision variables to be integer.
Mixed integer programs include both integer and continuous variables.
Binary integer programs restrict every decision variable to 0 or 1.
Rounding an LP solution need not preserve feasibility or optimality.

Examples¶

The figure uses the illustrative objective $3x_1+2x_2$ and restrictions $2x_1+2x_2\le9.5$ $9.5$ , $x_1\le3.5$ $3.5$ , $x\ge0$ $0$ . Its continuous optimum $(3.5,1.25)$ has value 13, whereas requiring both variables to be integers gives $(3,1)$ with value 11. Branch-and-bound on LP relaxations is an exact method; arbitrary rounding is not.

A bus count must be a nonnegative integer.
A warehouse-opening decision uses a binary variable.

Prerequisites¶

Linear Programming

Sources¶

OR Modelling · Week 2

Aliases: ILP, integer programming, Integer program, IP, integer optimization, integer linear optimization, integer linear program Symbols: element of, integers

Last updated: 20 October 2026 03:02