HiPO: a failed IPX refinement restart discards a near-optimal HiPO result as "Internal error" / Solve error

[spoorendonk]

Versions: reproduces on v1.14.0, v1.15.1 (04024d701f) and master @ 73cac48c53 (2026-08-19), all built with -DHIPO=ON. Linux x86_64, gcc 14.2, CMake 4.4.

Summary

On the LP below (gist), HiPO converges to a near-optimal interior point (gap 3.75e-09, pinf 1.67e-07), then stagnates and ends its IPM with kStatusNoProgress. That triggers the IPX refinement restart in Solver::refineWithIpx(). IPX cannot build a starting basis from that point and returns IPX_STATUS_failed after 0 iterations. refineWithIpx() then unconditionally overwrites HiPO's status with the IPX status, so the whole solve is reported as Hipo: Internal error / Model status: Solve error (CLI exit 255) — even though HiPO's own point is essentially optimal and every other route (--solver simplex, or hipo with run_crossover=off) solves the model to Optimal.

Reproduction

LP: hipo_ipx_refine_failure.mps (3.4 MB, in this gist together with the patch and a repro script) — 4601 rows, 9601 cols, 102809 nonzeros; costs in [2, 1e6], all matrix entries 1, RHS in [5e-4, 1]. It is a column-generation restricted master (min-cost multicommodity flow, path formulation) whose wide cost range comes from penalty columns.

highs --solver hipo    hipo_ipx_refine_failure.mps   # Solve error, exit 255
highs --solver ipm     hipo_ipx_refine_failure.mps   # same (routes to HiPO)
highs --solver simplex hipo_ipx_refine_failure.mps   # Optimal, 3.0750411511e+07
highs --solver hipo --run_crossover off hipo_ipx_refine_failure.mps   # Optimal, 3.0750411760e+07 (HiPO alone converges)

Log of the failing run (v1.15.1, default options), trimmed:

   69   3.07504114e+07   3.07504115e+07   1.67e-07   7.84e-14  3.75e-09     5.7
   70   3.07504114e+07   3.07504115e+07   1.67e-07   7.84e-14  3.75e-09     5.8
   71   3.07504114e+07   3.07504115e+07   1.67e-07   7.84e-14  3.75e-09     5.9
Restarting with IPX
...
Interior point solve
 Using starting point provided by user. Skipping initial iterations.
 Constructing starting basis...
 Iter       primal obj         dual obj       pinf       dinf       gap      time
Summary
    Status interior point solve:                        failed
    Status crossover:                                   not run
IPX reports: ipm failed
Summary
Status:                         internal error
HiPO iterations:                71
IPX iterations:                 0
ERROR:   Hipo: Internal error
Model status        : Solve error

Where it happens

highs/ipm/hipo/ipm/Solver.cpp, Solver::refineWithIpx() (v1.15.1 lines 287–320):

  ipx_lps_.Solve();
  info_.ipx_used = true;
  info_.ipx_info = ipx_lps_.GetInfo();

  // Convert between ipx and hipo status
  info_.status = IpxToHipoStatus(info_.ipx_info.status_ipm);   // <-- clobbers HiPO's status

• HiPO's checkBadIter() sets kStatusNoProgress when it stagnates and checkTerminationKkt() rejects the point (here pinf 1.67e-07 is just over the 1e-07 feasibility tolerance).
• statusNeedsRefinement() is true for kStatusNoProgress/kStatusImprecise, so IPX is restarted from HiPO's iterate (prepareIpx() → LoadIPMStartingPoint).
• IPX's BuildStartingBasis() fails (StartingBasis sets errflag, lp_solver.cc → status_ipm = IPX_STATUS_failed) with 0 IPM iterations.
• IpxToHipoStatus(IPX_STATUS_failed) = kStatusError, which replaces kStatusNoProgress. In IpxWrapper.cpp solveLpHipo(), reportHipoStatus() turns kStatusError into Hipo: Internal error and HighsStatus::kError / kSolveError, and the solution is never extracted.

The IPX restart is an optional improvement step. When it fails, the result that existed before it should survive: with kStatusNoProgress kept, solveLpHipo() goes down the hipo.stopped() branch, extracts the interior solution, and reports kUnknown with a warning — from which HiGHS already recovers on its own (run_crossover=on → "IPM solution is imprecise, so clean up with simplex" → Optimal in 2899 simplex iterations).

