Integer Programs

An integer program is a linear program with some variables restricted to whole numbers. The restriction looks small and changes everything: the feasible set becomes a scatter of isolated points rather than a polyhedron, its optimum need not sit at a corner, and the geometric account that makes the simplex method work no longer applies.

Definition

An integer linear program has the form

min c^{T} x subject to A x \leq b, x \geq 0, x_{j} \in Z for j \in I,

where $I$ indexes the variables required to take whole-number values.

Three cases by which variables are restricted. When $I$ is every variable the program is a pure integer program. When $I$ is a proper non-empty subset it is a mixed-integer program. When the integer variables additionally carry bounds $0 \leq x_{j} \leq 1$ they are binary, and a program of only such variables is a binary program.

The feasible set. Dropping integrality leaves a polyhedron. Imposing it keeps only the points of that polyhedron with whole-number coordinates in the restricted positions. The result is generally not convex, not connected, and has no interior: it is a scatter of isolated points.

What stops being true. The objective no longer attains its optimum at a vertex of the polyhedron, because the optimal point is usually not a vertex at all. Convexity arguments do not apply. Moving between neighbouring feasible points is not a local operation with a direction. The simplex method solves the wrong problem.

What remains true. The objective is still linear, the constraints are still linear, and feasibility is still decided by substitution. An integer program with bounded variables has finitely many feasible points, so an optimum exists whenever any feasible point does.

Formal statement

$min {c^{T} x : A x \leq b, x \geq 0, x_{j} \in Z (j \in I)}$ . Pure integer: $I = {1, \dots, n}$ . Mixed-integer: $\emptyset ⊊ I ⊊ {1, \dots, n}$ . Binary: $x_{j} \in {0, 1}$ for $j \in I$ . Feasible set $= P \cap (Z^{I} \times R^{n - | I |})$ where $P$ is the polyhedron.

Assumptions and scope

Integrality is a restriction on the variables, stated in the program. It is not a property of the answer to be arranged afterwards, and a program whose integrality lives only in the modeller's intention is a linear program.
The feasible set of an integer program is generally non-convex and has no interior, so convexity arguments and the vertex characterisation of optima do not apply to it.
An integer program with bounded variables has finitely many feasible points, so if one is feasible an optimum exists. Unbounded integer variables can still produce an unbounded program.
Requiring integrality of a variable that is genuinely divisible costs computation and buys nothing. Tonnes of flour do not need to be whole numbers.
Integer programs are computationally much harder than linear ones of the same size. The difficulty is intrinsic to the restriction rather than a deficiency of current solvers.

Worked material

Example

The same constraints, with and without integrality

Take

max x_{1} + x_{2} subject to 2 x_{1} + 3 x_{2} \leq 12, 3 x_{1} + x_{2} \leq 9, x_{1}, x_{2} \geq 0 .

As a linear program. The binding constraints meet where $2 x_{1} + 3 x_{2} = 12$ and $3 x_{1} + x_{2} = 9$ . From the second, $x_{2} = 9 - 3 x_{1}$ ; substituting, $2 x_{1} + 27 - 9 x_{1} = 12$ , so $- 7 x_{1} = - 15$ and $x_{1} = 15 / 7$ , giving $x_{2} = 9 - 45 / 7 = 18 / 7$ . The optimum is $(15 / 7, 18 / 7) \approx (2.14, 2.57)$ with value $33 / 7 \approx 4.71$ , at a vertex.

Now require $x_{1}, x_{2} \in Z$ . The feasible points are the whole-number pairs inside the region. Checking those with the largest sums: $(2, 2)$ gives $4 + 6 = 10 \leq 12$ and $6 + 2 = 8 \leq 9$ , feasible, value $4$ . $(3, 0)$ gives $6 \leq 12$ and $9 \leq 9$ , feasible, value $3$ . $(0, 4)$ gives $12 \leq 12$ and $4 \leq 9$ , feasible, value $4$ . $(1, 3)$ gives $2 + 9 = 11 \leq 12$ and $3 + 3 = 6 \leq 9$ , feasible, value $4$ .

The integer optimum is $4$ , attained at $(2, 2)$ , $(1, 3)$ and $(0, 4)$ .

What to notice. The continuous optimum was $4.71$ at a vertex; the integer optimum is $4$ and is attained at three points, none of them a vertex of the polygon. The value fell, the location moved, and the vertex account gave no guidance at all.

Non-example

When integrality is not what is needed

Not an integer program: a divisible quantity that happened to come out whole. A blending model returns exactly $40$ kg of an ingredient. Nothing about kilograms is indivisible, and adding $x \in Z$ to enforce what the arithmetic produced anyway makes the program dramatically harder and can exclude a better fractional plan.

Not an integer restriction: a bound. $x \leq 5$ restricts the size of a quantity, not its divisibility. $x = 4.3$ satisfies it. Bounds and integrality are independent, and a variable can carry either, both, or neither.

Not binary: a general integer variable. Hiring vans is indivisible but not a yes-or-no choice; $v = 3$ is meaningful. Writing $v \in {0, 1}$ forbids hiring more than one van, which is a restriction the situation never stated.

Not a repair: rounding the continuous answer. Rounding $(2.14, 2.57)$ to $(2, 3)$ in the earlier example gives $4 + 9 = 13 > 12$ , infeasible. Rounding down to $(2, 2)$ is feasible and optimal there, but that is luck rather than method, and the unit on relaxation shows cases where rounding is feasible and far from optimal.

Not an integer program: a linear program the modeller intends to round. If integrality is not written into the program it is not part of the problem, whatever anyone plans to do with the output. The solver optimises what it is given.

Contrast

Why rounding a relaxed solution fails

The most common account of integer programming is that you solve the linear program and round. It is wrong in two separate ways, shown concretely below.

Rounding can be infeasible. In the example above the continuous optimum is $(15 / 7, 18 / 7) \approx (2.14, 2.57)$ . Round to nearest, giving $(2, 3)$ , and check the first constraint: $2 (2) + 3 (3) = 13 > 12$ . The plan violates a constraint outright. Rounding moved the point off the region, and nothing in the rounding step could notice.

Rounding can be feasible and wrong. Consider

max x_{1} + 10 x_{2} subject to 10 x_{1} + 11 x_{2} \leq 21, x_{1}, x_{2} \geq 0, x_{1}, x_{2} \in Z .

The relaxation pushes everything into $x_{2}$ : $x_{2} = 21 / 11 \approx 1.909$ , $x_{1} = 0$ , value $\approx 19.09$ . Round down to $(0, 1)$ , which is feasible, value $10$ . But $(1, 1)$ satisfies $10 + 11 = 21 \leq 21$ and has value $11$ , which is better. The rounded answer was feasible, plausible, and not optimal, and no amount of care in the rounding would have found the improvement, because it required increasing a variable the relaxation had set to zero.

Why this keeps happening. The continuous and integer optima are answers to different questions. The constraints binding at one need not bind at the other, so there is no reason the integer optimum should be near the fractional one. In larger problems they can be far apart.

What the relaxation is actually for. Not the answer. A bound, and a starting point for methods that search properly. That is the subject of its own unit, and the distinction between a bound and an answer is the thing to carry there.

Common errors

Common misconception

An integer program is solved by solving the linear program and rounding the answer to whole numbers, so integrality is a finishing step rather than part of the problem.

Integer Programs

Assumptions and scope

Worked material

The same constraints, with and without integrality

When integrality is not what is needed

Why rounding a relaxed solution fails

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history