Integers change the answer

Drop the whole-number requirement and solve the easy problem. If the answer happens to be whole, you are finished. If some variable comes back at 30.6897, no whole-number plan can sit between 30 and 31 for that variable, so split the problem in two: one where it is at most 30, one where it is at least 31. Solve each. Each relaxed answer is an upper bound on everything inside that branch, so the moment a branch's relaxed answer falls below the best whole plan you have already found, the whole branch can be discarded without being explored. Keep splitting what is left. Ravensworth finishes in 29 nodes.

• Integer programme. The same objective and constraints, plus a requirement that some or all variables be whole numbers.
• Relaxation. The same problem with the whole-number requirement dropped. Easy to solve and always at least as good as the real answer.
• Bound. The relaxed value of a branch. Nothing inside that branch can beat it, which is what makes it useful.
• Incumbent. The best genuinely whole-number plan found so far. It only ever improves.
• Prune. Discard a branch whose bound cannot beat the incumbent. No solving, no exploring, no apology.
• Node. One subproblem in the search. Ravensworth takes 29 of them.
• Gap. The distance between the best bound and the incumbent. When it closes, the incumbent is proved optimal.
• Origin shift. Applying a lower bound by substituting x = L + x' rather than by adding a row. Tonight it is the difference between a search that works and one that quietly does not.

Every whole-number plan is also a legal fractional plan, because a whole number is a number. So the set of plans the relaxation searches contains the set of plans the integer problem searches, and the best of a larger set is at least as good as the best of a smaller one. That one sentence is what the entire method rests on, and it is worth being able to say it without hedging, because it is also what lets you prune.

Read Ravensworth's two numbers with that in hand. The relaxation says 4,666.90 and the whole-number answer is 4,656.00. The second must be at most the first, and the gap between them, 10.90, is the price of being unable to bag fractions of a tonne. That gap is the honest cost of integrality, and the rounded plan's shortfall of 60.00 is something else entirely: it is the cost of a bad method.

The recursion carries two arrays, lo and hi, holding the current bounds on every variable. At each node it builds the node's own linear problem, solves it with the same simplex from session 3, and then does three tests in order. If the status is not optimal, return. If the bound cannot beat the incumbent, return, which is the line if (bound <= bestObj + 1e-7) return; and it is the prune. If every integer variable came back whole, this is a new incumbent, so record it and return.

Only if all three tests fall through does it branch: take the first variable that is still fractional, and call itself twice, once with that variable's upper bound set to Math.floor of the fractional value and once with its lower bound set to Math.ceil. There is a node counter with a ceiling of 6,000 and a depth limit of 60, both of which are guards rather than parts of the method, in the same spirit as the iteration counter inside the simplex.

Pruning needs an incumbent to prune against, and at the start of the search there is not one. Until some branch runs all the way down to a whole-number plan, bestObj is negative infinity and no branch can be discarded, so the early part of the search is pure exploration with no savings at all. This is why the order matters: find a decent whole plan early and a large fraction of the tree evaporates, find one late and you paid to walk it.

This implementation takes the first fractional variable it finds, and explores the down branch before the up branch, which is a choice with no theory behind it. Choosing the variable that most changes the bound, or diving towards a feasible plan first and only then searching properly, are both standard and both cost something per node. The node count you see is a property of those choices as much as of the problem.

The continuous optimum sits on a corner where two ceilings meet exactly. Chop a fraction off one variable and the plan is no longer on that corner, and the capacity you just released is not free, it is stranded. Nothing puts it back to work, because rounding is not an optimisation, it is an edit. The whole-number optimum is a genuinely different corner of a genuinely different problem, found by searching, and there is no reason for it to be near the continuous one.

Here the search discovers that giving up a tonne of Dairy, 64.8276 down to 63, frees enough milling and protein to add nearly three tonnes of Standard, and the swap pays. That trade is invisible from the continuous answer, and rounding cannot find it because rounding never re-solves anything.

If the mill were planning 30,689 tonnes rather than 30.6897, one tonne either way would be a rounding error in the ordinary sense, and nobody should spend a search on it. The damage from rounding scales with how large one unit is relative to the quantities. Small numbers of large things are where integrality bites, and Ravensworth's whole-tonne batches are exactly that case.

The test is cheap enough that you do not have to guess. Solve both, compare, and keep the comparison in the write-up. If the gap is negligible on your problem, you now know rather than assume, and you have a number to point at when somebody asks why the model does not respect whole units.

Three things lined up. The refusal was legitimate: a negative right hand side really does need a preliminary phase this solver does not implement, and returning a status was the honest thing to do. The caller's early return on a non-optimal status was also reasonable, because a node that cannot be solved is usually a node with no feasible plans in it. And the output of a search that only ever goes down is a real, feasible, whole-number plan with a normal-looking objective. Every individual decision was defensible and the combination was wrong.

Note what would not have caught it. Reading the code catches it only if you are already thinking about signs. The three shipped self-test problems do not catch it, because none of them has an optimum that requires branching upward. A unit test asserting that solveMILP returns an optimal status passes. What caught it was solving many generated problems a second way and comparing, which is the subject of session 9.

Given a model with fractional quantities, should you enforce integrality at all? Practitioners split, and not along a line of sophistication.

One camp treats integrality as something to avoid wherever it can honestly be avoided. Solving the relaxation is fast and predictable; solving the integer version can take exponentially longer and the time is impossible to forecast, which is fatal for anything that has to run on a schedule. In most operational settings the quantities are large enough that a unit is noise, the input data are far less precise than the fraction being argued about, and a plan that arrives late is worth nothing however optimal it is. On this view, add integrality only after demonstrating that rounding actually costs something.

The other camp holds that the demonstration is the whole point and it is cheap to run, so run it. Rounding does not merely lose a little, it can land in a different part of the space, as it does here, and it silently hides trades the search would have found. Worse, a great many real decisions are not quantities at all but yes-or-no choices, where there is no such thing as rounding and the relaxed answer is meaningless on its own. On this view, treating integrality as optional is a habit formed on problems where it happened not to matter.

They agree on more than they appear to: both would solve both and compare. They differ on which one is the default when the comparison has not been done yet, and that default decides what ships when somebody is in a hurry.