When the Answer Is Yes or No

TL;DR

• A continuous variable may take fractional values; an integer variable must be a whole number; a binary variable is the special yes-or-no case, 0 or 1. A mixed-integer program contains both discrete and continuous decisions.
• Removing the integrality restrictions produces an LP relaxation. It is easier to solve and contains every integer-feasible solution, so its value gives a valid bound. Its fractional answer need not be usable.
• Naïve coordinate-wise rounding is not a general solution method. It can violate a constraint, and repairing the rounded point can lead somewhere far from the true integer optimum.
• Branch-and-bound solves LP relaxations inside smaller and smaller regions. For a maximisation problem, once an integer-feasible incumbent exists, it maintains a certified interval L ≤ z^* ≤ U. The interval's width is the unresolved proof.
• Integrality does not make global optimality unprovable. Modern branch-and-cut solvers combine bounds, branching, cutting planes, presolve and heuristics until the gap meets a stated tolerance. If a time limit is reached first, they report any incumbent found and the best available bound.

The first article used George Stigler's diet to explain a linear-programming certificate: a feasible basket and a set of feasible nutrient prices met at the same cost. The second opened the optimiser and followed its rows, columns, bases and linear systems. Both lived in a continuous world. If $10.00 spent on flour is allowed, then so is $10.01.

Many decisions do not behave that way. A distribution centre is open or closed. A vehicle takes a route or it does not. A metabolic reaction is permitted in a candidate network or it is not. A portfolio may hold at most twenty names, even though the weight placed in any one of those names remains continuous. Writing 0.4 instead of 0 or 1 may help an algorithm reason, but it does not open forty per cent of a warehouse.

That distinction creates a new class of model. A continuous variable can take any value in an interval. An integer variable is restricted to whole numbers. A binary variable is an integer variable restricted to 0 or 1. If all variables are integral, the model is an integer linear program. If some remain continuous, it is a mixed-integer linear program, or MILP.

Yes-or-no decisions gave this piece its title, but counts draw better pictures, so the worked example below uses two general integer variables rather than two binaries. Binary models can exhibit the same rounding obstruction, although simply restricting this particular example to 0 or 1 would make its relaxed optimum integral.

Four answers to one small problem

Consider this deliberately small problem from Stephen Bradley, Arnoldo Hax and Thomas Magnanti's Applied Mathematical Programming.[1]

The variables are counts of two unnamed choices. Each unit of the first contributes 5 to the objective; each unit of the second contributes 8. The two inequalities are resource limits. The abstraction pays off on paper. Every feasible answer is a point in the plane, and every integer-feasible answer sits where two grid lines cross.

Erase only the word integer. The resulting LP relaxation keeps the same objective and resource limits but fills in every fractional point between the feasible lattice points. Because the relaxation removes a restriction, it cannot exclude any feasible integer point. For this maximisation problem its optimum is therefore at least as high as the integer optimum. It is an upper bound, not necessarily an admissible answer.

The relaxed optimum occurs where the two sloping boundaries meet:

Neither coordinate is allowed in the integer model. Rounding both to the nearest whole number gives (2, 4). The first constraint is exactly met, but the second becomes 5(2) + 9(4) = 46. Its limit is 45. The rounded point is not slightly suboptimal; it is infeasible.

Moving to the nearest feasible lattice point in Euclidean distance does not rescue the idea. The point (2, 3) is feasible and has value 34. The actual integer optimum is (0, 5), with value 40. It is farther from the relaxed solution in the plane and much better in the objective. The source goes further: by rescaling this construction, the integer optimum can be placed arbitrarily far from the rounded LP point in distance or objective value.[1]

There are 25 feasible lattice points here, so exhaustive checking is easy. That is a property of the illustration, not of integer programming. With one hundred binary decisions there are 2¹⁰⁰ possible yes-or-no assignments before the constraints eliminate any. LP-based MILP solvers rely on relaxations because exhaustive enumeration stops being a plan.

The LP bound exceeds the integer optimum by 1.25 objective units. That difference is this formulation's absolute root-relaxation gap. Be careful with the name: other authors write integrality gap for a ratio rather than a difference, and for the worst case over a whole family of instances rather than one model, so the convention has to be declared before the number means anything.

It is also a different quantity from the primal–dual gap of the first two articles. The LP relaxation can close its own primal–dual gap completely and still sit above the best integer answer, because the point where it closes is fractional.

The size of the root gap matters because a tight relaxation lets the solver throw away branches early, while a loose one leaves more territory to disprove. It describes the formulation the modeller wrote, not the speed of the solver that reads it.

A tree made of valid promises

Branch-and-bound turns the fractional answer into a search without surrendering the proof. Ailsa Land and Alison Doig published the LP-based enumeration method now recognised as branch-and-bound in 1960.[2] Its logic is four verbs.

