Three cases pass, and that is not verification
A solver that is subtly wrong does not throw. It returns a plan, a margin, a slack column and a set of prices, all formatted correctly and all plausible, and there is nothing in the reply to distinguish it from a correct one. That is the situation to design against, because it is the only failure mode in this whole subject with no symptom at the point of use.
★ What you walk out with tonight. Two real faults, told in the order they were found, with the second one lying in the opposite direction to the first. A cross-check you can run in this page over 1,100 generated problems, and can watch fail when the checker is given the box it originally had. And one habit that would have caught both faults on the first afternoon: generate random instances and check them against something that cannot share the same mistake.
LiveWhat the three cases are for4 min▶
They are worth having. A hand-checked case catches the errors of the first hour: a transposed matrix, a sign flipped on the objective row, a ratio test that picks the wrong leaving row on the simplest possible input. Every one of those would fail case one immediately, and finding them in ten seconds rather than in a client meeting is the entire value of the suite.
What the suite cannot do is tell you about the region of input space it does not visit. Three problems is three points. Branch and bound has branches that none of the three ever enters, because all three are solved at the relaxation or at the first split. The code in those branches was never executed by the test suite, and untested code that is also unexecuted looks exactly like code that works.
The honest description of a passing suite is "the code runs and does the obvious thing on the obvious inputs". That is a real statement and it is not the statement people hear, which is "the solver is correct". The gap between those two sentences is where this session lives.
Self-studyThe words, and where each one bites4 min▶
- Hand-checkable case. A problem small enough that the right answer is known without running the code. Three of them here.
- Cross-check. Running the same problem through a second, independent method and comparing. The main tool tonight.
- Brute force. Enumerate every candidate in a box and keep the best. Slow, simple, and easy to get right, which is why it makes a good second opinion.
- Silent refusal. A function that declines to answer and says so in a return value nobody reads. Worse than a crash, because the caller carries on.
- Negative right hand side. A row written as
-x <= -5. This simplex has no phase one, so it will not start from there. - Origin shift. Substituting
x = L + x'to impose a lower bound while keeping every right hand side non-negative. The fix for fault one. - Search box. The range a brute force enumerates over. If it is smaller than the feasible region, the brute force is wrong and looks confident. Fault two.
- Laundering a bug. Agreement between two methods that share a mistake, mistaken for evidence of correctness.
A refusal nobody read, and a search that only went down
15 min liveBranch and bound splits on a fractional variable. If the relaxation says x = 4.3, one child forces x <= 4 and the other forces x >= 5, and between them they cover every integer possibility. The first child is easy to add: a row with a positive right hand side. The second one is the fault.
// A lower bound written as a row carries a negative right hand side.
OPT.solveLP([1, 1], [[1, 1], [-1, 0]], [10, -5]);
// { status: "needs-phase-one",
// message: "a negative right hand side needs a phase one start, ..." }
// No exception. No console warning. A plain object with a status field,
// and a caller that checks only for "optimal" throws the branch away.
// The fix, as the branch and bound now does it: shift the origin so the
// lower bounds are built into the variables rather than added as rows.
// b2[i] = b[i] - sum over k of A[i][k] * lo[k]; // stays >= 0
// solve in x', then report x = lo + x'.
...
LiveWhy the wrong answers were plausible4 min▶
Think about what a downward-only search actually produces. Every plan it finds is feasible, because rounding a variable down inside a set of upper-bound constraints keeps you inside the region. Every objective value it reports is achievable. The status says optimal. The plan is integral. Nothing about it is malformed in any way a type system, a schema or a reviewer scanning output would notice.
It is simply not the best plan. The fault produced answers that were too low by an amount that varied with the problem, which is the most difficult kind of wrong to notice, because there is no fixed offset to spot and no value that is obviously impossible. On Ravensworth in particular the true integer optimum has Standard at 33 while the relaxation sits at 30.69, so the right answer is reached by rounding a variable up. A search that never rounds up cannot find it.
LiveA silent refusal is worse than a crash3 min▶
Compare the two possible behaviours. If the simplex had thrown on a negative right hand side, the first branch-and-bound run would have stopped with a stack trace pointing at the exact line, and the fault would have been fixed in five minutes. Because it returned a status instead, the program carried on, produced a complete and well-formed answer, and the fault survived every test in the suite.
The general rule is worth carrying around. A library that declines to answer should make the decline impossible to ignore, and a caller that receives a status it did not expect should treat that as a defect rather than as an empty result. The pattern to look for in your own code is any place where a non-success status silently becomes "nothing here", because that is where a refusal turns into a wrong number.
Then the solver started overstating, and it was right
12 min liveWith the origin shift in place the search finally explored both directions, and the cross-check began reporting a new class of disagreement in the opposite direction: the solver now claimed values the brute force said were impossible. The obvious reading is that the fix introduced a bug. The obvious reading was wrong.
Press the button. Each problem is generated from the seed, solved by branch and bound, and solved again by enumeration.
LiveReading a disagreement without assuming who is wrong4 min▶
When two methods disagree, the instinct is to trust the simpler one. It is a decent prior and it is not evidence. The brute force here is twelve lines long and the branch and bound is sixty, so the brute force felt obviously right, and it was the one with the fault.
The move that settles it costs a minute and needs no theory. Take the disputed point the solver claims, put it back into the original constraints by hand, and check two things: that it satisfies every row, and that it earns what the solver said. If both hold, the solver's answer is achievable and the checker's answer is not the maximum, whatever the checker thinks. That test is one-directional and completely decisive, because feasibility and objective value are both trivial to verify even when optimality is not.
Notice the shape of that argument. Checking a claimed optimum is easy; finding one is hard. Wherever that asymmetry exists, verify the claim rather than re-deriving the answer.
LiveWhat 1,100 of 1,100 does and does not prove3 min▶
After both fixes, 1,100 of 1,100 agree across five seeds. That is a far stronger statement than three cases passing, and it is still a statement about a region of input space. The generated problems have a particular number of variables, coefficients from a particular range and right hand sides from another, and a fault that only appears outside those ranges would not show up here any more than it showed up in the three hand-checked cases.
So the honest claim is bounded and should be written that way: agreement with an independent enumeration on 1,100 generated problems across five seeds, within the stated generator. Not "the solver is correct". The difference matters most when somebody later feeds it a problem shaped differently from anything the generator produces.
Self-studyWhere serious people disagree5 min▶
There is a live argument about whether writing the solver was the right call at all, and it is sharpened rather than settled by this session.
One camp says this is the case against ever implementing your own. The two faults here were not exotic; they are in the standard list of things that go wrong in branch and bound, and they still took a generated cross-check to find. A mature implementation has had those exact faults found by other people over many years, and the time spent here was spent re-discovering known bugs. On this view the correct move is to use something maintained and spend the saved days on the formulation, which is where the errors that actually cost money live.
The other camp says the exercise bought something a dependency cannot. Nobody on this project can be fooled by a plausible plan any more, because they have seen the same code produce plausible plans that were wrong. A team using a solver purely as a black box has no calibration at all for how a subtly broken answer looks, and will happily pass one along. On this view the cross-check habit is the deliverable and the solver is the excuse.
The strongest version of each: a dependency does not remove the need for a cross-check, because your formulation can be wrong even when the solver is perfect, and the cross-check catches both. And a hand-written solver does not remove the need for judgement about when the extra days are affordable. What neither camp argues for is trusting an unverified answer, whoever wrote the code.
Break the checker, then break the solver
15 min hands onSix steps, using the two live boxes above and a page console. The aim is to leave with the cross-check as a reflex rather than a technique, and with a clear memory of what a wrong answer looked like.
Watch the refusal happen
In the console, call OPT.solveLP([1, 1], [[1, 1], [-1, 0]], [10, -5]) and read the object that comes back. Note that no exception was thrown and no warning appeared. Then write the one line of caller code that would have turned this into a loud failure.
Run the cross-check both ways
Run it with the box sized from the constraints and note the agreement count. Switch to the capped box and run it again. Write down how many problems the old checker got wrong, and in which direction it was wrong.
Verify one disputed point by hand
Take a disagreement from the capped run. Put the solver's claimed point into the problem's constraints yourself and check that it fits, then compute its objective. Say out loud which of the two methods the arithmetic convicts.
Confirm the round-up case on Ravensworth
Solve the mill's relaxation and read the Standard variable. Then solve it as integers. The optimum requires rounding that variable up, not down. Say in one sentence what the old fault would have reported for the mill, and why nobody would have queried it.
Write a generator for your own problem shape
Not for this solver. For something in your own work that has a checkable answer: a pricing rule, an allocation, a rounding routine. Write twenty random inputs and a second implementation that computes the answer a slower, dumber way. Compare them.
Plant a fault and confirm the check catches it
Deliberately break your slow implementation, run the comparison, and confirm it fails. A cross-check that has never failed has not been shown to be capable of failing. Session 10 puts every piece of the toolkit on one bench.
The habit to keep. When you write or inherit a solver, generate random instances and check them against something that cannot share the same mistake. Then plant a fault and confirm the check catches it, because an agreement you have never seen fail is not evidence. And treat any status you did not expect as a defect rather than as an empty result.
Three questions
The solver passes all three of its hand-checked cases. What does that establish?
The suite is worth having and catches the errors of the first hour. It cannot speak for the region of input space it never visits, and this solver passed all three while being wrong on roughly one problem in five.
Why did applying a lower bound as the row -x <= -5 make the solver understate optima?
The row is a correct statement of the bound. The problem is that this simplex has no phase one, its refusal is a return value rather than an exception, and a caller that only checks for "optimal" silently discards the branch. The fix is to shift the origin with x = L + x' so every right hand side stays non-negative.
After the fix, the solver reported values the brute force said were impossible. What was actually wrong?
The solver's points were feasible and their objective values were real, which is checkable in a minute by hand. The checker was searching a box smaller than the feasible region. An independent cross-check has to be independently correct, or it launders the bug it was meant to catch.
Homework
Thirty minutes, on code you already depend on.
Find your own silent refusal
Search your codebase for places where a non-success status, an empty result or a caught exception quietly becomes "nothing found". For each one, say what a caller would do with the wrong answer. Bring the worst example you find.
Build one cross-check and make it fail
Pick a calculation your team relies on. Write a second, slower implementation that shares no code with the first, run both over random inputs, then plant a fault and confirm the comparison goes red. Bring both the agreement count and the planted failure. Session 10 assembles the whole toolkit on one bench, with every number computed live.
What this session covers
Cheat sheet
x = L + x', so every right hand side stays non-negative.