Verifying a Reported Solution

A solver returns a status, a point and a value. Checking that answer is a competence separate from producing one, and it is cheap: substitute the point into every constraint, recompute the objective, and ask whether the reported status is consistent with what you find. Each check catches a different class of fault, and a model that solves without error can still be answering a different question than the one you posed.

Definition

A solver reports a status, and if it terminated successfully, a point $\hat{x}$ and an objective value $\hat{z}$ . Verification is a sequence of independent checks.

Primal feasibility. Substitute $\hat{x}$ into every constraint of the model as you wrote it, including sign restrictions and bounds. Every one must hold, within a stated numerical tolerance.

Objective consistency. Recompute $c^{T} \hat{x}$ from the reported point and compare with $\hat{z}$ . A mismatch means the objective solved is not the objective written, typically a sign error, a missing constant from a shifted variable, or a term omitted.

Status credibility. Ask whether the reported status is consistent with what the model can support. A status of INFEASIBLE is refuted by exhibiting any point that satisfies every constraint. A status of UNBOUNDED requires a direction along which the region recedes and the objective improves; if every variable carries a finite upper bound, no such direction exists and the status is false.

Optimality evidence. For a reported optimum, nonnegative reduced costs on all nonbasic variables certify optimality for a minimisation. Where duals are reported, complementary slackness gives an independent check: a constraint with slack should carry a zero dual, and a nonzero dual should correspond to a binding constraint.

What verification cannot do. It cannot establish that the model is the right model. A point may satisfy every constraint you wrote and be useless because a constraint you meant to write is absent.

Assumptions and scope

Feasibility must be checked against the model as originally written, not against the transformed program the solver received. Checking against the transformed version verifies the transformation and misses the transcription faults that are more common.
Numerical tolerance is unavoidable. A constraint satisfied to within $10^{- 9}$ is satisfied; treating floating-point residue as a violation produces false alarms, and a tolerance loose enough to hide a real violation produces false confidence.
A reported status is a claim about the model the solver received, not about the model you intended. Statuses that contradict inspection indicate a translation fault rather than a solver defect.
Verification establishes that an answer is consistent with the model. It cannot establish that the model represents the situation, which is a formulation question and is not decidable from the solver's output at all.
A shifted or split variable means the reported values are not the original decision variables. The optimal value may also carry a constant that must be restored before the number is comparable with anything.

Worked material

Example

Three reports and what each check returns

A clean report. Model: $max 3 x_{1} + 2 x_{2}$ subject to $x_{1} + x_{2} \leq 10$ , $x_{1} \leq 6$ , $x_{1}, x_{2} \geq 0$ . Reported: OPTIMAL, $\hat{x} = (6, 4)$ , $\hat{z} = 26$ .

Feasibility: $6 + 4 = 10 \leq 10$ holds with equality; $6 \leq 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 \neq 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 \leq 10$ , $0 \leq 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.

Non-example

Checks that do not check what they appear to

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.

Contrast

A clean solve is not a correct model

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 $2 x_{1} + 3 x_{2} \leq 100$ and type $2 x_{1} + 3 x_{2} \geq 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.

Common errors

Common misconception

A solver that returns an optimal status without errors has confirmed that the model is correct, so a reported optimum does not need independent checking.

Verifying a Reported Solution

Assumptions and scope

Worked material

Three reports and what each check returns

Checks that do not check what they appear to

A clean solve is not a correct model

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history