Mip Solver And Solution Audit

MIP Solver and Solution Audit

Core principle

A valid optimization submission has one final solution, one set of recomputed metrics, and one truthful solver report. The solver objective, written output, metrics file, and explanation must all refer to the same final solution.

Feasible does not mean optimal. A time-limited MIP solve may return a useful incumbent without proving optimality. Report that distinction clearly.

Solver discovery

For Python optimization tasks, test installed solver packages before concluding that no solver is available. Prefer a callable installed solver over writing a model for an unavailable package or falling back to a heuristic-only method.

PySCIPOpt is a good first check for binary and mixed-integer models:

try:
    from pyscipopt import Model, quicksum
    SCIP_AVAILABLE = True
except Exception as exc:
    SCIP_AVAILABLE = False
    SCIP_IMPORT_ERROR = exc

If PySCIPOpt imports successfully, use it unless the task or environment clearly provides a better solver. Do not skip it because other packages or command-line binaries are unavailable.

If the task requires an integer program or optimization solver, do not submit a pure greedy search, local search, swap heuristic, or advisory script as the main method unless the task explicitly allows that substitution.

Minimal PySCIPOpt pattern

from pyscipopt import Model, quicksum

model = Model("mip_model")
model.setParam("limits/time", 600.0)

# create binary/integer variables
# add hard constraints
# build named objective components
model.setObjective(objective_expr, "minimize")

model.optimize()
status = str(model.getStatus()).lower()

if model.getNSols() == 0:
    raise RuntimeError(f"No feasible solution found; solver status={status}")

sol = model.getBestSol()
incumbent_objective = float(model.getObjVal())

try:
    best_bound = float(model.getDualbound())
except Exception:
    best_bound = None

try:
    mip_gap = float(model.getGap())
except Exception:
    mip_gap = None

Use model.getSolVal(sol, var) or model.getVal(var) to read values. Do not call unsupported variable methods such as var.getVal().

Incumbent, bound, and gap

Record solver information whenever the output format allows it:

• solver name and interface;
• solver status;
• time limit;
• incumbent objective;
• best bound, if available;
• MIP gap, if available;
• whether the solution is proven optimal, within a stated gap, or only a feasible incumbent.

Do not claim “optimal” unless the solver status or gap certifies it. Statuses such as time limit, node limit, solution limit, or gap limit usually mean the submitted solution is an incumbent, not a proof of global optimality.

For minimization, a useful manual check is:

absolute_gap = incumbent_objective - best_bound
relative_gap = absolute_gap / max(1.0, abs(incumbent_objective))

Prefer the solver-provided gap when available, because solvers may use their own safe conventions for bounds and tolerances.

Extraction discipline

After solving, extract the final output from the selected incumbent solution and validate the extracted artifact directly.

sol = model.getBestSol()

for binary_var in binary_vars:
    value = model.getSolVal(sol, binary_var)
    if value > 0.5:
        # include the corresponding assignment, route arc, sequence position, etc.
        pass

Validate hard rules from the output itself, not only from solver feasibility:

• every required item is assigned or served exactly as required;
• every required slot, position, capacity, or resource rule is satisfied;
• there are no duplicates or missing assignments;
• all task-specific eligibility, timing, and policy constraints hold;
• all numeric fields are finite and have the expected type.

If extraction fails, fix the model or extraction logic before writing output files.

Independent metric evaluator

Build a pure evaluator that depends only on the input data and the final output, not on solver variables. Use it to write the metrics file and to check the solver objective.

def evaluate_output(final_output, input_data):
    components = {}
    components["component_a"] = compute_component_a(final_output, input_data)
    components["component_b"] = compute_component_b(final_output, input_data)
    components["objective"] = weighted_sum(components)
    return components

final_output = extract_solution(model, sol)
validate_hard_rules(final_output, input_data)
metrics = evaluate_output(final_output, input_data)

If the solved model is intended to match the official objective, compare the independent evaluator with the solver objective:

if abs(metrics["objective"] - incumbent_objective) > 1e-6:
    raise AssertionError(
        "solver objective and independently recomputed objective differ; "
        "check the linearization, extraction, weights, and reported output"
    )

Write reported metrics from the independent evaluator. Do not mix solver expressions from one solution with a schedule, route, or assignment from another solution.

For sequence, route, timetable, or assignment tasks, make the evaluator mirror the official objective semantics, not a simplified human interpretation:

• preserve ordered tuple keys unless unordered keys are explicitly specified;
• use the declared start-position masks for each component;
• follow the declared successor/order relation instead of assuming zero-based contiguous positions;
• implement overlap terms exactly as defined, not as a broader span count or all combinations in a window unless that is the stated rule;
• treat missing rows consistently with the data contract, usually zero only when the task or table format supports sparse costs.

Never write metrics.json before reloading and evaluating the exact artifact that will be submitted.

Minimal final-artifact audit template:

def load_final_output(path):
    # Parse the exact CSV/JSON/text file that will be submitted.
    ...

def evaluate_output(final_output, input_data):
    # Pure function: no solver variables, no cached incumbent state.
    ...

final_output = load_final_output(output_path)
validate_hard_rules(final_output, input_data)
metrics = evaluate_output(final_output, input_data)

with open(metrics_path, "w") as f:
    json.dump(metrics, f, indent=2)

roundtrip = load_final_output(output_path)
roundtrip_metrics = evaluate_output(roundtrip, input_data)
assert roundtrip_metrics == metrics

Post-processing rule

If post-processing is used after the solver, disclose it and recompute all metrics from the post-processed output. Do not reuse the original solver gap or optimality certificate for a modified solution unless the modification is part of a certified solver process.

For solver-required tasks, prefer the solver-extracted incumbent as the final output. Use heuristics only for warm starts, incumbent construction, or allowed improvement steps, and keep the final report honest about what is certified.