HiGHS
HiGHS copied to clipboard
ERGO-Code
IPM reports feasible instance infeasible
Observe the following:
./highs --model_file neos-2987310-joes.mps --solver ipm
Running HiGHS 1.0.0 [date: 2021-04-26, git hash: cfe064e6]
Copyright (c) 2020 ERGO-Code under MIT licence terms
LP : neos-2987310-joes
Rows : 16250
Cols : 6133
Nonzeros : 220541
Presolve : Reductions: rows 16206(-44); columns 6092(-41); elements 220381(-160)
INFO : Solving the presolved LP
INFO : IPX model has 16206 rows, 6092 columns and 220381 nonzeros
Input
Number of variables: 6092
Number of free variables: 0
Number of constraints: 16206
Number of equality constraints: 0
Number of matrix entries: 220381
Matrix range: [1e+00, 4e+06]
RHS range: [1e+00, 5e+07]
Objective range: [8e+03, 2e+07]
Bounds range: [1e+00, 1e+00]
Preprocessing
Dualized model: yes
Number of dense columns: 0
Range of scaling factors: [9.77e-04, 5.12e+02]
IPX version 1.0
Interior Point Solve
Iter P.res D.res P.obj D.obj mu Time
0 1.46e+03 7.70e+03 2.06743857e+09 2.06801861e+09 1.14e+07 0s
1 7.09e+02 4.52e+03 2.54925859e+09 1.93212872e+09 7.67e+06 0s
2 5.74e+02 3.69e+03 3.46514337e+09 1.69765152e+09 6.31e+06 0s
3 2.38e+02 1.19e+03 3.32447130e+09 1.72138954e+09 2.17e+06 0s
4 1.51e+02 6.25e+02 2.94131530e+09 1.53751466e+09 1.19e+06 0s
5 1.10e+02 4.34e+02 2.55291686e+09 1.42878027e+09 8.59e+05 0s
6 8.38e+01 3.05e+02 2.24248319e+09 1.30972270e+09 6.27e+05 0s
7 6.86e+01 2.30e+02 2.02201226e+09 1.21810717e+09 4.92e+05 0s
8 5.25e+01 1.73e+02 1.75859636e+09 1.12728325e+09 3.89e+05 0s
9 4.28e+01 1.28e+02 1.58945859e+09 1.03561740e+09 3.05e+05 0s
10 3.37e+01 8.85e+01 1.42122032e+09 9.27215746e+08 2.28e+05 0s
11 2.72e+01 6.01e+01 1.29217912e+09 8.34189170e+08 1.67e+05 0s
12 2.11e+01 3.60e+01 1.16182703e+09 7.42447620e+08 1.10e+05 0s
13 1.53e+01 1.80e+01 1.03414116e+09 6.69078314e+08 6.33e+04 1s
14 7.90e+00 9.20e+00 8.53387015e+08 6.35872873e+08 3.47e+04 1s
15 2.08e+00 2.60e+00 7.11235476e+08 6.12503475e+08 1.21e+04 1s
Constructing starting basis...
16 4.49e-01 1.48e+00 6.57176174e+08 6.13106385e+08 7.06e+03 1s
17 1.22e-01 8.51e-01 6.38191846e+08 6.15764893e+08 4.12e+03 1s
18 6.91e-02 4.25e-01 6.33523788e+08 6.17996554e+08 2.30e+03 1s
19 5.68e-02 3.10e-01 6.32898280e+08 6.18119565e+08 1.90e+03 1s
20 5.07e-02 2.58e-01 6.32192487e+08 6.18214959e+08 1.71e+03 1s
21 4.95e-02 2.44e-01 6.32112881e+08 6.18132239e+08 1.67e+03 1s
22 3.83e-02 2.06e-01 6.30706786e+08 6.18220985e+08 1.55e+03 1s
23 3.69e-02 1.98e-01 6.30448839e+08 6.18139467e+08 1.55e+03 1s
24 3.28e-02 1.83e-01 6.30141744e+08 6.18071511e+08 1.51e+03 1s
25 2.90e-02 1.60e-01 6.29315596e+08 6.18081571e+08 1.42e+03 1s
26 2.80e-02 1.52e-01 6.29159045e+08 6.17979715e+08 1.39e+03 1s
27 2.59e-02 1.41e-01 6.28850533e+08 6.17916720e+08 1.37e+03 1s
28 2.46e-02 1.26e-01 6.28186988e+08 6.17916148e+08 1.28e+03 1s
29 2.36e-02 1.21e-01 6.27752281e+08 6.17789073e+08 1.27e+03 1s
30 2.14e-02 1.11e-01 6.27040111e+08 6.17615912e+08 1.24e+03 1s
31 2.06e-02 1.06e-01 6.26858712e+08 6.17468564e+08 1.23e+03 1s
32 1.79e-02 9.82e-02 6.26279112e+08 6.17233372e+08 1.23e+03 1s
33 1.74e-02 9.09e-02 6.25977657e+08 6.17055702e+08 1.18e+03 1s
34 1.65e-02 8.52e-02 6.25444229e+08 6.16948532e+08 1.16e+03 1s
35 1.60e-02 7.62e-02 6.25214333e+08 6.16566694e+08 1.10e+03 2s
36 1.54e-02 7.26e-02 6.24682905e+08 6.16527953e+08 1.08e+03 2s
37 1.50e-02 7.15e-02 6.24587091e+08 6.16416223e+08 1.09e+03 2s
38 1.43e-02 6.91e-02 6.24518245e+08 6.16216947e+08 1.08e+03 2s
39 1.25e-02 6.29e-02 6.23426693e+08 6.16006151e+08 1.05e+03 2s
40 1.21e-02 6.03e-02 6.23107968e+08 6.15791244e+08 1.03e+03 2s
41 1.17e-02 5.63e-02 6.22938651e+08 6.15498614e+08 1.01e+03 2s
42 1.09e-02 5.28e-02 6.22413384e+08 6.15282340e+08 9.93e+02 2s
43 1.07e-02 5.10e-02 6.22332833e+08 6.15078100e+08 9.88e+02 2s
44 9.63e-03 4.71e-02 6.21724877e+08 6.14836917e+08 9.76e+02 2s
45 9.29e-03 4.59e-02 6.21473070e+08 6.14716723e+08 9.75e+02 2s
46 8.96e-03 4.18e-02 6.21172462e+08 6.14438833e+08 9.33e+02 2s
47 8.42e-03 3.93e-02 6.20670330e+08 6.14230641e+08 9.25e+02 2s
48 7.95e-03 3.78e-02 6.20257972e+08 6.14056264e+08 9.28e+02 2s
49 7.64e-03 3.57e-02 6.19734028e+08 6.13862842e+08 9.12e+02 2s
50 7.46e-03 3.35e-02 6.19539428e+08 6.13543087e+08 8.91e+02 2s
51 7.22e-03 3.08e-02 6.19318623e+08 6.13116177e+08 8.62e+02 2s
52 6.86e-03 2.84e-02 6.19038030e+08 6.12764567e+08 8.41e+02 2s
Summary
Runtime: 2.03s
Status interior point solve: no progress
Status crossover: not run
WARNING: Ipx: Stopped
WARNING: Ipx: IPM no progress
WARNING: Ipx: Crossover not run
WARNING: No progress: primal objective value = -6.128e+08
WARNING: No progress: max absolute primal residual = 29.13
WARNING: No progress: max absolute dual residual = 45.24
Postsolve :
Time : 2.08
Time Pre : 0.03
Time PreLP : 2.05
Time PostLP: -1.00
For LP neos-2987310-joes: Presolve 0.03 ( 1%): Solve presolved LP 2.05 ( 98%)
Model status : Infeasible
Primal status : Not set
Dual status : Not set
Simplex iterations: 0
IPM iterations: 52
HiGHS run time : 2.08
$ ./highs --model_file neos-2987310-joes.mps --solver simplex
Running HiGHS 1.0.0 [date: 2021-04-26, git hash: cfe064e6]
Copyright (c) 2020 ERGO-Code under MIT licence terms
LP : neos-2987310-joes
Rows : 16250
Cols : 6133
Nonzeros : 220541
Presolve : Reductions: rows 16206(-44); columns 6092(-41); elements 220381(-160)
INFO : Solving the presolved LP
INFO : Scaling: Improvement factor is 2.903e+11 >= 1 so scale LP
INFO : Basis condition estimate of 1 is within the tolerance of 1e+14
INFO : Using dual simplex solver - serial
Iteration Objective Infeasibilities num(sum)
DuPh2 0 -7.3910262247e+09 Pr: 4321(2.10498e+07)
DuPh2 180 -1.6926206816e+09 Pr: 3679(4.62295e+06)
DuPh2 373 -9.0514943018e+08 Pr: 3691(1.88118e+06)
DuPh2 548 -6.3821779376e+08 Pr: 3523(791924)
DuPh2 788 -6.2389983921e+08 Pr: 3368(688053)
DuPh2 1218 -6.2389983870e+08 Pr: 2990(584629)
DuPh2 1678 -6.2314914810e+08 Pr: 2366(421750)
DuPh2 2166 -6.2314914759e+08 Pr: 1689(261174)
DuPh2 2672 -6.2246090565e+08 Pr: 951(110220)
DuPh2 3207 -6.2235564953e+08 Pr: 207(21019.7)
DuPh2 3532 -6.1270104566e+08 Pr: 62(19283.2)
DuPh2 3568 -6.1080298782e+08 Pr: 0(3.55271e-13)
DuPh2 3568 -6.1079746568e+08 Pr: 0(3.55271e-13)
INFO : Dual simplex iterations [Ph1 0; Ph2 3568; Pr 0] Total 3568
INFO : Solving the original LP from the solution after postsolve
INFO : Scaling: Improvement factor is 3.706e+10 >= 1 so scale LP
INFO : Basis condition estimate of 7.498e+04 is within the tolerance of 1e+14
Postsolve : 0
Time : 0.24
Time Pre : 0.04
Time PreLP : 0.16
Time PostLP: 0.02
For LP neos-2987310-joes: Presolve 0.04 ( 18%): Solve presolved LP 0.16 ( 69%): Solve original LP 0.02 ( 10%)
Model status : Optimal
Primal status : Feasible point
Dual status : Feasible point
Simplex iterations: 3568
Objective value : -6.1079746568e+08
HiGHS run time : 0.24
It looks like the culprit is https://github.com/ERGO-Code/HiGHS/blob/cfe064e60fdca9dc8008fd956fff04d7b562e210/src/ipm/IpxWrapper.h#L668-L672 and https://github.com/ERGO-Code/HiGHS/blob/cfe064e60fdca9dc8008fd956fff04d7b562e210/src/ipm/IpxWrapper.h#L501-L505.
IMO it's surprising for PRIMAL_INFEASIBLE to be used when there's no proof or certificate of infeasibility (up to numerical tolerances).
I can share the instance data, but it will take a few extra steps on my side. This is not the exact same neos-2987310-joes.mps instance as from miplib.
Indeed, it doesn't take much work with the simplex solver to tidy up such edge cases, particularly now I've got a primal simplex solver.
