Integer programming

Add “and the variables must be whole numbers” to linear-programming and everything changes. T2 — Wikipedia as a tertiary survey, per this spoke’s existing practice.

Integer programming restricts “some or all of the variables … to be integers”; with a linear objective and constraints it is ILP, and mixed-integer programming (MIP) when only some variables are integral. It is NP-complete — 0–1 ILP is one of Karp’s 21 — while its continuous relaxation is polynomial. The gap between those two facts is the entire subject.

How it is actually solved

• LP relaxation: drop integrality, solve the LP, and you have a bound. Rounding the answer usually gives something infeasible or bad, but the bound is what everything else is built on.
• Branch and bound: split on a fractional variable, recurse, prune any branch whose relaxation bound cannot beat the incumbent. It can stop early with “a feasible, although not necessarily optimal, solution” plus a measured gap to optimality.
• Cutting planes: add constraints that “drive the solution towards being integer without excluding any integer feasible points.”
• Branch and cut: both together, which is what every serious solver runs.
• Total unimodularity: when the constraint matrix is totally unimodular with integer coefficients, “the solution returned by the simplex algorithm is guaranteed to be integral” — the integrality comes free, which is why network-flow problems are easy.

Where it sits against this spoke’s centre of gravity

This is the discipline’s answer to a combinatorial problem, and it is the opposite of the metaheuristic answer. A genetic-algorithm or tabu-search run on a scheduling problem returns a good solution and no idea how good. Branch and bound on the same problem returns a solution and a bound, so you know you are within x% of optimal, or you learn that the instance is out of reach. Both approaches face NP-hardness; only one of them tells you what it cost you.

That is the trade to keep in mind whenever a paper here reports a metaheuristic beating another on a scheduling or routing benchmark: the relevant baseline is often a MIP solver given the same time budget, and this corpus has never seen that comparison. The solver side’s own measured reality is on miplib and mittelmann-benchmarks — including how many instances remain open.

Applications named: production planning, scheduling, districting, telecommunications network design, cellular frequency planning, energy systems.