Why is "whole numbers only" so expensive?
Integer programming (topic 04) is where the corner theorem stops being enough, and branch and bound (05) is the machinery that copes. Topic 19 shares this course's language of variables and constraints but drops the objective: sometimes the honest question is not “what's best” but “does anything work at all.” Topic 21 asks when the simplest rule of thumb is provably good enough, and topic 10 is what you reach for once exact methods die.
Add one word, "integer", and the ground gives way.
The reason is that convexity dies. The feasible region stops being a solid shape and becomes a scatter of isolated dots. There is no longer a sensible notion of sliding to a corner, because the dots are not corners of anything. Every guarantee from topic 02 evaporates at once.
It matters enormously in practice because whole numbers are what most real decisions are made of. You cannot dispatch 0.4 of a truck, open 2.7 of a warehouse, or assign 1.5 nurses to a ward. The moment a model touches the physical world it usually needs integers, and the moment it needs integers it becomes a fundamentally harder problem than the one it looks like.
The continuous answer is not useless, though, and this is the key insight the next topic is built on. It is a bound. Whatever the integer answer is, it cannot be better than the continuous one, because the integer problem is the continuous problem with extra restrictions. That single observation is what makes integer programming solvable at all.
An integer linear program is a linear program plus an integrality requirement:
maximise cᵀx
s.t. Ax ≤ b , x ≥ 0 , x ∈ ℤⁿ
Dropping the last condition gives the LP relaxation, whose optimum z_LP satisfies z_IP ≤ z_LP for a maximisation. The difference is the integrality gap, 1.0 in the figure above, since 21 − 20 = 1.
Complexity. Integer programming is NP-hard; 0–1 integer programming is one of Karp's original 21 NP-complete problems (Karp, 1972). Unless P = NP there is no polynomial algorithm. This is not a statement about current technology. It is a statement about the problem.
What makes real instances tractable anyway is that some integer programs are secretly easy. If the constraint matrix is totally unimodular (every square submatrix has determinant 0, +1 or −1) then the LP relaxation's vertices are already integral, and you get the integer answer for free from a polynomial-time solve. Network flow and bipartite matching (topics 06 and 07) are exactly this case, which is why they are the two corners of combinatorial optimisation that behave beautifully.
Most integer programs that show up in practice are one of three named shapes, distinguished by what the constraint means, not what it looks like:
COVERING PACKING PARTITIONING
Σ x_j ≥ 1 per i Σ x_j ≤ 1 per i Σ x_j = 1 per i
"cover everything" "never overlap" "split exactly"
Covering. Every requirement met by at least one chosen item, e.g. crew scheduling: every flight covered by some crew. Packing: chosen items never conflict, e.g. selecting non-overlapping intervals, or an independent set in a graph. Partitioning. Every element assigned to exactly one group, e.g. districting, or splitting a workforce into non-overlapping shifts. The three differ by one inequality sign, and almost every scheduling, routing or districting problem you meet is a covering, packing or partitioning problem wearing a domain-specific name.
Where to put the warehouses The facility-location problem: given demand across a country and a set of candidate sites, decide which sites to open and which customers each serves, trading a fixed cost per open site against transport cost. The open/closed decision is inherently binary (half a warehouse serves nobody) so this is integer by nature, not by choice. The same structure decides mobile-tower placement, hospital catchments, and where a delivery company puts its depots. Instances with thousands of candidate sites are solved routinely today; the same instances were hopeless in 1990, and the improvement came far more from better algorithms than from faster machines.
Check yourself
Why can you not just round the LP solution (3, 1.5) to get the best whole-number plan?
The continuous optimum is worth 21; the best whole plan is worth 20. The LP value is an upper bound for a maximisation, which is exactly what makes branch and bound possible.