Improve log to encourage user to check infeasibilities and/or clear and resolve in particular cases

[joaquimg]

Backstory:

The following LP solution log came from a sequence of solves of LP's changing the RHS.

Running with 1 thread(s)
Coefficient ranges:
  Matrix [5e-03, 3e+02]
  Cost   [1e-02, 6e+03]
  Bound  [7e-01, 2e+05]
  RHS    [7e+03, 3e+06]
Solving LP without presolve, or with basis, or unconstrained
Using EKK dual simplex solver - serial
Cost perturbation for
   Initially have 112 nonzero costs ( 73%) with min / average / max = 0.04 / 5.60673 / 19.0728
   Perturbation column base = 9.53641e-06
   Perturbation row    base = 1e-12
dual-phase-2-start
Move down: cost shift = -3.20775e-05; objective change = -0.809378
Move down: cost shift = -3.59357e-05; objective change = -0.57497
Move down: cost shift = -2.75482e-05; objective change = -2.69135
Performed num / max / sum = 3 / 3.59357e-05 / 9.55613e-05 shift(s) for num / max / sum dual infeasibility of 3 / 3.58015e-05 / 9.51e-05; objective change = -4.0757
       Iteration        Objective     C_Aq R_Ep R_Ap S_Ed Infeasibilities num(sum)
DuPh2          0    -8.4563627127e+05   99   99   99   99 Pr: 5(3.35014e+06) No reason
       Iteration        Objective     C_Aq R_Ep R_Ap S_Ed     EnC     LvC     LvR        ThDu        ThPr        DlPr       NumCk          Aa Infeasibilities num(sum)
DuPh2          1    -6.6083739807e+05    2    4    3    3       5     116       0      -2.095    1.75e+05  -1.783e+05           0        -0.5 Pr: 4(2.06968e+06)
DuPh2          2    -5.8792286321e+05    2    4    3    2     112      13       5       1.048  -3.469e+04   7.094e+04           0          -2 Pr: 3(1.63452e+06)
DuPh2          3    -2.5820460993e+05    2    3    2    2      13      85       1     -0.2619  -3.032e+05  -1.272e+06           0           4 Pr: 2(591199)
DuPh2          4     2.0852099430e+05    1    2    2    2      17     152      15       -1.75  -1.901e+04  -4.941e+05           0       9.473 Pr: 2(31588.7)
DuPh2          5     2.0852136247e+05    1    2    2    1     116     112       5  -2.498e-05   1.474e+04  -1.474e+04           0          -1 Pr: 1(16851)
DuPh2          6     2.2885284625e+05    1    2    1    1      10      17      15      -1.207   9.691e+08  -1.685e+04    1.25e-12  -1.739e-05 Pr: 6(9.84903e+09)
DuPh2          7     2.4356773449e+05    1    1    1    1       8       6       6  -9.036e-06   6.401e+07  -1.937e+09   3.809e-13      -22.66 Pr: 6(1.31206e+09)
DuPh2          8     2.4512925833e+05    1    1    1    1      15       4       4  -1.223e-05  -9.272e+04  -1.277e+08   1.792e-16        1269 Pr: 2(90439.2)
DuPh2          9     2.4512930686e+05    1    1    1    1       7     164      11    6.33e-07   5.587e+04   7.666e+04           0       1.372 Pr: 1(6945.5)
DuPh2         10     2.4512935618e+05    1    1    1    1     164     169      14     7.1e-06  -7.791e+04        6946   1.868e-15    -0.08915 Pr: 0(0)
       Iteration        Objective     C_Aq R_Ep R_Ap S_Ed Infeasibilities num(sum)
DuPh2         10     2.4512935618e+05    1    1    1    1 Pr: 2(2.2212e-07) Possibly optimal
DuPh2         11     2.4512935618e+05    1    1    1    0     167     166      13   2.632e-05  -1.132e-07   1.132e-07   5.717e-13          -1 Pr: 0(0)
       Iteration        Objective     C_Aq R_Ep R_Ap S_Ed Infeasibilities num(sum)
