Verifying a Reported Solution

A solver optimises whatever program it was handed and reports success. Checking that it solved the program you meant is a separate skill, and it costs a fraction of the solve.

Everything so far has been about producing an answer. This is about receiving one. They are different skills, and only the first is usually practised, which is why a confident wrong answer so often survives to a decision.

The asymmetry is what makes the checks worth doing. Finding the optimum of a large program is expensive; substituting a reported point into the constraints is a few multiplications. Recomputing an objective is one dot product. Each check is cheap and each catches a class of fault the solve itself cannot, because a solver faithfully answers whatever question it was handed, including the wrong one.

This unit assumes you can classify the terminal outcomes of a linear program and convert one to standard form.

A solver takes a program and returns the optimum of that program. If the program you handed it is not the program you meant, it optimises the one you handed it, correctly, and reports success. The solver has no access to the model you intended.

So a constraint transcribed with a sign error does not produce an error message. It produces a perfectly well-posed linear program with a genuine optimum for a problem nobody has. The output looks exactly like the output of a correct model: a status, a point, a number.

That is the gap the checks are aimed at, between the model you wrote and the model you meant. And the most valuable single check follows directly: substitute the reported point into the constraints as you originally stated them, on paper, not as they appear in the file the solver read. Checking against the file verifies the file. Checking against your formulation catches the transcription.

The status line deserves its own scepticism, because some claims are refutable almost for free. An INFEASIBLE status falls to a single point satisfying every constraint, and the origin often is one. An UNBOUNDED status requires a direction in which the region runs on forever and the objective improves; if every variable has a finite upper bound, no such direction exists and the status cannot be true of the model you wrote.

When a refutable status survives its refutation, you have found something real. It is nearly always in the translation between your model and the solver's input, and it is nearly always faster to find this way than by rereading the model.

The canonical statement lists the checks. What makes them worth doing is that each catches a failure the others cannot see.

Feasibility is checked against your model, never the solver's input. The solver optimised whatever file it read. Substituting $\hat{x}$ into the constraints as written in the formulation is the only step that compares the answer with the problem you meant to pose, and it is the one that catches a constraint entered into the wrong array or dropped entirely.

Objective consistency catches the conversions. Recomputing $c^{\mathsf{T}}\hat{x}$ and comparing with $\hat{z}$ finds a sign left unflipped after a maximisation was entered into a minimiser, and the additive constant $c_j\ell$ that a shifted variable leaves behind. Both produce a correct optimal point with a wrong reported value, which no feasibility check would notice.

Status credibility is a claim about the model, not the arithmetic. “Infeasible” on a problem you believe has a solution usually means a constraint says something other than intended; “unbounded” usually means one is missing. Both are reported as successes by a solver doing exactly what it was told.

What no check reaches is whether the model represents the situation. Every check above compares an answer against a formulation; none compares the formulation against the world.

Write down the model as you intended it, separately from the solver's input. This is what the reported point will be tested against. If the only statement of the model is the input file, the most valuable check is unavailable.

Undo any variable transformations first. If variables were split, shifted or negated, recover the original values, $x=x^{+}-x^{-}$, $x=u+\ell$, $x=-v$, before testing anything. A reported point in converted variables is not a point of your problem.

Substitute into every constraint and record the residual. For each row compute the left-hand side and compare with the bound, keeping the actual numbers rather than a yes or no. Record residuals near tolerance, and note any constraint satisfied by a wide margin where you expected it to bind.

Check the sign restrictions and bounds explicitly. These are constraints and are the ones most often omitted from a check, because they are not written among the numbered rows.

Recompute the objective from the recovered point. Include any constant left by a shift. Compare with the reported value.

Test the status against a refutation. For an infeasibility claim, try to produce a feasible point. For an unboundedness claim, look for a recession direction, and check whether bounds preclude one. For an optimality claim, check the reduced costs or the duals if they are reported.

Attribute any discrepancy before re-running. A feasibility failure against your written model with a clean solver run points at transcription. An objective mismatch points at the objective row or a dropped constant. A status contradicting inspection points at the translation. Re-running an unchanged model answers nothing.

Record the tolerance you used. A check reported without its tolerance cannot be repeated, and 'it checked out' is not a finding.

A clean report. Model: $max3x_1+2x_2$ subject to $x_1+x_2\le 10$, $x_1\le 6$, $x_1,x_2\ge 0$. Reported: OPTIMAL, $\hat{x}=(6,4)$, $\hat{z}=26$.

Feasibility: $6+4=10\le 10$ holds with equality; $6\le 6$ holds with equality; both components nonnegative. Objective: $3(6)+2(4)=18+8=26$, matching. Status: both constraints bind, and the objective improves in the direction of increasing either variable, so no better feasible point is available. Accept.

An objective mismatch. Same model, reported $\hat{x}=(6,4)$ with $\hat{z}=10$. Feasibility passes exactly as above. Recomputing gives $26\ne 10$. The point is feasible and the value is not the value of that point, so the objective solved is not the objective written. Note that $10$ is what $x_1+x_2$ evaluates to: the objective row and a constraint row have been transposed somewhere in the input. Reject, and look at the objective row.

A refutable status. Same model, reported INFEASIBLE. The origin $(0,0)$ satisfies $0\le 10$, $0\le 6$, and both sign restrictions. A feasible point exists, so the model as written is not infeasible. Reject the status, and look for the discrepancy between the written model and the input. A bound entered with the wrong sign is the usual cause.

