When primal simplex is optimal with bound shifts, avoid primal corrections when recomputing the primal values: return and use dual simplex to clean up

[shwhmmmam]

fail.mps.txt

triggers an assertion failure in HiGHS:

Running HiGHS 1.11.0 (git hash: 26b632af1): Copyright (c) 2025 HiGHS under MIT licence terms
Set option log_file to "HiGHS.log"
MIP  small has 11 rows; 9 cols; 84 nonzeros; 6 integer variables (0 binary)
Coefficient ranges:
  Matrix [3e-02, 5e+02]
  Cost   [2e+01, 3e+02]
  Bound  [1e+02, 1e+02]
  RHS    [2e+01, 7e+04]
Presolving model
10 rows, 9 cols, 83 nonzeros  0.001548s
10 rows, 9 cols, 83 nonzeros  0.003174s

Solving MIP model with:
   10 rows
   9 cols (0 binary, 6 integer, 0 implied int., 3 continuous, 0 domain fixed)
   83 nonzeros

Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
     H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
     I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
     z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
Src  Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   -102811         inf                  inf        0      0      0         0     0.1s
         0       0         0   0.00%   21580.316208    inf                  inf        0      0      0        11     0.1s
highs: /tmp/HiGHS/highs/lp_data/HighsInterface.cpp:2709: HighsStatus Highs::lpKktCheck(const std::string &): Assertion `info.num_complementarity_violations == 0' failed.
Aborted (core dumped)

[fwesselm]

The solution of an LP solved by the feasibility pump heuristic has one complementarity violation.

[jajhall]

Thanks, I'll look at this.

[jajhall]

It's a false positive, but gives me something to think about.

Was there a particular reason why you compiled with Debug or RelWithDebug?

[shwhmmmam]

No special reason, but debug sometimes help spot issues earlier.

[jajhall]

Note for @jajhall

The complementarity violation is due to a nonbasic variable being off its bound.

Specifically, row 5 is nonbasic, and has (primal / dual) residual (2.27295e-05 / 0.0117425) so complementarity violation = 2.669e-07

It's off its bound because a bound shift was performed in primal simplex phase 2 to accommodate an infeasibility when row 5 was basic. This bound shift is still present when optimality is declared. Surely this shift should be removed, and the basic primal values recomputed. If this yields primal infeasibilities, then dual simplex should be used to clean up (since the basis remains dual feasible).

Code exposing this complementarity violation is in fix-2643

In practice, such primal infeasibilities will be small, so unlikely to affect the MIP solver.

Duals of basic variables are set to the residual of $B^T\pi-c_B$ (so could lead to complementarity violations)

Would be better to set duals of basic variables to be set to zero so that the residual in the dual equations for basic variables is nonzero (so cannot lead to complementarity violations).

[jajhall]

Note for @jajhall

In HEkkPrimal::rebuild(), correctPrimal() is always called in Phase 2. This can shift bounds to remain in Phase 2. However, when dual feasible - ie possibly optimal - this shouldn't be done. The primal simplex solver should return with primal infeasibilities - to be cleaned up by dual simplex phase 2.

Note that for 2643.mps, this feature isn't exhibited. Hence, now that the shift that caused the complementarity violation is cleaned up in HEkkPrimal::rebuild(), the original issue of @shwhmmmam is fixed. However, the issues it exposed remain. Hence the change of subject for the issue.

However, for the 2643.mps relaxation solve that yielded the issue, when the scaling is removed a small primal infeasibility is created. Strangely, primal simplex is still used since options_.simplex_strategy is now 4. Presumably this was set to 4 because the initial basis was primal feasible. Surely the decision of what simplex solver to use should be revisited when considering the need to tidy up infeasibilities created when scaling is removed.

[jajhall]

Note for @jajhall

So options_.simplex_strategy is restored (to 0). Have to track down when it's set to 4