Suggestion/Question: Use primal simplex for IPM crossover cleanup?

[Wronskode]

​Hi everyone,
​I was looking into the IPM crossover logic and noticed that it performs a pushdual followed by a pushprimal.
​If my understanding is correct, finishing with the pushprimal phase should leave the resulting basis in a primal feasible state (according to the asserts in PushAll). However, it looks like the final cleanup is currently being routed to the dual simplex.
​Since the basis is already primal feasible (but potentially dual infeasible at this stage), wouldn't it make more sense and be more efficient to run the primal simplex for the cleanup? If the dual simplex is called instead, it likely has to trigger a Phase 1 to handle the dual infeasibilities, which seems to defeat the purpose of establishing primal feasibility right before it.
​Let me know if I'm missing something about the internal solver state after those push phases

[jajhall]

Where are you seeing this "final cleanup is currently being routed to the dual simplex"?

Within the IPM crossover, there's no call to the HiGHS dual simplex solver. What you may be seeing is that, after IPM+crossover, a simplex clean-up will be performed if optimality is unknown, or if the LP has been identified as being unbounded or infeasible (and simplex is being used to distinguish the outcomes). However, I'd expect that if the basis is primal (dual) feasible, then primal (dual) simplex is used to clean up.

Do you have anything to add @filikat?

[filikat]

Not really. I agree that the clean up with simplex only happens outside of the IPMs, and only if crossover is allowed.

[Wronskode]

Thanks for the details! You're right that there might not be a hardcoded call within the crossover loop itself, but the clean-up fallback definitely routes to the dual simplex.

Here is the exact output I get when running s100.mps from miplib (with solve_relaxation = true, solver = ipx, run_crossover = on):

Running HiGHS 1.14.0 (git hash: 39edd92d13): Copyright (c) 2026 under MIT licence terms
...
  80   -1.71096721e-01  -1.71096733e-01   1.17e-14   1.12e-17  1.01e-08      43.3
  81*  -1.71096725e-01  -1.71096734e-01   1.76e-14   1.12e-17  7.12e-09      43.4
  82*  -1.71096731e-01  -1.71096732e-01   5.83e-15   1.12e-17  3.98e-10      43.5
  83*  -1.71096732e-01  -1.71096732e-01   2.05e-14   9.49e-18  3.95e-11      43.7
  84*  -1.71096732e-01  -1.71096732e-01   3.90e-14   9.49e-18  4.22e-12      43.8
  85*  -1.71096732e-01  -1.71096732e-01   3.23e-13   1.04e-17  1.21e-13      43.8
Running crossover as requested
    Primal residual before push phase:                  4.26e-09
    Dual residual before push phase:                    3.14e-08
    Number of dual pushes required:                     13838
    Number of primal pushes required:                   889
Summary
    Runtime:                                            44.01s
    Status interior point solve:                        imprecise
    Status crossover:                                   imprecise
    objective value:                                    -1.71096732e-01
    interior solution primal residual (abs/rel):        5.18e-08 / 5.71e-13
    interior solution dual residual (abs/rel):          1.00e-06 / 9.95e-07
    interior solution objective gap (abs/rel):          3.88e-08 / 3.31e-08
    basic solution primal infeasibility:                3.48e-15
    basic solution dual infeasibility:                  1.06e-05
WARNING: Ipx: IPM       imprecise
WARNING: Ipx: Crossover imprecise
WARNING: Unwelcome IPX status of Unknown: basis is valid; solution is valid; run_crossover is "on"
WARNING: IPM solution is imprecise, so clean up with simplex
Using dual simplex solver
  Iteration        Objective     Infeasibilities num(sum)
          0     0.0000000000e+00 Ph1: 0(0) 44.1s
       7767    -1.7109442138e-01 Pr: 171(3.3411); Du: 0(1.75959e-05) 49.4s
       9887    -1.7109412850e-01 Pr: 0(0); Du: 0(1.93671e-05) 54.9s
       9887    -1.7109675893e-01 Pr: 0(0); Du: 0(2.23487e-12) 54.9s

Performed postsolve
Solving the original LP from the solution after postsolve
WARNING: Solution optimality conditions
    max           inf                                  integrality violations     (tolerance = 1e-06)
num/max      0 /        0 (relative      0 /        0) primal infeasibilities     (tolerance = 1e-06)
num/max      0 / 4.94e-17 (relative      0 / 4.92e-17)   dual infeasibilities     (tolerance = 1e-07)
                                         0 / 1.65e-16  P-D objective error        (tolerance = 1e-07)

Model name          : s100
Model status        : Optimal
Simplex   iterations: 9887
IPM       iterations: 85
Crossover iterations: 2716
Objective value     : -1.7109675893e-01
P-D objective error :  1.6543412106e-16

As you can see, the basis after crossover is perfectly primal feasible (3.48e-15) but dual infeasible (1.06e-05). Yet, the fallback clean-up explicitly prints Using dual simplex solver.

[jajhall]

As you can see, the basis after crossover is perfectly primal feasible (3.48e-15) but dual infeasible (1.06e-05). Yet, the fallback clean-up explicitly prints Using dual simplex solver.

Yes, but the first dual simplex logging shows zero dual infeasibilities at the start of Phase 1 - for some reason recomputing the primal and dual solution from the crossover basis yields a dual feasible point - so there's no inefficiency

[Wronskode]

Thanks, that makes sense :)

[Wronskode]

Hi @jajhall , I just tested with primal_strategy=4 to force primal simplex as cleanup
Here's my results on this specific instance
s100_primal.log
s100_default.log

As we can see the cleanup faster with primal simplex (47s / 56s) and makes 1037 iterations instead of 9887.

I can do more benchmarks if you think it's usefull.