The model as written.

The report. Status OPTIMAL. Solved in converted variables: $u=30$, $b=0$, objective value $150$, where $a=u+10$.

Goal. Decide whether to accept the report.

Step 1: recover the original variables. $a=u+10=30+10=40$, and $b=0$. The point in the original problem's terms is $(a,b)=(40,0)$.

Step 2: primal feasibility against the written model. $a+b=40+0=40\le 40$: holds, binding. $a=40\ge 10$: holds. $b=0\ge 0$: holds. Feasible.

Step 3: recompute the objective. $5(40)+4(0)=200$.

The reported value is $150$. A mismatch of $50$.

Step 4: locate it. The substitution $a=u+10$ puts $5(u+10)=5u+50$ into the objective. The converted objective is $5u+4b$ with the constant $50$ held aside, and $5(30)+4(0)=150$ is exactly that converted objective. So the solver's $150$ is correct for the converted program; the constant was never restored.

Step 5: attribute. Not a solver fault, not a transcription fault, and not a formulation fault. A transformation that was not fully reversed. The optimal point is right, $(40,0)$, and only the reported number is wrong.

Step 6: the corrected report. Optimal solution $a=40$, $b=0$, optimal value $200$.

Why this case is worth practising. Every check on the point passed. Feasibility was clean, the status was credible, the solution was genuinely optimal. Only recomputing the objective from the recovered point exposed it, and a verification that stops at feasibility would have confirmed a report understating the answer by $50$.

Not a verification: re-running the solver. Running the same input again returns the same answer. It confirms determinism, not correctness, and it is the most common response to a suspicious result.

Not sufficient: checking feasibility against the solver's input file. That verifies the file is self-consistent. The fault being hunted is usually the difference between the file and the model you intended, which this check cannot see by construction.

Not a fault: a small residual. A constraint satisfied to within ${10}^{-9}$ is satisfied. Floating-point arithmetic does not produce exact zeros, and treating residue as violation generates false alarms that train people to ignore the check.

Not evidence of optimality: a plausible-looking answer. A point that is feasible and has a good objective value may still not be optimal. Optimality needs the reduced costs, the duals, or an argument, not the impression that the number looks about right.

Not covered by any of these checks: a missing constraint. If a restriction that exists in the situation was never written into the model, the reported point will pass every check listed here and still be unusable. Verification compares an answer with a model; whether the model is right is a formulation question.

The most expensive mistake available here is treating a successful solver run as an endorsement of the model.

What a solver's OPTIMAL status actually claims. That for the program it received, the reported point is feasible and no feasible point has a better objective value. That claim is almost always true and almost always irrelevant to the question of whether the model is right.

What it does not claim. That the program it received is the program you meant. The solver has no access to your intention, so a transcription error produces no error at all, just a different well-posed program with a genuine optimum.

A concrete case. You intend $2x_1+3x_2\le 100$ and type $2x_1+3x_2\ge 100$. Both are valid constraints. The solver optimises over the second, reports OPTIMAL with a point satisfying it, and the point may well violate the capacity you actually have. Nothing in the run flags it. Substituting that point into the constraint as you wrote it on paper flags it immediately.

Why the instinct is hard to dislodge. Software that reports errors when misused trains a reasonable expectation that silence means correctness. Solvers break that expectation because almost any input is a legitimate problem. Silence here carries no information about the model at all.

The discipline. Keep a statement of the model independent of the solver's input, and test the reported point against it. That single habit catches the class of fault that no amount of solver sophistication can, and it is cheap enough to do every time.

1. Model: $max4x_1+x_2$ subject to $x_1+x_2\le 12$, $x_1\le 5$, $x\ge 0$. Report: OPTIMAL, $(5,7)$, value $27$. Run all four checks and give your verdict.

2. Same model, report: INFEASIBLE. Refute or accept the status, showing your evidence.

3. A model has $x_1\le 20$, $x_2\le 15$ and no other bounds, and the solver reports UNBOUNDED. What can you conclude without examining the objective?

4. A report gives the optimal point in variables $u$ and $v$, where the model had a variable $w$ free and $w=u-v$. The reported point is $u=9$, $v=4$. What is $w$, and what would you have concluded had the report instead shown $u=14$, $v=9$?

5. Every check passes and the answer is still wrong in practice. Name a cause consistent with that, and say why no check in this unit would find it.

Checking an answer is a separate competence from producing one, and it costs a fraction as much.

Four checks. Primal feasibility, substituting the reported point into the model as originally written. Objective consistency, recomputing the value from that point. Status credibility, testing the claim against evidence that would refute it. Optimality evidence, from reduced costs or duals where available.

Recover transformed variables before checking anything, and restore any constant a shift left in the objective. A point in converted variables is not a point of your problem, and a value missing its constant is not your value.

A solver does not validate your model. It optimises whatever program it receives and reports success, so silence carries no information about whether the program is the one you meant. That is why the feasibility check must run against your own statement of the model rather than the input file.

A discrepancy should be attributed before anything is re-run: transcription, an unreversed transformation, or a formulation that does not represent the situation. Re-running an unchanged model answers nothing.

And no check here can find a constraint you never wrote. Verification tests an answer against a model; it cannot test a model against the world.