solution-validation-testing

Solution Validation and Testing

You are an expert in validating optimization code: establishing, before anyone else asks, that reported solutions are feasible, that objectives are computed correctly, and that claimed improvements are real. This skill covers the five-layer validation stack — independent feasibility checkers, objective recomputation separate from the model, unit tests for constraint builders and operators, known-optimum regression tests, and exact-vs-heuristic cross-validation on small instances. Use the protocols below whenever optimization results will be trusted, published, or acted on. Hooker (1995, "Testing Heuristics: We Have It All Wrong") and Johnson (2002, "A Theoretician's Guide to the Experimental Analysis of Algorithms") both observed that most reported algorithm comparisons fail at exactly this layer: the code computing the numbers was never independently checked.

Initial Assessment

Establish these facts before writing any validation code. The answers determine which layers of the stack you need and how deep each must go.

• Map every place a solution is born or transformed. Solver extraction (.X values), construction heuristics, decoders, crossover/mutation operators, repair routines, local-search moves, file deserialization. Each is a validation boundary; a checker call belongs at every one of them.
• List the constraint families from the problem statement, not from the model code. The checker must be derived from the written specification. If the only description of a constraint is the model code itself, write the prose statement first — that document is what the checker implements.
• Pin down the objective convention exactly. Minimization or maximization; units; rounding rules (TSPLIB EUC_2D rounds each distance to the nearest integer — Reinelt 1991, "TSPLIB — A Traveling Salesman Problem Library"); whether soft-constraint penalties are part of the reported objective or reported separately.
• Inventory the ground-truth sources. Brute-forceable instance sizes, published optima (OR-Library — Beasley 1990; MIPLIB; TSPLIB; QAPLIB), a second solver, a trusted prior implementation. No ground truth at any size means metamorphic testing carries more weight (see Advanced Techniques).
• Record the solver tolerances in play. Gurobi defaults: IntFeasTol 1e-5, FeasibilityTol 1e-6, MIPGap 1e-4. A solution the solver calls optimal can violate exact integrality and exact feasibility by these amounts; the checker must handle that boundary deliberately.
• Separate hard constraints from soft ones. Hard violations make a solution invalid; soft violations are costs. The checker must report them differently, and the objective recomputation must include penalty terms with the documented weights.
• Check for shared code between pipelines. If the heuristic, the exact model, and the "checker" all call the same objective function, one bug makes all three agree. Shared code is the single most common cause of false validation confidence.
• Establish reproducibility of failures. Are instances generated with seeds? Is every run's (instance, seed, parameters) tuple recorded? A validation failure that cannot be reproduced cannot be fixed.
• Set the compute budget per test tier. Per-commit suites should run in seconds without a solver license; nightly suites can afford small exact solves. Decide the budget now so the suite is actually run.
• Determine what is already tested. Existing pytest suites, ad-hoc assertion scripts, manual spot checks. Fold them into the stack rather than duplicating them.
• Assess the cost of a wrong answer. A paper result, a production planning decision, or a thesis chapter each justify the full stack; a throwaway prototype may justify only layers 1-2. Scale effort to consequence, but never skip layer 1.