Proposed fix

Remember the pre-refinement status and keep it when IPX's IPM fails but HiPO had already stopped with a non-failed status. Also reset ipx_used, so getInteriorSolution() returns HiPO's own iterate (it_) rather than asking IPX for the iterate of a failed run (in this instance IPX fails before its first iteration, so its iterate is the loaded starting point and both give the same answer, but a failure after k>0 IPX iterations would otherwise hand back a partially-iterated IPX point under HiPO's status).

--- a/highs/ipm/hipo/ipm/Solver.cpp
+++ b/highs/ipm/hipo/ipm/Solver.cpp
@@ void Solver::refineWithIpx() {
   if (checkInterrupt()) return;

+  // Pre-refinement HiPO status. If the optional IPX refinement step fails, we
+  // fall back to this rather than discarding a usable HiPO result.
+  const Status pre_refine_status = info_.status;
+
   if (statusNeedsRefinement() && refinementIsOn()) {
     logger_.print("\nRestarting with IPX\n");
   } else if (statusAllowsCrossover() && crossoverIsOn()) {
@@
   // Convert between ipx and hipo status
   info_.status = IpxToHipoStatus(info_.ipx_info.status_ipm);

+  // A failed IPX refinement must not turn a usable HiPO result into a hard
+  // error: when IPX's IPM fails but HiPO already stopped with a non-failed
+  // status (e.g. kStatusNoProgress / kStatusImprecise), keep the HiPO status
+  // instead of the IPX failure. Without this, a near-optimal HiPO point is
+  // reported as "internal error" / Solve error.
+  const bool ipx_failed = info_.status >= kStatusFailed &&
+                          info_.status < kStatusSolved;
+  const bool hipo_was_usable = pre_refine_status < kStatusFailed ||
+                               pre_refine_status >= kStatusSolved;
+  if (ipx_failed && hipo_was_usable) {
+    info_.status = pre_refine_status;
+    info_.ipx_used = false;  // report HiPO's iterate, not IPX's failed one
+  }
+
   std::stringstream log_stream;
   log_stream << "IPX reports: ipm "
              << ipx::StatusString(info_.ipx_info.status_ipm);

With the patch (v1.15.1), default options:

IPX reports: ipm failed
Status:                         no progress
WARNING: Hipo: No progress
WARNING: No progress: primal objective value       =   3.075e+07
WARNING: No progress: max absolute primal residual =   3.348e-07
WARNING: No progress: max absolute   dual residual =    2.81e-06
WARNING: Unwelcome IPX status of Unknown: basis is not valid; solution is valid; run_crossover is "on"
WARNING: IPM solution is imprecise, so clean up with simplex
Model status        : Optimal
Simplex   iterations: 2899
Objective value     :  3.0750411511e+07

--solver ipm behaves the same; --solver simplex and --run_crossover off are unchanged.

We have been carrying the status-restore part of this patch (without the ipx_used line) against v1.14.0 and v1.15.1 in a column-generation solver where the master LP is re-solved every iteration with HiPO; before it, this failure mode aborted otherwise healthy runs. I understand solver-core PRs aren't taken, so the diff is offered as a suggestion only — happy to test whatever fix you land on this LP and on our CG workloads.

Files

All in https://gist.github.com/spoorendonk/c5dac7bc832d69640cba504b976cf434:

• hipo_ipx_refine_failure.mps (3.4 MB, md5 5c87478a06c9c1729f0cb9099a66619c)
• highs-hipo-refine-status.patch (the diff above, against v1.15.1; applies to master)
• repro.sh — HIGHS=/path/to/highs ./repro.sh hipo_ipx_refine_failure.mps runs the four commands above

Disclosure: the diagnosis and the suggested diff were worked out with AI assistance (Claude); every result quoted above comes from running the listed HiGHS builds on the file.

[jajhall]

Thanks @spoorendonk, let's see what @filikat makes of this.

[filikat]

Thanks, this makes sense. I noticed this behaviour in some rare cases and indeed HiPO should keep the previous status if IPX fails completely. I will look at this when I'm fully back to work, in 2 weeks.