1. Relax. Solve an LP whose feasible set still contains every integer answer the current region allows.
2. Branch. Choose a variable that is fractional in the LP answer and split the region into cases that exclude that fractional value.
3. Bound. Use each child relaxation to limit how good any integer answer inside that child could be.
4. Fathom. Stop exploring a child if its relaxation is infeasible, already integer, or unable to beat the best integer solution found so far.

At the root of our example, x₂ = 3.75. Every integer solution must satisfy either x₂ ≤ 3 or x₂ ≥ 4, so those two children cover every admissible answer while excluding the fractional root point.

Solve both root children. The case x₂ ≤ 3 reaches the integer point (3, 3), worth 39. It becomes the first incumbent. The case x₂ ≥ 4 gives (1.8, 4) and the larger upper bound, 41, so pursue that branch. Split it on x₁. The case x₁ ≥ 2 is infeasible. The case x₁ ≤ 1 gives another fractional point, (1, 40/9), worth 365/9 ≈ 40.56, and is split once more. One child produces (1, 4), worth 37; it is feasible but cannot improve the incumbent.

An incumbent is the best integer-feasible point encountered so far. For a maximisation problem its objective value is a lower bound L on the unknown optimum z^*. The largest valid raw LP bound attached to an unresolved node supplies an upper bound U. A newly created node may initially inherit its parent's bound; solving its own relaxation can tighten it. Once an incumbent exists, the algorithm has a certified interval:

After the two root children are solved, the certificate reads 39 ≤ z^* ≤ 41. Solving the next pair lowers the raw LP upper bound to 365/9, so the displayed interval becomes 39 ≤ z^* ≤ 365/9. Because every integer-feasible objective value here is integral, flooring that bound gives the stronger valid statement 39 ≤ z^* ≤ 40; the figure retains the raw fraction to show what the LP relaxation itself supplied. The last unresolved child produces (0, 5), worth 40, and nothing else is still open: one sibling was infeasible, the other two returned integer answers the tree could not improve on. With no region left to supply a higher bound, the interval closes at 40 = z^* = 40. The point (0, 5) is proven optimal without testing the other feasible integer points one by one.

The word gap now has a third meaning. A live optimality gap is the distance between the incumbent bound and the best remaining global bound. It measures unfinished proof. Before the first incumbent exists, the solver may have a relaxation bound but no implementable endpoint on the other side. For minimisation the directions reverse: a feasible incumbent gives the upper bound and relaxations give lower bounds. Solver interfaces also normalise relative gaps differently, so the safest statement is always the interval in objective units.[3]

Stopping early can therefore produce something more informative than “the best answer found.” After the root children, the solver can return (3, 3), worth 39, together with the certificate 39 ≤ z^* ≤ 41. After the next branch, the incumbent is unchanged but the raw LP ceiling has fallen to 365/9. When (0, 5) is found, the interval closes at 40. Subject to the solver's numerical tolerances, optimality is then certified.

So integrality did not destroy the proof. It broke it into pieces. The LP certificate still appears in full at every single node, and the tree is the structure that assembles those local guarantees into one global claim.

Branch-and-cut, not the textbook tree alone

The hand-built tree isolates one idea. A modern MILP solver also simplifies the formulation in presolve, searches for feasible incumbents with heuristics, exploits symmetry and special constraint structure, and adds valid inequalities called cuts. Combining those cuts with branch-and-bound gives branch-and-cut.[3]

A cut removes fractional territory without removing any integer-feasible point. Our tiny example supplies one in two lines of arithmetic. Add three quarters of the first constraint to one quarter of the second:

Every integer-feasible point satisfies the stronger second inequality because its left-hand side is an integer. The fractional root point reaches 15.75 and is cut away. Ralph Gomory's 1958 cutting-plane work made this logic algorithmic; modern solvers draw from many families of cuts and decide dynamically which ones are worth adding.[4]

Solver logs often call these two tracks the primal bound and the dual bound. The primal track searches for better feasible incumbents. The dual track tightens the global limit derived from relaxations. Sometimes the final plan is found early and most of the runtime is spent proving that nothing better remains. The first article's lesson returns in a more expensive form: computation often buys less improvement in the answer than confidence in it.

Three places where fractions mean different things

A warehouse has a fixed cost

A warehouse-location model has continuous shipment variables x_ij and binary opening variables y_i. The binary is the switch: y_i = 1 if site i opens and 0 otherwise. A linking constraint such as

allows shipments only from an open site. In the objective, f_iy_i charges its fixed operating cost. Relaxing y_i to 0.4 creates a useful bound by paying forty per cent of the fixed cost and receiving forty per cent of the capacity. It does not describe a facility the company can build.

There is an instructive exception nearby. With integral supplies and demands, every vertex of the classical transportation polytope is integral, so an LP optimum already hands back whole shipments and no branching is needed.[5] The presence of discrete quantities is therefore not by itself what makes a model expensive. How the constraints are written, and what structure that gives the matrix, decides it.

