Graphical Integer Programming¶

Definition¶

Graphical integer programming solves a two-variable integer model by plotting its continuous constraints and considering only the lattice points satisfying all restrictions. Evaluate the objective at feasible integer points to identify the best value.

Interpretation¶

Graphical integer programming solves a two-variable integer problem by looking: draw the continuous feasible region as in the graphical method, mark the lattice points inside it, and find the best of those points. Unlike an LP, the best integer point need not be a corner of the continuous region.

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 cut out by $2x_1+2x_2\le9.5$ and $x_1\le3.5$ $3.5$ ; filled dots are the feasible lattice points and hollow dots are not. The orange lines are objective lines $3x_1+2x_2=z$ for $z=6$ $6$ , $9$ and $11$ . Moving the line outwards, the last one that still meets a filled dot is $z=11$ $11$ , at $(3,1)$ , a point inside the polygon rather than at a corner.

Only the lattice points count. The best integer point (ringed) need not be a corner of the continuous region: with the starting objective it lies on an edge, while in the static figure above it is an interior point.

Two habits from the LP case have to be dropped. Checking the corners is not enough: the best corner $(3.5,1.25)$ , with value $13$ , is not a lattice point, and rounding it to $(4,1)$ leaves the region. Instead, the objective is compared over the feasible lattice points, which is possible because a bounded two-variable region contains only finitely many of them.

The picture also shows why the LP relaxation gives a bound: the polygon contains every feasible lattice point, so its optimum $13$ is at least the integer optimum $11$ . With more variables there is no picture, and branch-and-bound replaces this comparison by a systematic search.

Key Results¶

Both coordinates must satisfy the stated integrality restrictions.
An LP-optimal fractional corner is not an integer-feasible decision.
For a small bounded example, explicit comparison of feasible lattice points proves optimality.

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 integer work-order model uses $3.2T+2.4S\le16$ and $2T+3S\le15$ $15$ .
Its best integer decision is $(T,S)=(0,5)$ $(0, 5)$ , with profit 750.

Prerequisites¶

Sources¶

OR Modelling · Week 3

Symbols: element of, integers

Last updated: 20 October 2026 03:02