Repository navigation
Wrong optimal objective reported with presolve enabled #3452
Description
What version of HiGHS and what language are you using?
Release 1.15.1 and branch latest (95bd9c8).
Using the standalone C++ command-line executable.
Which solver are you using (e.g. LP, MIP, QP)
MIP
What operating system (Linux, Windows, ...) and version?
Debian GNU/Linux 12, x86-64
What did you do?
Ran the attached model test.mps.txt
highs test.mps --threads 1 --time_limit 120
What did you expect to see
Optimal, objective ≈ 8104.99914
What did you see instead?
Optimal, objective 12924.9999939 (primal and dual bound both 12924.9999939, gap 0%)
Disabling presolve returns an optimal solution with objective approximately 8104.99914364:
highs test.mps --threads 1 --time_limit 120 --presolve off
The attached witness.txt lists a verified feasible solution with objective approximately 8104.99914364, disproving the reported optimality claim. Variables not listed are zero.
Anything else we should know about your project / environment
On 95bd9c8, turning off only the DualFixing presolve rule (presolve_rule_off = 131072) also gives 8104.99914364; on 1.15.1 it does not.
Activity
fwesselm commentedon Oct 22, 2026
I will have a look.
fwesselm commentedon Oct 22, 2026
@Opt-Mucca, I think I need your help here, our friend "analytic center computation" is back:
HighsMipSolverData::startAnalyticCenterComputationsolves the presolved LP with zero costs using IPX withrun_centring = trueandrun_crossover = off.status_ipm = IPX_STATUS_no_progress), so it never attempts the centring steps.IpxWrapperreturns model statuskUnknown.lpKktCheckthen upgrades the status tokOptimal, because the point is primal and dual feasible (zero objective).HighsMipSolverData::finishAnalyticCenterComputationonly checksanalyticCenterStatus == HighsModelStatus::kOptimal. Columnx2365is at its upper bound293000(a bound set by presolve), and the code sets its lower bound to293000. The global domain becomes infeasible, the root node is pruned, and the incumbent found earlier by a heuristic (with objective12924.99999) is reported as optimal.I think losing the status
IPX_STATUS_no_progressis the culprit here.Opt-Mucca commentedon Oct 22, 2026
@fwesselm I was just exploring the same bug in the other issue! Nice to know we got to the same conclusion
Edit: Agree on losing the status being the likely culprit.
odow commentedon Oct 29, 2026
Closed by #3456