A portfolio may hold at most K names

Markowitz's basic weights are continuous. A cardinality rule adds a binary y_i saying whether asset i appears, then links it to its weight:

The model now chooses both which assets to own and how much of each. With a quadratic variance objective it becomes a mixed-integer quadratic program. A fractional y_i in the relaxation can support a bound, but it has spent only a fraction of one place in the portfolio. That is not the rule the manager asked to enforce.[6]

A cell optimises inside the model

Flux balance analysis treats metabolic reaction rates as continuous variables and usually maximises a proxy for cellular growth. OptKnock adds an outer set of binary knockout decisions: keep or disable a reaction, while the modelled cell responds by solving its own inner growth LP. Burgard, Pharkya and Maranas converted that bilevel construction into one MILP using the strong duality of the inner LP.[7]

In my own metabolic-modelling work, binary use variables record whether reactions may be active and, in thermodynamic formulations, in which direction. A relaxed value of 0.4 is computational bookkeeping, not forty per cent of a biochemical reaction. Rounding those indicators independently can violate their linking constraints to flux or a cardinality limit; repairing the fluxes may then disturb mass balance or feasibility elsewhere.

That broader line of model-guided strain design did not stay inside textbooks. In 2011, Yim and co-authors reported an engineered E. coli pathway for direct production of 1,4-butanediol; Anthony Burgard was part of the Genomatica team.[8] No single MILP produced that strain. The work combined pathway identification, a genome-scale model and years of biological engineering. But the discrete interventions it chose were built into a living organism.

What remains after the answer changes

The continuous model from the first two pieces has not been discarded. It survives as the relaxation that produces every bound in the tree. The certificate has not disappeared either. It has become a tree whose unresolved leaves measure what the optimiser still does not know.

That distinction matters the moment a solve runs into a deadline. An incumbent without a bound is a candidate. A bound without an incumbent is a limit with nothing implementable attached. Together they say what can be acted on and how much improvement might still exist.

The model can now certify that no better warehouse plan, gene-deletion set or cardinality-constrained portfolio exists beyond a stated optimality tolerance. It is still taking every coefficient as given. Fixed costs, expected returns, capacities and reaction bounds all enter the model as if they were facts. In the next piece they become estimates. The optimiser will go on doing exactly what it was asked to do, and that is precisely where the trouble starts.

Data and code

Every number and both figures are generated in the Post 3 folder of github.com/Denis-Joly/what-optimal-means. The scripts solve the LP relaxation and integer model with HiGHS, enumerate all lattice points as an independent check, reproduce the branch-and-bound trace with exact rational arithmetic and verify the bound invariants at every step.

The pedagogical branch-and-bound script is deliberately not presented as HiGHS's internal search. Real solvers may choose different variables, nodes, cuts and incumbents. The exact trace is useful because it exposes the proof; the production solver is useful because it independently confirms the answer.

References

1. Stephen P. Bradley, Arnoldo C. Hax and Thomas L. Magnanti, Applied Mathematical Programming, chapter 9 (Addison-Wesley, 1977), especially §§9.4–9.5. MIT hosts the authors' text. The four-way comparison and branching tree above reproduce its example; the companion code uses the same branches on an explicitly declared processing schedule and verifies them independently.
2. Ailsa H. Land and Alison G. Doig, “An Automatic Method of Solving Discrete Programming Problems”, Econometrica 28, no. 3 (1960): 497–520.
3. Gurobi Optimization, “MIP Logging”, documentation for the incumbent, global bound, gap, cuts and branch-and-cut progress; Ksenia Bestuzheva et al., “The SCIP Optimization Suite 8.0”, 2021.
4. Ralph E. Gomory, “Outline of an Algorithm for Integer Solutions to Linear Programs”, Bulletin of the American Mathematical Society 64, no. 5 (1958): 275–278.
5. Alexander Schrijver, Theory of Linear and Integer Programming (Wiley, 1986), chapters 19–21. Total unimodularity yields integral vertices here when the right-hand side is integral.
6. Daniel Bienstock, “Computational Study of a Family of Mixed-Integer Quadratic Programming Problems”, Mathematical Programming 74 (1996): 121–140; T.-J. Chang, N. Meade, J. E. Beasley and Y. M. Sharaiha, “Heuristics for Cardinality Constrained Portfolio Optimisation”, Computers & Operations Research 27 (2000): 1271–1302.
7. Anthony P. Burgard, Priti Pharkya and Costas D. Maranas, “OptKnock: A Bilevel Programming Framework for Identifying Gene Knockout Strategies for Microbial Strain Optimization”, Biotechnology and Bioengineering 84, no. 6 (2003): 647–657.
8. Harry Yim et al., “Metabolic Engineering of Escherichia coli for Direct Production of 1,4-Butanediol”, Nature Chemical Biology 7 (2011): 445–452.