Integer Programming Modelling

An airline cannot fly 0.4 of an aircraft on a route; a council cannot build 2.7 fire stations; a delivery firm either opens a depot or it does not — there is no half-open. The moment a decision is indivisible or yes/no, the smooth world of the linear program breaks down and we need integer programming (IP): optimisation where some or all variables are forced to be whole numbers, and very often just 0 or 1.

That single restriction does two things at once. It makes the problem far harder to solve — but it hands the modeller an astonishing new vocabulary. With binary variables you can write "on or off", "either this or that", "if we do A we must also do B", "pay a setup cost only if we produce at all" — logic that a plain LP simply cannot express. This page is about that modelling power.

Two kinds of integrality

Integer programs come in a spectrum. A pure integer program forces every variable to be a whole number (how many buses, how many machines). A mixed-integer program (MIP) lets some variables stay continuous while others are integer — the workhorse of industry. And the special, wildly useful case is the binary (or 0/1) program, where variables live in \{0, 1\} and encode a decision rather than a quantity:

x_j = \begin{cases} 1 & \text{if we choose option } j,\\ 0 & \text{otherwise.}\end{cases}

A binary variable is a switch. Everything below is a way of wiring those switches together with linear inequalities so that the arithmetic enforces the logic you mean.

The modelling toolkit of binary variables

These five patterns turn up again and again. Learn them and most real formulations become assembling familiar pieces.

On/off (indicator) link. Let continuous production x run only if switch y\in\{0,1\} is on: x \le M\,y. If y=0 then x=0; if y=1 the cap is the "big" constant M.
Fixed-charge (setup) cost. To pay a one-off cost f only when we produce, minimise f\,y + c\,x subject to x \le M\,y. Producing (x>0) forces y=1, so the fixed charge is unavoidable exactly when it should be.
Either/or constraints (big-M). To require constraint A or constraint B (not both needed), write a_1^\top x \le b_1 + M y and a_2^\top x \le b_2 + M(1-y). One of the two is always enforced; the binary y chooses which.
Logical implication. "If we choose A we must choose B" is simply x_A \le x_B. "Choose at most one of A, B, C" is x_A + x_B + x_C \le 1; "at least one" replaces \le with \ge.
Set covering / set packing. To cover every demand point i with at least one chosen facility, \sum_{j \text{ covers } i} x_j \ge 1 for all i (covering); replace by \le 1 to forbid overlap (packing).

The recurring character is the constant M — a number chosen big enough to make a constraint vanish when we want it to, but no bigger (an over-large M is a classic performance killer, which we flag below).

Worked example: choosing projects on a budget

A firm can invest in five projects. Each has a capital cost and a net present value (NPV). The capital budget is \pounds 12\text{M}. Two extra business rules apply: project D can only go ahead if B does (D depends on B's platform), and the firm will run at most one of the two competing products A and E.

Project	A	B	C	D	E
Cost (£M)	5	4	3	7	6
NPV (£M)	8	5	4	10	7

Let x_A,\dots,x_E \in \{0,1\} select each project. The whole decision becomes:

\max\; 8x_A + 5x_B + 4x_C + 10x_D + 7x_E

\text{s.t.}\quad 5x_A + 4x_B + 3x_C + 7x_D + 6x_E \le 12, \qquad x_D \le x_B, \qquad x_A + x_E \le 1.

Watch the pull of temptation: D has the biggest NPV (£10M), so grabbing it first feels right. But D drags in B (cost £11M together), leaving only £1M — nothing else fits — for a total NPV of just £15M. The optimal portfolio instead is A + B + C: cost 5+4+3 = 12 (exactly on budget), NPV 8+5+4 = \pounds 17\text{M}, and it obeys both side rules (x_D=0\le x_B, and only one of A/E). Chasing the single juiciest item lost £2M — a foretaste of why greedy choices fail on the knapsack problem.

Why integers are hard: the relaxation gap

Here lies the sting. Throw away the integrality requirement and you get the LP relaxation — an ordinary linear program you can solve instantly. It is tempting to solve that and round. The picture below shows why this is dangerous. The shaded region is the LP relaxation; the dots are the genuinely feasible integer points. The LP optimum sits at a fractional corner — and the true integer optimum is somewhere else entirely.

The LP relaxation peaks at (1,\,2.5) with value 6. Round the fraction up to (1,3) and you fall outside the feasible region — an impossible plan. Round down to (1,2) and you land on the integer optimum, value 5 — but only by luck; in higher dimensions the nearest integer point can be infeasible in every rounding direction, or feasible yet far from best. The gap between the relaxation's value and the integer optimum is the very thing that makes IP hard, and the quantity that branch and bound spends its life closing.

A continuous variable answers "how much?"; a binary variable answers "whether?" — and "whether" is where logic lives. Because y\in\{0,1\} can be multiplied into a linear inequality via a big-M, a switch can turn whole constraints on and off, couple distant decisions together, and encode "if–then" reasoning that no purely continuous model can. This is why integer programming quietly runs airline schedules, chip layouts, vaccine distribution and sports fixtures: almost every real plan is a tangle of yes/no choices, and 0/1 variables are the language that tangle is written in.

The single most common beginner error is to solve the LP relaxation, round to the nearest integers, and declare victory. It fails in two ways at once: the rounded point may be infeasible (it breaks a constraint the LP satisfied only with a fraction), and even when feasible it may be far from optimal. Worse, integer programming is genuinely in a harder complexity class — it is NP-hard, while LP is solvable in polynomial time. A related trap is choosing a needlessly huge M: it keeps the model correct but makes the LP relaxation floppy, the gap wide, and the solver crawl. Pick the smallest valid big-M you can justify.