DuPh2         11     2.4512935618e+05    1    1    1    0 Pr: 0(0) Possibly optimal
dual-phase-2-optimal
dual-cleanup-shift
       Iteration        Objective     C_Aq R_Ep R_Ap S_Ed Infeasibilities num(sum)
DuPh2         11     2.4508258200e+05    1    1    1    0 Pr: 0(0) Perturbation cleanup
problem-optimal
Simplex iterations: DuPh2 11; Total 11
EKK dual simplex solver returns 0 primal and 0 dual infeasibilities: Status Optimal
Have num/max/sum primal (1/2.9942e-07/2.9942e-07) and dual (0/0/0) unscaled infeasibilities
Using EKK dual simplex solver - serial
Dual feasible with unperturbed costs and num / max / sum primal infeasibilities of 1 / 2.9942e-07 / 2.9942e-07, so near-optimal
Near-optimal, so don't use cost perturbation
dual-phase-2-start
       Iteration        Objective     C_Aq R_Ep R_Ap S_Ed Infeasibilities num(sum)
DuPh2         11     2.4508258200e+05   99   99   99   99 Pr: 1(2.9942e-07) No reason
       Iteration        Objective     C_Aq R_Ep R_Ap S_Ed     EnC     LvC     LvR        ThDu        ThPr        DlPr       NumCk          Aa Infeasibilities num(sum)
DuPh2         12     2.4508258200e+05    2    3    2    2     166     167      13           0  -2.994e-07   2.994e-07           0          -1 Pr: 0(0)
       Iteration        Objective     C_Aq R_Ep R_Ap S_Ed Infeasibilities num(sum)
DuPh2         12     2.4508258200e+05    2    3    2    2 Pr: 2(6.53788e-07) Possibly optimal
DuPh2         13     2.4508258200e+05    2    2    2    2     167     168      16           0  -4.359e-07   4.359e-07   2.274e-13          -1 Pr: 0(0)
       Iteration        Objective     C_Aq R_Ep R_Ap S_Ed Infeasibilities num(sum)
DuPh2         13     2.4508258200e+05    2    2    2    2 Pr: 1(1.7928e-07) Possibly optimal
DuPh2         14     2.4508258200e+05    1    2    1    1     168     167      16           0  -1.793e-07   1.793e-07    2.22e-16          -1 Pr: 0(0)
       Iteration        Objective     C_Aq R_Ep R_Ap S_Ed Infeasibilities num(sum)
DuPh2         14     2.4508258200e+05    1    2    1    1 Pr: 2(6.04894e-07) Possibly optimal
 basis change (168 out; 167 in) is bad
 basis change (166 out; 167 in) is bad
HEkkDual::solve return of HighsStatus::Warning
Simplex iterations: DuPh2 3; Total 3
EKK dual simplex solver returns 2 primal and 0 dual infeasibilities: Status Unknown
solveLpSimplex return of HighsStatus::Warning
callSolveLp return of HighsStatus::Warning
Postsolve  :
Time       :     0.14
Time Pre   :    -1.00
Time PreLP :    -1.00
Time PostLP:     0.14
For LP                 : Solve original LP     0.14 (100%)
highsStatusFromHighsModelStatus return of HighsStatus::Warning
Model   status      : Unknown
Simplex   iterations: 14
Objective value     :  2.4508258200e+05
HiGHS run time      :          0.14

A rare event of cycling was spotted:

In iteration 13: Column 167 becomes basic, and column 168 becomes nonbasic
In Iteration 14: Column 168 becomes basic, and column 167 becomes nonbasic

The solution was to Highs::clearSolver, and then Highs::run again.

However, it is also important to state that HIGHS essentially solved the problem as the new solve leads to the same objective and the primal and dual infeasibilities are almost satisfied.

End of backstory

---

One suggestion that came up in private communications was:

Add some message (possibly combined with some documentation) that encourages the user to look at the maximum primal and dual infeasibility and decide whether they accept the problem as being solved OR re-solve after clearing the solver.

---

A follow-up question, related to JuMP would be:

Is it easy to query such infeasibilities or should the user query solutions and check themselves?

cc @odow