🔬 mipster_diag

Diagnose wrong MIP results — wrong-optimal and wrong-infeasible — in minutes.

mipster_diag is a standalone diagnostic binary shipped alongside mipster. When the solver produces a result that contradicts a certified objective value — claiming optimal at the wrong value, or declaring infeasibility on a feasible problem — mipster_diag automates the debugging process and pinpoints the root cause with clean, actionable output.

How it works

Usage

mipster_diag <problem.{mps,lp}[.gz]> -opt <value> [OPTIONS]

Worked example — enlight_hard

Scenario: A bug in node-level bound propagation caused MIPster to declare enlight_hard infeasible, even though the certified optimal is 37. The bug was triggered by the parameters nodeBoundProp on, nodeBoundPropMinDepth 2, nodeBoundPropDepthInterval 3.

Step 1 — run mipster_diag

mipster_diag enlight_hard.mps.gz -opt 37 \
    -p nodeBoundProp on \
    -p nodeBoundPropMinDepth 2 \
    -p nodeBoundPropDepthInterval 3

Step 2 — read the output

Step 3 — interpret

The three nodeBoundProp BAD FIXING lines are the smoking gun:

• Column 156 (y#9#2) is a general integer with optimal value 2. Bound propagation incorrectly classified it as binary and fixed it to [1,1].
• The BAD 156 1 <= 2 <= 1 line confirms the reference solution value (2) is outside the wrongly-fixed bounds.
• No bad row lines appear → row cuts are not involved. The bug is in bound propagation.

When the debugCuts pass is not conclusive

If no bad row or BAD FIXING lines appear, the bug may be in a feature that the debugger doesn't trace directly (e.g. branching, heuristics, preprocessing). Add -scan to run the 13-config sweep:

mipster_diag problem.mps -opt <N> -sol /tmp/ref.sol -scan

Each config result is printed on one line:

• OK — disabling this feature fixed the bug (the culprit).
• WRONG — same wrong result; feature is not the cause.
• not proven — timed out without proof; obj value still informative.
• LEAD ★ — found the certified objective without proof; strong signal.

Tips

Bug reproduces only with specific settings? Pass them via -p:

mipster_diag problem.mps -opt 37 \
    -p nodeBoundProp on \
    -p nodeBoundPropMinDepth 2 \
    -p nodeBoundPropDepthInterval 3

Hard instance that needs more time? Increase -time:

mipster_diag problem.mps -opt <N> -time 300

Already have a reference solution? Skip auto-obtain with -sol to save time. Obtain one with preprocessing disabled:

mipster problem.mps -preprocess off -solve -solu /tmp/ref.sol
mipster_diag problem.mps -opt <N> -sol /tmp/ref.sol

🔍 mipster_validate_sol

Validate MIP solution feasibility — bounds, integrality, constraints, and objective.

mipster_validate_sol checks whether a solution file (.sol) is truly feasible for a given MIP problem. It is useful for:

• Verifying that solutions saved from experiments are correct (no preprocessing bug, no rounding error).
• Pinpointing exactly which constraint, variable, or integrality condition is violated.
• Assessing how close to the feasibility boundary a "near-feasible" solution sits.

Usage

mipster_validate_sol <problem.{mps,lp}[.gz]> <solution.sol>

What is checked

The tool loads the problem model (without solving) and computes:

1. Variable bounds — lb ≤ x[i] ≤ ub for every variable
2. Integrality — |x[i] − round(x[i])| ≤ int_tol for integer/binary variables
3. Row activities — rowLB ≤ Ax ≤ rowUB for every constraint
4. Objective value — computed c·x vs. the value claimed in the .sol header

Default tolerances:

primal (bounds / constraints) = 1e-5 (scaled)
integrality                   = 1e-5
objective (relative)          = 1e-6

Worked example — air05

Solve and save a solution, then validate it:

mipster air05.mps.gz -preprocess off -solve -solu /tmp/air05.sol
mipster_validate_sol air05.mps.gz /tmp/air05.sol

Output for a valid solution:

mipster_validate_sol
  Problem:  air05.mps.gz
  Solution: /tmp/air05.sol

  Tolerances: primal=1e-05  integer=1e-05  objective=1e-06

  Model: 7195 variables (7195 integer),  426 constraints
  Solution file: 66 non-zero variables listed

  Claimed status: Optimal   claimed obj = 26374

RESULT: FEASIBLE ✓

  Bounds:       7195 variables — no violations
  Integrality:  7195 integer variables — no violations
  Constraints:  426 rows — no violations
  Objective:    computed=26374  claimed=26374  rel_delta=0.000e+00

─── CLOSEST TO TOLERANCE ────────────────────────────────────────
  Objective discrepancy:      rel_delta=0.000e+00

Output for an infeasible solution (example — one variable modified to 0.3):

RESULT: INFEASIBLE ✗

─── VIOLATIONS FOUND (6) ─────────────────────────────────────
  INTEG: col 2 (x#1#3)  val=0.3  nearest_int=0  error=3.000e-01
  ROW:   row 1 (inner_area_2)  activity=-0.7  bounds=[0, 0]  viol=7.000e-01 [BELOW LB]
  ROW:   row 64 (upper_border_1)  activity=-0.7  bounds=[0, 0]  viol=7.000e-01 [BELOW LB]
  ROW:   row 65 (upper_border_2)  activity=-0.7  bounds=[0, 0]  viol=7.000e-01 [BELOW LB]
  ROW:   row 66 (upper_border_3)  activity=-0.7  bounds=[0, 0]  viol=7.000e-01 [BELOW LB]
  OBJ:   computed=36.3  claimed=37  rel_delta=1.892e-02

Summary:
  Integrality violations:      1
  Constraint violations:       4
  Objective mismatch:          computed=36.3  claimed=37

Scanning experiment results

To validate all solutions saved by an experiment run (when solutions are saved with -solu), use a shell loop:

for sol in /path/to/experiment/*.sol; do
  inst=$(basename "$sol" .sol)
  result=$(mipster_validate_sol "$MIPSTER_INSTANCES/miplib/2017+spp/${inst}.mps.gz" "$sol")
  rc=$?
  if [[ $rc -ne 0 ]]; then
    echo "INFEASIBLE: $inst"
    echo "$result" | grep -E "VIOL|INTEG|ROW|OBJ:"
  fi
done