The formula
The general mixed-integer linear program (MILP) is stated like this:
minimize c·x
subject to A·x ≤ b
x ≥ 0
x_j integer for j in some set I
Reading: pick the vector of decisions x that makes the cost c·x as small as possible, while satisfying every linear constraint in A·x ≤ b, and forcing the variables in set I to land on whole numbers. Drop the integer requirement and you have an ordinary linear program (LP) — easy. Keep it, and the problem becomes one of the hardest things a computer routinely solves.
The binary special case is where most engineering lives:
x_j ∈ {0, 1}
Reading: each decision is a yes/no switch. Run this cable or don't. Assign this tech to that stand or not. Fly this sortie or skip it.
The bound that governs everything — the branch-and-bound relaxation:
LP-relaxation(P) ≤ integer-optimum(P) (for a minimization)
Reading: solve the easy fractional version first. Its answer is a floor you can never beat with whole numbers, so it tells you how much room is left to search — and when to stop.
Where you meet it
Test-stand scheduling at Redstone. Twelve articles need environmental, vibration, and EMI runs across three chambers over two weeks, each with setup times, crew availability, and a fixed delivery date. The decision "does article A go in chamber 2 during slot 5" is a 0/1 variable. Minimize total span or lateness, and you have written a scheduling MILP whether you called it that or not.
Cable and harness routing. Picking which of a finite set of raceways and connector positions to use, minimizing wire length or weight while respecting separation rules between power and signal lines. Discrete choices, hard constraints, an objective — the exact shape of an integer program.
Sensor and instrument placement on a review board. You have forty candidate accelerometer locations and budget for twelve channels. Which twelve maximize modal coverage without redundant placements? That is a binary selection problem, and the board will argue about it whether or not anyone writes down the cost vector.
Vehicle and logistics routing. A tech van servicing sites across the Tennessee Valley, or a drone visiting a set of survey points and returning to base. That is the traveling salesman problem, the canonical combinatorial optimization, and it hides inside more delivery, inspection, and coverage tasks than people expect.
How it works
The trouble is counting. A continuous problem has infinitely many points but a smooth landscape you can slide downhill on. A combinatorial problem has a finite number of answers — and that is exactly what makes it brutal, because "finite" here means numbers that stop meaning anything.
Take the traveling salesman. For n stops the number of distinct round-trip tours is (n − 1)! / 2. Ten stops gives 181,440 tours — a laptop chews through those instantly. Fifteen stops gives 43,589,145,600, about 4.4 × 10¹⁰. Twenty stops gives 6.08 × 10¹⁶, sixty quadrillion. Check a billion tours a second and twenty stops still takes over two years of brute force. A knapsack-style yes/no problem with 50 items has 2⁵⁰ ≈ 1.13 × 10¹⁵ subsets; at 100 items it is 1.27 × 10³⁰. You cannot enumerate your way out. This is what people mean when they say these problems are NP-hard: nobody knows a method that stays fast as the problem grows, and there is good reason to believe none exists.
So you don't enumerate. Branch and bound is the trick that makes it tractable most of the time. Solve the LP relaxation — the easy fractional version. If it happens to come out whole, you are done; that is provably the best integer answer. Usually it doesn't. Some variable comes back at 3.4. So you branch: create two subproblems, one forcing that variable ≤ 3, one forcing it ≥ 4, and solve each relaxation. Every relaxation gives a bound. The moment a branch's relaxed cost is already worse than the best whole answer you have found so far, you prune the entire branch without exploring it — thousands of solutions eliminated by one comparison. Cutting planes sharpen the same idea: add extra linear constraints that slice off fractional garbage without removing any valid integer point, tightening the relaxation so the bounds bite harder. Modern solvers run both together — branch-and-cut — and that combination is why a problem that looks like it needs geologic time can solve in seconds.
The gotchas are real and they bite working engineers:
The relaxation lies about feasibility, not just optimality. An LP will happily hand you 3.4 test stands. Rounding it is not a solution — 3.4 rounded to 3 may violate a constraint you thought was satisfied, and rounded to 4 may blow the budget. The integer answer can sit far from the rounded fractional one.
Solve time is wildly unpredictable. Two instances of identical size can differ by orders of magnitude in runtime. A model that solved in a second last week can hang for an hour after you add one constraint. Formulation matters more than raw size — a tight formulation with good bounds beats a loose one every time.
The most common mistake is forcing everything to be integer. Most variables in a mixed model should stay continuous; only the genuinely indivisible decisions need the integer flag. Every unnecessary integer variable multiplies the search tree. Engineers new to this reflexively integer-ize quantities that were fine as fractions and then wonder why the solver never returns.
"Optimal" is only optimal for the model you wrote. The solver honors your constraints and your objective exactly. If you left out crew fatigue, or your cost vector doesn't match what the program actually cares about, you get a perfect answer to the wrong question. The math is never the weak link; the modeling is.
Where it stops working: when the model is genuinely huge and tight formulations don't exist, exact solvers give up and you fall back to heuristics — greedy rules, local search, simulated annealing — that find good answers fast with no guarantee they are best. For a lot of real scheduling and routing, "provably within 2% of optimal" delivered this afternoon beats "provably optimal" delivered never.
History
The story starts with a hard problem nobody could crack. In 1954 George Dantzig — the man who had already given the world the simplex method for linear programming — teamed with Ray Fulkerson and Selmer Johnson at RAND and did something that looked impossible: they solved a 49-city traveling salesman problem to guaranteed optimality [1]. Their weapon was the cutting plane: start with the easy relaxation, then hand-add linear constraints that carved off the illegal fractional solutions until the answer came out as a real tour. It took only 26 such cuts. But the cuts were built by hand and human insight; there was no algorithm behind them yet [1].
The next move split into two directions at the turn of the decade. In 1958 Ralph Gomory found the missing algorithm — a systematic, finite procedure for generating cutting planes for any pure integer program, published in the Bulletin of the American Mathematical Society, and he coded it in the brand-new FORTRAN language that same summer [2]. Two years later, in 1960, Ailsa Land and Alison Doig — working at the London School of Economics — published "An Automatic Method of Solving Discrete Programming Problems" in Econometrica, and it laid out branch and bound: the systematic tree of relaxations and prunings that, over sixty-five years later, is still the backbone of essentially every general-purpose integer solver [3][4]. Their paper deliberately used nothing beyond ordinary linear programming so it could run on the automatic computers of the day [3]. R. J. Dakin tightened the branching scheme in 1965 [5], and the branch-and-cut framework that fuses Land-Doig branching with Gomory-style cuts came together decades later, notably in the large-scale TSP work of Padberg and Rinaldi around 1991 [2].
Land and Doig's contribution went underappreciated for a long time — two women publishing the foundational algorithm of an entire computational field in 1960, whose method quietly runs inside every commercial optimizer shipping today.
Sources
- https://www.math.uwaterloo.ca/~bico/papers/dfj_mathprog.pdf
- https://ems.press/content/book-chapter-files/27365
- https://www.econometricsociety.org/publications/econometrica/1960/07/01/automatic-method-solving-discrete-programming-problems
- https://onlinelibrary.wiley.com/doi/10.1111/anzs.12439
- R. J. Dakin, "A tree-search algorithm for mixed integer programming problems," The Computer Journal 8(3):250-255 (1965). https://doi.org/10.1093/comjnl/8.3.250