Pure Integer Program¶

Definition¶

A pure integer program is an integer linear program in which every decision variable is restricted to integer values. Nonnegativity, upper bounds, and other restrictions remain separate model constraints.

Interpretation¶

A pure integer program fits decisions that are counts, such as numbers of buses or workers, where a fractional answer has no meaning. Its feasible solutions are then only the points with integer coordinates inside the region of the constraints.

A feasible polygon with the integer points inside it filled and those outside hollow, three parallel objective lines, and the best integer point (3, 1) with value 11 marked.

The shaded polygon is that region without integrality; the filled dots are the integer points in it. Moving the objective line $3x_1+2x_2=z$ outwards, the last filled dot it reaches is $(3,1)$ with $z=11$ $11$ , while the best point of the polygon is the corner $(3.5,1.25)$ with $z=13$ $13$ .

"Pure" only says that every variable is integer-restricted; nonnegativity and upper bounds remain separate constraints. The best integer point need not be a corner of the polygon, and rounding $(3.5,1.25)$ to $(4,1)$ violates $x_1\le3.5$ $3.5$ , so integer programs need their own methods, such as branch-and-bound.

Key Results¶

All $n$ decision variables are integer-restricted, whereas a mixed integer program restricts only some of them.
Binary integer programs are a special case with the additional bounds 0 and 1.
Dropping integrality gives its LP relaxation.

Examples¶

The figure uses the illustrative model $\max(3x_1+2x_2)$ subject to $2x_1+2x_2\le9.5$ $9.5$ , $x_1\le3.5$ and $\boldsymbol{x}\in\mathbb{Z}_{\ge0}^2$ $Z_{\geq 0}^{2}$ . Its best lattice point is $(3,1)$ with value 11; it is not a corner of the continuous polygon.

The bus-scheduling model counts buses beginning each shift.
The integer work-order model counts tow bars and stabilizer bars.

Prerequisites¶

Integer Linear Programming

Sources¶

OR Modelling · Week 2

Aliases: pure integer programming, all-integer program, pure IP Symbols: element of, integers

Last updated: 20 October 2026 03:02