ERGO-Code
BUG: IPX w/out presolve fail on easy problem
When solve the following problem the model gets unset (presumably from an error during the course of optimization). Any insights into why it might be failing?
c [-1, 1] (MIN)
A = [[1, 0], [0, 1]]
lhs = [-inf, 2]
rhs = [1, 2]
lb = [1, 2]
ub = [1, 2]
The solution should be trivial, but simplex with presolve returns unset model as well as any variant of ipm. The only thing that solves this is simplex with presolve turned off.
This issue was resolved by solution in #282 , update to C API was all it took
I've just spotted that IPX says that this problem is infeasible when HiGHS is run without presolve. The same happens with the vanilla IPX from Lukas' repo @galabovaa so I've created issue an Issue for him! https://github.com/ERGO-Code/ipx/issues/1
I can replicate the issue:
- solver: ipm
- presolve: off
MPS file:
NAME
ROWS
N COST
L row0
E row1
COLUMNS
col0 COST -1
col0 row0 1
col1 COST 1
col1 row1 1
RHS
RHS_V row0 -inf
RHS_V row1 2
RANGES
RANGE row0 -inf
BOUNDS
FX BOUND col0 1
FX BOUND col1 2
ENDATA
I'm going to try to get this included as a unit test in scipy so we can make sure we catch any breakages in the future, thanks for noticing @jajhall !
I can replicate the issue:
* solver: ipm * presolve: offMPS file:
NAME ROWS N COST L row0 E row1 COLUMNS col0 COST -1 col0 row0 1 col1 COST 1 col1 row1 1 RHS RHS_V row0 -inf RHS_V row1 2 RANGES RANGE row0 -inf BOUNDS FX BOUND col0 1 FX BOUND col1 2 ENDATA
This isn't the same LP, as it defines an upper bound of -inf on row 0. [HiGHS and Clp won't read it, and Gurobi and Soplex say that it's infeasible]. It's the LHS of the L-row that's -inf, and that's implied by it being an L-row. You shouldn't have to use "inf" in an MPS file, anyway. The LP we were discussing originally is defined by issue280.mps.txt
I'll prompt Lukas to consider the IPX issue
Interesting that the MPS was generated incorrectly. I have a wrapper I wrote over writeMPS that I used to generate it, so the output is from writeMPS. I'll take a look and see if the issue is with input passed through by the wrapper
Interesting. I should observe that there's no check in writeMPS that "Inf" isn't being written out. It's just an assertion that it's possible in principle. Looking at the code, if you set the upper bound to anything less than -1e20 it will be stored internally as -Inf so, unless the lower bound were also (stored as) -Inf [in which case it would be an E row with RHS=-Inf] it would be an L row with RHS -Inf and range -Inf
Note, in passing, HiGHS is now using std::numeric_limits
With the MPS file that you provided I can also replicate the issue with IPX without presolve
Sure - it was created with writeMPS from the unit test check/TestSpecialLps.cpp (issue280) where I hard-code your example.
I believe the issue may be in basis.cc (see here).
The value of delta_obj is calculated as 2 in the example we are testing which seems to be unreasonably high. It is also being calculated in a different way the only other instance of delta_obj, so I suspect there may be a bug here? Again, I am taking stabs in the dark, but hopefully this helps localize the issue.
When I comment out this line (i.e., force ipx to think the rows are consistent):
info->rows_inconsistent = true;
then the correct answer is produced (optimal value with obj value of 1).
Can replicate on current master still, here's basic console output:
Running HiGHS 1.1.1 [date: 2021-12-19, git hash: ab302f1c1-dirty]
Copyright (c) 2021 ERGO-Code under MIT licence terms
LP issue280 has 2 rows; 2 cols; 2 nonzeros
Solving LP without presolve or with basis
IPX model has 2 rows, 2 columns and 2 nonzeros
Input
Number of variables: 2
Number of free variables: 0
Number of constraints: 2
Number of equality constraints: 1
Number of matrix entries: 2
Matrix range: [1e+00, 1e+00]
RHS range: [1e+00, 2e+00]
Objective range: [1e+00, 1e+00]
Bounds range: [1e+00, 2e+00]
Preprocessing
Dualized model: no
Number of dense columns: 0
Range of scaling factors: [1.00e+00, 1.00e+00]
IPX version 1.0
Interior Point Solve
Iter P.res D.res P.obj D.obj mu Time
0 1.50e+00 2.07e+00 1.00000000e+00 1.00000000e+00 3.21e+00 0s
1 7.39e-02 2.07e-06 1.06812342e+00 1.00000000e+00 1.65e-01 0s
2 7.39e-08 2.07e-12 1.00000007e+00 1.00000000e+00 1.65e-07 0s
3* 7.39e-14 0.00e+00 1.00000000e+00 1.00000000e+00 1.65e-13 0s
Constructing starting basis...
Summary
Runtime: 0.00s
Status interior point solve: primal infeas
Status crossover: not run
WARNING: Ipx: IPM primal infeasible
WARNING: Ipx: Crossover not run
Model status : Infeasible
IPM iterations: 3
Objective value : 1.0000000000e+00
HiGHS run time : 0.00
This certainly still happens with the IPM solver - and I can't see us getting it fixed, although I expect to be doing more with the Interior point solver myself so maybe I'll come back to your suggestion I guess it's due to the fixed variables. However, since presolve is performed by default, and will remove all fixed variables, it's not something that will happen for a general user.
The title of the issue refers to simplex, but I can't see any problem. Even with presolve=off, the simplex solvers aren't used since the logical basis is optimal.
The title of the issue refers to simplex, but I can't see any problem. Even with presolve=off, the simplex solvers aren't used since the logical basis is optimal.
Ah -- I see that now too. Back in 2020 the dual simplex solver must have had the same issue but is now resolved. It's just IPX that has this issue now. I'll edit the title