Integer Programming: Introduction, Methods, Examples

Integer programming is linear programming with one extra rule: some or all decision variables must take whole-number values. The objective and constraints stay linear, but fractional answers are forbidden. You cannot produce 2.7 buses or hire 4.3 workers, so the mathematics must respect whole units.

This matters because rounding a normal linear programming solution is often wrong: the rounded point can violate a constraint, or a different integer point can be better. Integer programming models the discrete choices of real business and needs its own solution methods.

Key Concepts

• Pure integer program: every variable must be an integer. Mixed integer program (MIP): only some variables must be integers.
• Binary (0-1) variables: restricted to 0 or 1, modelling yes-or-no decisions such as opening a facility or accepting a project.
• LP relaxation: the same problem with the integrality rule dropped. For maximization, its optimum is always an upper bound on the integer optimum.
• Integrality gap: the difference between the LP relaxation value and the true integer optimum; a large gap means rounding is dangerous.
• Branch and bound: the standard solution method: solve LP relaxations, then split (branch) on a fractional variable until all branches are resolved or pruned.

Formulas

Standard form, maximize c^T x subject to Ax ≤ b, x ≥ 0, x ∈ Z^n, where Z^n means every component is an integer. A binary variable adds x_j ∈ {0, 1}. The LP relaxation replaces x ∈ Z^n with x ∈ R^n. These models assume linear relationships and known coefficients.

Worked Example

Maximize 3x + 4y subject to x + 2y ≤ 8, 2x + y ≤ 8, x, y ≥ 0 integers. First the LP relaxation: both constraints bind, so x + 2y = 8 and 2x + y = 8 give x = y = 8/3 ≈ 2.67, with objective 56/3 ≈ 18.67, an upper bound on any integer answer. Now check feasible integer points. With y = 3: x ≤ 2, giving (2, 3) with value 3(2) + 4(3) = 18. With y = 2: x ≤ 3, giving (3, 2) with value 17. With y = 4: x ≤ 0, giving 16. The integer optimum is (2, 3) with value 18. Rounding the LP point (2.67, 2.67) to (3, 3) violates x + 2y ≤ 8, and the nearest feasible rounded point (3, 2) gives only 17. Rounding fails; exact methods are needed.

Common Misconceptions

• Rounding the LP solution is good enough. The rounded point can be infeasible or strictly worse than the true integer optimum, as shown above.
• Integer programming is as easy as linear programming. LP is solvable in polynomial time, but integer programming is NP-hard: solution time can explode, which is why branch-and-bound and cutting planes exist.
• Only large items need integer variables. Even tiny yes-or-no decisions need binary variables; the discreteness of the choice, not its size, forces integrality.

Real-World Applications

Integer programming schedules airline crews, routes delivery vehicles, selects capital projects under a budget, decides warehouse locations, assigns machines to jobs, and designs telecommunication networks. Wherever a decision is indivisible, an integer or binary variable models it exactly.

Integer programming extends linear programming to discrete decisions, uses LP relaxations to bound the answer, and relies on branch-and-bound because rounding is unreliable and the problem is genuinely hard.