ERGO-Code
HiGHS Falsely Declares a MILP as Integer-Infeasible
I have been going through our set of internal industrial discrete and linear optimization problems (MILP) and have noticed that for the problem found in the LP and MPS files attached (re-typed as *.txt to allow attachment), that HiGHS declares the problem as integer-infeasible when in fact it is not.
This problem solves correctly by several other MILP solvers and when I add penalties or excursion variables to the problem and run with HiGHS it solves correctly and all of the penalty/excursion variables are zero (0.0) at the provably optimal solution.
In addition, if I turn the presolve "off", then HiGHS solves correctly.
FYI - these LP and MPS do not have penalty/excursion variables added. JFSC-IMF-QL.lp.txt JFSC-IMF-QL.mps.txt
The lp and mps files seem to be different. The .lp file seems to be infeasible regardless of presolve and also with other solvers. For the mps-File I can reproduce the behavior
Thanks, I am not sure why the LP and MPS files are different as I called the same HiGHS Highs_writeModel but with a different file of ".lp" and ".mps"
Perhaps this is another issue to raise but I will leave that up to your discretion as my software does not read LP nor MPS files.
I'll see if I can identify why the two files are different.
Thanks for doing this testing @jeffreydeankelly2
No problem, in fact HiGHS is working well even in our SLP algorithm for nonlinear problems so the 3 issues I have posted so far are very small compared to the number of internal industrial optimization test problems solved.
Thanks, that's good to hear. It's used in our SLP solver for a particular industrial problem, so I know how hard these can be numerically
Thanks, I am not sure why the LP and MPS files are different as I called the same HiGHS Highs_writeModel but with a different file of ".lp" and ".mps"
In the .lp file, values are written to 6sf, but in the MPS file it's about 14sf. They should be the same
@lgottwald In resolving the issues with the .lp file writer (see #938) I've found a very simple example where presolve claims false infeasibility. See small_mip.lp.txt with and without presolve. Note that this MIP is check/instances/small_mip.mps and has 2-sided bounds on a row. These are converted into separate 1-sided lower- and upper-bounded constraints when writing the .lp file so there are two parallel rows. Is this any help?
It happens with master
This issue has been tracked down to implied column bounds being incorrect after the aggregator is applied: the new terms introduced can lead to an increase (decrease) in the implied upper (lower) bound that isn't identified.
Strange that this hasn't caused more issues @lgottwald
The fix will take a little time