ERGO-Code
Re-solving many times with primal simplex can lead to basis issues (rare occurrence)
Within a column generation setup, I've noticed that "primal simplex" can fail (with a warning) after adding columns and re-solving many times. This might be related to #1607.
Technically, it seems the issue is with cycling in the dual simplex code, when trying to restore primal feasibility. If I clear the solver and run again, it solves without issue. I'm happy to help debug/fix but would appreciate your thoughts.
I've managed to capture the issue for easy replication. See attached files (lp file renamed for attachment), code to replicate, and detailed logs below:
Highs m;
m.readModel("rmp3050.lp");
m.readBasis("basis3050.txt");
m.setOptionValue("simplex_strategy", 4);
m.setOptionValue("log_dev_level", 2);
m.run();
Running HiGHS 1.7.0 (git hash: 5626dd7b5): Copyright (c) 2024 HiGHS under MIT licence terms
Running with 12 thread(s)
Coefficient ranges:
Matrix [1e+00, 1e+00]
Cost [2e+01, 2e+03]
Bound [1e+00, 1e+00]
RHS [1e+00, 1e+00]
Solving LP without presolve, or with basis, or unconstrained
Using EKK primal simplex solver
primal-phase2-start
phase2CorrectPrimal: num / max / sum primal corrections = 35 / 0.00617098 / 0.00880487
Iteration Objective Infeasibilities num(sum)
PrPh2 0 3.2364315019e+03 Pr: 0(0); Du: 4(35.1711) No reason
PrPh2 151 3.2364304914e+03 Pr: 0(0); Du: 0(2.57228e-09) Possibly optimal
primal-phase-2-optimal
primal-cleanup-shift
PrPh2 151 3.2366945477e+03 Pr: 17(0.000314618); Du: 0(2.57228e-09) Perturbation cleanup
HEkkPrimal:: Using dual simplex to try to clean up num / max / sum = 17 / 3.4443e-05 / 0.000314618 primal infeasibilities
Dual feasible with unperturbed costs and num / max / sum primal infeasibilities of 17 / 3.4443e-05 / 0.000314618, so near-optimal
Near-optimal, so don't use cost perturbation
Basis is not logical, but near-optimal, so use Devex rather than compute steepest edge weights
dual-phase-2-start
DuPh2 151 3.2366945477e+03 Pr: 17(0.000314618); Du: 0(2.57228e-09) No reason
DuPh2 167 3.2366945811e+03 Pr: 18(57.5969); Du: 0(4.59636e-10) Possibly optimal
DuPh2 191 3.2366945824e+03 Pr: 5(3.00536); Du: 0(6.06059e-08) Possibly optimal
DuPh2 192 3.2366945823e+03 Pr: 5(2.99004); Du: 0(1.82287e-07) Possibly optimal
DuPh2 193 3.2366945824e+03 Pr: 5(3.00536); Du: 0(6.06133e-08) Possibly optimal
basis change (11985 out; 12235 in) is bad
DuPh2 195 3.2366945823e+03 Pr: 5(2.99004); Du: 0(1.82255e-07) Possibly optimal
basis change (12235 out; 11985 in) is bad
DuPh2 198 3.2366945824e+03 Pr: 5(3.00536); Du: 0(6.0604e-08) Possibly optimal
basis change (11985 out; 12235 in) is bad
basis change (13572 out; 12235 in) is bad
DuPh2 201 3.2366945823e+03 Pr: 5(2.99004); Du: 0(1.82269e-07) Possibly optimal
basis change (12235 out; 11985 in) is bad
basis change (15024 out; 12520 in) is bad
basis change (12520 out; 15024 in) is bad
DuPh2 213 3.2366945824e+03 Pr: 5(3.00536); Du: 0(2.90648e-07) Possibly optimal
DuPh2 214 3.2366945823e+03 Pr: 5(2.99004); Du: 0(3.11605e-07) Possibly optimal
DuPh2 215 3.2366945824e+03 Pr: 5(3.00536); Du: 0(2.90659e-07) Possibly optimal
basis change (11985 out; 12235 in) is bad
DuPh2 217 3.2366945823e+03 Pr: 5(2.99004); Du: 0(3.11588e-07) Possibly optimal
basis change (12235 out; 11985 in) is bad
DuPh2 220 3.2366945821e+03 Pr: 10(17.1186); Du: 0(2.45435e-07) Possibly optimal
DuPh2 223 3.2366945824e+03 Pr: 5(2.99004); Du: 0(3.61897e-07) Possibly optimal
basis change (12235 out; 11985 in) is bad
basis change (15024 out; 12520 in) is bad
DuPh2 225 3.2366945821e+03 Pr: 10(17.1186); Du: 0(2.45467e-07) Possibly optimal
basis change (11985 out; 10325 in) is bad
DuPh2 230 3.2366945824e+03 Pr: 5(2.99004); Du: 0(3.61744e-07) Possibly optimal
basis change (12235 out; 11985 in) is bad
basis change (12415 out; 11985 in) is bad
basis change (15024 out; 12520 in) is bad
DuPh2 236 3.2366945821e+03 Pr: 10(17.1186); Du: 0(1.03108e-07) Possibly optimal
DuPh2 240 3.2366945824e+03 Pr: 5(2.99004); Du: 0(1.7567e-07) Possibly optimal
DuPh2 243 3.2366945821e+03 Pr: 10(17.1186); Du: 0(1.03136e-07) Possibly optimal
DuPh2 246 3.2366945824e+03 Pr: 5(2.99004); Du: 0(2.4206e-07) Possibly optimal
basis change (12235 out; 11985 in) is bad
DuPh2 248 3.2366945821e+03 Pr: 10(17.1186); Du: 0(1.03206e-07) Possibly optimal
basis change (11985 out; 10325 in) is bad
basis change (12395 out; 12235 in) is bad
basis change (13868 out; 12235 in) is bad
DuPh2 255 3.2366945822e+03 Pr: 11(12.9497); Du: 0(1.40751e-07) Possibly optimal
DuPh2 257 3.2366945822e+03 Pr: 10(11.1186); Du: 0(1.44616e-07) Possibly optimal
basis change (13868 out; 12235 in) is bad
basis change (13572 out; 12235 in) is bad
DuPh2 260 3.2366945822e+03 Pr: 11(12.9497); Du: 0(1.21941e-07) Possibly optimal
basis change (12235 out; 13868 in) is bad
basis change (12395 out; 13868 in) is bad
basis change (13572 out; 13868 in) is bad
DuPh2 263 3.2366945822e+03 Pr: 9(10.969); Du: 0(9.62381e-08) Possibly optimal
DuPh2 269 3.2366945824e+03 Pr: 5(2.99004); Du: 0(1.61534e-07) Possibly optimal
DuPh2 271 3.2366945822e+03 Pr: 9(10.969); Du: 0(1.03549e-07) Possibly optimal
DuPh2 273 3.2366945824e+03 Pr: 5(2.99004); Du: 0(1.61695e-07) Possibly optimal
DuPh2 276 3.2366945822e+03 Pr: 9(10.969); Du: 0(1.03477e-07) Possibly optimal
DuPh2 278 3.2366945824e+03 Pr: 5(2.99004); Du: 0(1.61593e-07) Possibly optimal
basis change (12415 out; 11985 in) is bad
basis change (12235 out; 11985 in) is bad
basis change (15024 out; 12520 in) is bad
DuPh2 282 3.2366945822e+03 Pr: 9(10.969); Du: 0(1.03432e-07) Possibly optimal
basis change (11985 out; 10325 in) is bad
DuPh2 285 3.2366945822e+03 Pr: 9(11.7162); Du: 0(5.99903e-08) Possibly optimal
basis change (12235 out; 15024 in) is bad
DuPh2 288 3.2366945825e+03 Pr: 1(0.00596841); Du: 0(1.79795e-07) Possibly optimal
basis change (12235 out; 15024 in) is bad
HEkkDual::solve return of HighsStatus::Warning
HEkkPrimal::solve return of HighsStatus::Warning
Simplex iterations: DuPh2 137; PrPh2 151; Total 288
EKK primal simplex solver returns 1 primal and 0 dual infeasibilities: Status Unknown
solveLpSimplex return of HighsStatus::Warning
callSolveLp return of HighsStatus::Warning
Postsolve :
Time : 0.21
Time Pre : -1.00
Time PreLP : -1.00
Time PostLP: 0.21
For LP rmp3050: Solve original LP 0.21 ( 99%)
highsStatusFromHighsModelStatus return of HighsStatus::Warning
Model status : Unknown
Simplex iterations: 288
Objective value : 3.2366945825e+03
HiGHS run time : 0.21
We have the same (rare) issue in a column generation (CG) implementation. I cannot recreate the issue in the same way as @mathgeekcoder, i.e., when we save the LP and the basis and read them in, it solves to optimality, though a bit slower than solving the lp without the basis.
I have attached the lp's and bases from each iteration in the CG if that could be of any help: model_before_solve_attempt_0.bas.txt model_before_solve_attempt_0.lp.txt model_before_solve_attempt_1.bas.txt model_before_solve_attempt_1.lp.txt model_before_solve_attempt_2.bas.txt model_before_solve_attempt_2.lp.txt model_before_solve_attempt_3.bas.txt model_before_solve_attempt_3.lp.txt
When we run CG we get the following log in the iteration where the status is unknown:
Running with 4 thread(s) Coefficient ranges: Matrix [5e-01, 3e+01] Cost [2e+01, 5e+03] Bound [1e+00, 2e+04] RHS [5e-03, 1e+05] Solving LP without presolve, or with basis, or unconstrained Using EKK primal simplex solver primal-phase2-start phase2CorrectPrimal: num / max / sum primal corrections = 6 / 0.0161862 / 0.0191592 Iteration Objective Infeasibilities num(sum) PrPh2 0 4.0130453412e+08 Pr: 0(0); Du: 4060(5.1243e+06) No reason PrPh2 653 3.9142520371e+08 Pr: 0(0); Du: 6757(1.37068e+07) Synthetic clock PrPh2 1107 3.8703786901e+08 Pr: 0(0); Du: 9115(2.97322e+07) Synthetic clock PrPh2 1566 3.8476247960e+08 Pr: 0(0); Du: 8965(2.82489e+07) Synthetic clock PrPh2 2054 3.8280568315e+08 Pr: 0(0); Du: 7731(2.45611e+07) Synthetic clock PrPh2 2521 3.8063927074e+08 Pr: 0(0); Du: 6261(7.19747e+06) Synthetic clock PrPh2 2970 3.7920836638e+08 Pr: 0(0); Du: 6166(1.40003e+07) Synthetic clock PrPh2 3447 3.7797952397e+08 Pr: 0(0); Du: 12307(1.72895e+08) Synthetic clock PrPh2 3887 3.7670439213e+08 Pr: 0(0); Du: 12198(4.46632e+08) Synthetic clock PrPh2 4355 3.7502521611e+08 Pr: 0(0); Du: 10341(7.67802e+07) Synthetic clock PrPh2 4836 3.7388425965e+08 Pr: 0(0); Du: 7784(6.8658e+07) Synthetic clock PrPh2 5295 3.7314123675e+08 Pr: 0(0); Du: 4896(6.54011e+06) Synthetic clock PrPh2 5749 3.7248887786e+08 Pr: 0(0); Du: 6271(1.21945e+07) Synthetic clock PrPh2 6216 3.7197250553e+08 Pr: 0(0); Du: 9953(1.01514e+08) Synthetic clock PrPh2 6663 3.7174811394e+08 Pr: 0(0); Du: 5675(7.75033e+06) Synthetic clock PrPh2 7198 3.7147771951e+08 Pr: 0(0); Du: 4370(1.1008e+06) Synthetic clock PrPh2 7696 3.7129047082e+08 Pr: 0(0); Du: 3074(792636) Synthetic clock PrPh2 8313 3.7118722657e+08 Pr: 0(0); Du: 1434(60328.3) Synthetic clock PrPh2 9085 3.7111507806e+08 Pr: 0(0); Du: 585(6739.79) Synthetic clock PrPh2 9852 3.7107982783e+08 Pr: 0(0); Du: 0(1.41705e-08) Possibly optimal primal-phase-2-optimal primal-cleanup-shift PrPh2 9852 3.7107994079e+08 Pr: 3(0.00148201); Du: 0(1.41705e-08) Perturbation cleanup HEkkPrimal:: Using dual simplex to try to clean up num / max / sum = 3 / 0.00148125 / 0.00148201 primal infeasibilities Basis is not logical, so compute steepest edge weights dual-phase-2-start DuPh2 9852 3.7107994079e+08 Pr: 3(0.00148201); Du: 0(1.41705e-08) No reason DuPh2 9855 3.7107994079e+08 Pr: 1(4.39861e-07); Du: 0(1.54971e-08) Possibly optimal DuPh2 9856 3.7107994079e+08 Pr: 1(1.2153e-07); Du: 0(1.54292e-08) Possibly optimal basis change (113049 out; 113052 in) is bad HEkkDual::solve return of HighsStatus::Warning HEkkPrimal::solve return of HighsStatus::Warning Simplex iterations: DuPh2 4; PrPh2 9852; Total 9856 EKK primal simplex solver returns 1 primal and 0 dual infeasibilities: Status Unknown solveLpSimplex return of HighsStatus::Warning callSolveLp return of HighsStatus::Warning Postsolve : Time : 15.81 Time Pre : -1.00 Time PreLP : -1.00 Time PostLP: 15.81 For LP : Solve original LP 15.81 ( 99%) highsStatusFromHighsModelStatus return of HighsStatus::Warning Model status : Unknown Simplex iterations: 9856 Objective value : 3.7107994079e+08 HiGHS run time : 39.87
In both cases, the HiGHS simplex solver is unable to solve the LP because it has detected cycling. The simple solution is to force HiGHS to re-start from a logical basis - by calling h.clearSolver(). There will be a computational hit - depending on how much presolve reduces the LP - but, as you say, it's a rare occurrence
In both cases, the HiGHS simplex solver is unable to solve the LP because it has detected cycling. The simple solution is to force HiGHS to re-start from a logical basis - by calling h.clearSolver(). There will be a computational hit - depending on how much presolve reduces the LP - but, as you say, it's a rare occurrence
This is also how we get around it now. We check if the model status is unknown, and if it is, we clear the solver and run it one more time.