Quantitative Methods

Integer Programming and Why Scheduling Is Hard

When the answer has to be a whole number of crews, depots, or trucks, the geometry changes and rounding stops working. Learn what the optimality gap on your solver output means, and when to stop the run.

  • Advanced
  • 12 min total
  • 14 chapters

What decision this helps you make: Whether to accept the schedule or plan your solver found after two hours at a 1.6% gap, or keep paying for compute, and whether the fractional plan you were about to round is worth anything at all.

What this topic is

Integer programming is linear programming with the added requirement that some or all of the decision variables must be whole numbers, usually zero or one. That single addition is what lets a model say "open this depot or do not", "assign this crew to that pairing", or "run this shift". It also removes the geometric property that made linear programming fast, which is why an integer model can take hours where its linear relaxation takes milliseconds.

Why it matters

Almost every real operational decision is discrete. You cannot hire 4.3 nurses, open 0.6 of a distribution centre, or dispatch two thirds of a truck. Businesses handle this by solving a continuous model and rounding, which produces plans that are often infeasible and reliably leave money on the table. Understanding integer programming tells you when rounding is safe, what number to demand from whoever runs the solver, and how to read a result that is honestly labelled "within 1.6% of the best possible".

Who should learn it

Anyone who schedules people, sites facilities, plans routes, allocates capital across indivisible projects, or buys optimisation software and needs to evaluate what it is telling them.

What you will understand

  • Why the linear relaxation gives a bound, and why rounding its answer is neither optimal nor necessarily feasible
  • What branch and bound is doing, and what the MIP gap between incumbent and bound actually measures
  • How binary variables encode logic: either-or, if-then, fixed charges, and counting rules
  • Why scheduling in particular is hard, and what makes a formulation solve in seconds instead of hours

Prerequisites

Common misconception

"NP-hard means the problem cannot be solved, so we use a heuristic." Both halves are wrong in a way that costs money. NP-hardness is a worst-case statement about how solution time scales as instances grow; it says nothing about the instance on your desk. Commercial branch-and-cut solvers routinely prove optimality on scheduling and facility-location models with hundreds of thousands of binary variables. Meanwhile the heuristic you chose instead returns a plan with no bound attached, so you cannot tell whether it is 1% or 40% away from the best possible. The exact method usually gives you a worse-sounding answer and a much better-informed decision.