CBC MILP Solver returns "Infeasible" status, but lpsolve in R gives "feasible" about cbc

[jjhforrest]

Does not look like an error in Cbc - but in the pulp interface. Have you tried a more recent version of pulp?

Running cbc 2.10.3 on python_1.mps looks fine

bin/cbc /tmp/python_1.mps -ratiogap 0.05 -allowablegap 0.05 -maximize -solve
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Jun 14 2019

command line - ../bin/cbc /tmp/eeeeee/python_1.mps -ratiogap 0.05 -allowablegap 0.05 -maximize -solve (default strategy 1)
At line 2 NAME Optimization_Problem
At line 3 ROWS
At line 378 COLUMNS
At line 2851 RHS
At line 3225 BOUNDS
At line 3638 ENDATA
Problem Optimization_Problem has 373 rows, 412 columns and 2060 elements
Coin0008I Optimization_Problem read with 0 errors
ratioGap was changed from 0 to 0.05
allowableGap was changed from 1e-10 to 0.05
Presolve 195 (-178) rows, 289 (-123) columns and 1031 (-1029) elements
0 Obj 31561.643 Primal inf 146.96956 (107) Dual inf 81713.138 (289)
78 Obj 113919.69 Primal inf 7.1017596 (21)
99 Obj 112268.35
Optimal - objective value 112268.35
After Postsolve, objective 112268.35, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 112268.3456 - 99 iterations time 0.002, Presolve 0.00
Total time (CPU seconds): 0.01 (Wallclock seconds): 0.01

[jjhforrest]

I have tried several solvers which all say infeasible. Take Infeasible2.mps - if I look at rows _C29 and _C585

G _C29 L _C585
x1335 _C29 6.000000000000e+00 x1335 _C585 6.000000000000e+00
x1336 _C29 1.100000000000e+01 x1336 _C585 1.100000000000e+01
x2208 _C29 2.920000000000e+02 x2208 _C585 2.920000000000e+02
x2209 _C29 4.180000000000e+02 x2209 _C585 4.180000000000e+02
x2758 _C29 7.000000000000e+00 x2758 _C585 7.000000000000e+00
x2759 _C29 3.000000000000e+00 x2759 _C585 3.000000000000e+00
x306 _C29 1.800000000000e+01 x306 _C585 1.800000000000e+01
x307 _C29 1.200000000000e+01 x307 _C585 1.200000000000e+01
x43 _C29 3.400000000000e+01 x43 _C585 3.400000000000e+01
x44 _C29 8.000000000000e+00 x44 _C585 8.000000000000e+00
x767 _C29 1.000000000000e+01 x767 _C585 1.000000000000e+01
x898 _C29 7.000000000000e+00 x898 _C585 7.000000000000e+00
x899 _C29 7.000000000000e+00 x899 _C585 7.000000000000e+00
RHS _C29 7.360000000000e+02 RHS _C585 7.100000000000e+02
The two rows are identical but _C29 says >= 736 while _C585 says <= 710
which is obviously infeasible

[jjhforrest]

I know very little about pulp, but I downloaded pulp.

Ran it from pulp as

var2,prob2=pulp.LpProblem.fromMPS("python_1.mps",pulp.LpMaximize)
prob2.solve()
and it still looks fine

Output -
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019

command line - /home/john/pulp/pulp/apis/../solverdir/cbc/linux/64/cbc /tmp/c3527ebbb1414f418780894de32fc856-pulp.mps max basisin /tmp/lp.bas timeMode elapsed branch basisout /tmp/lp.bas printingOptions all solution /tmp/c3527ebbb1414f418780894de32fc856-pulp.sol (default strategy 1)
At line 2 NAME MODEL
At line 3 ROWS
At line 378 COLUMNS
At line 2851 RHS
At line 3225 BOUNDS
At line 3638 ENDATA
Problem MODEL has 373 rows, 412 columns and 2060 elements
Coin0008I MODEL read with 0 errors
At line 1 NAME MODEL VALUES
At line 255 ENDATA
Option for timeMode changed from cpu to elapsed
Presolve 195 (-178) rows, 289 (-123) columns and 1031 (-1029) elements
0 Obj 59981.313 Primal inf 3.3289825 (3) Dual inf 20884.355 (253)
0 Obj 59981.313 Primal inf 3.3289825 (3) Dual inf 9.6897901e+10 (246)
110 Obj 105036.31 Dual inf 7632.5281 (129)
249 Obj 112268.35
Optimal - objective value 112268.35
After Postsolve, objective 112268.35, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 112268.3456 - 249 iterations time 0.002, Presolve 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.01 (Wallclock seconds): 0.01

1

[jjhforrest]

It seems to me that fromMPS is broken. If I do writeMPS on a small miplib problem like enigma, I can see that some of RHS values are missing. If I edit file so that only one RHS value per line it works. With MARKER INTORG in file pulp thinks problem is integer - if BV in bounds then it thinks it is a continuous problem.

[jjhforrest]

Other solvers say infeasible. On Infeasible2.mps clp with loglevel 3 gives

Problem is infeasible due to row 584, -1.797693134862316e+308 710
and debugging gave other row

[tle4336]

@jjhforrest Thank you very much for your quick reply, Dr. Forrest. My pulp version is 2.7.0, which is the latest one I believe. Could you retry the .mp file above without changing the ratiogap and allowablegap (so, let's switch them back to their default values)? I was searching on this github exhaustively to try fixing the above issue myself, but the pulp.PULP_CBC_CMD() does not give options to change either primalTolerance or dualTolerance, and I have no idea what else to try.

One minor information - I ran cbc via the python code in Pycharm, not via the command line option like you did (I don't know how to run it through command line in Pycharm though).

[tle4336]

@jjhforrest Thank you so much. It is indeed weird, because I replicated your step and still got Infeasible. It always stops at the 55th iteration...

var2, prob2 = pulp.LpProblem.fromMPS("/Users/MyName/Downloads/python_1.mps",pulp.LpMaximize)
prob2.solve()
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019
command line - C:\Users[Name]\lib\site-packages\pulp\solverdir\cbc\win\64\cbc.exe C:\Users\MYNAME1\AppData\Local\Temp\0cc2907b024549d8bfc512c207f4076d-pulp.mps max timeMode elapsed branch printingOptions all solution C:\Users\MYNAME1\AppData\Local\Temp\0cc2907b024549d8bfc512c207f4076d-pulp.sol (default strategy 1)
At line 2 NAME MODEL
At line 3 ROWS
At line 378 COLUMNS
At line 2851 RHS
At line 3225 BOUNDS
At line 3638 ENDATA
Problem MODEL has 373 rows, 412 columns and 2060 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Presolve 193 (-180) rows, 289 (-123) columns and 1011 (-1049) elements
0 Obj 31829.833 Primal inf 153.86618 (105) Dual inf 81713.138 (289)
55 Obj 115959.85 Primal inf 22.794851 (43)
Primal infeasible - objective value 115959.85
Presolved problem not optimal, resolve after postsolve
After Postsolve, objective 115959.85, infeasibilities - dual 0 (0), primal 54.149996 (42)
PrimalInfeasible objective 115959.8501 - 55 iterations time 0.002, Presolve 0.00
Result - Linear relaxation infeasible
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.01
Time (Wallclock Seconds): 0.01
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.01 (Wallclock seconds): 0.01

[tle4336]

The differences start at the Presolve step of CBC. Mine was

Presolve 193 (-180) rows, 289 (-123) columns and 1011 (-1049) elements

compared to yours: Presolve 195 (-178) rows, 289 (-123) columns and 1031 (-1029) elements

The 0th iteration showed a huge discrepancy in terms of result. So weird.

Is this due to the FACT that you ran 'cbc' on Linux, while I ran it on Windows 10 (64-bit)?

[tle4336]

@jjhforrest Hi Dr. Forrest, I am wondering if you have some time to think about the potential sources of the discrepancy? I tried turning off the presolve option using this link (https://or.stackexchange.com/questions/8285/how-do-i-turn-off-preprocessing-in-pulp) but it did not work.

[tle4336]

@jjhforrest Good morning, thank you very much for your further investigation. Didn't your second test above with var2,prob2=pulp.LpProblem.fromMPS("python_1.mps",pulp.LpMaximize) give the same, correct result as the first test? I think the presolve step is somehow broken, but I am not sure if it is ONLY the problem with Windows 10 (64-bit). I went through the above .mps file but I don't see any missing RHS NOR the MARKET INTORG . Something else must have gone wrong in the presolve capability?

Please help give the below .mps files a run, as both of them are currently seen as "Infeasible" in the pre-solve and post-solve step. They are all feasible problems)
2InfeasibleProbs.zip

[tle4336]

@jjhforrest @dpo @chmduquesne Could either of you help give these problems (
InfeasibleProblems.zip) a run on your machine in Linux. I am wondering whether the presolve step of CBC solver behaved differently on Linux versus Windows, which would then require a serious fix from the Development team of CBC solver? All these 3 problems failed at presolve step with the logs below:

Infeasible1.mps file - Output from CBC

At line 2 NAME MODEL
At line 3 ROWS
At line 1576 COLUMNS
At line 23405 RHS
At line 24977 BOUNDS
At line 28616 ENDATA
Problem MODEL has 1571 rows, 3638 columns and 18190 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Presolve 990 (-581) rows, 3055 (-583) columns and 14847 (-3343) elements
0 Obj 317849.66 Primal inf 1583.772 (539) Dual inf 4529047.1 (3055)
94 Obj 4148089.4 Primal inf 167.31494 (277)
103 Obj 4146366.3 Primal inf 144.05725 (274)
Primal infeasible - objective value 4146366.3
Presolved problem not optimal, resolve after postsolve
After Postsolve, objective 4146366.3, infeasibilities - dual 0 (0), primal 1008.173 (274)
PrimalInfeasible objective 4146366.288 - 103 iterations time 0.012, Presolve 0.00
Result - Linear relaxation infeasible
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.02
Time (Wallclock Seconds): 0.02
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.03 (Wallclock seconds): 0.03

Infeasible2.mps file - Output from CBC:

At line 2 NAME MODEL
At line 3 ROWS
At line 1346 COLUMNS
At line 22455 RHS
At line 23797 BOUNDS
At line 27316 ENDATA
Problem MODEL has 1341 rows, 3518 columns and 17590 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Presolve determined that the problem was infeasible with tolerance of 1e-08
Analysis indicates model infeasible or unbounded
0 Obj -0 Primal inf 1693.7166 (641) Dual inf 4490588.9 (3518)
101 Obj 3588287.6 Primal inf 250.09876 (346)
202 Obj 3551472.8 Primal inf 130.91826 (270)
220 Obj 3548817.9 Primal inf 95.447883 (251)
Primal infeasible - objective value 3548817.9
PrimalInfeasible objective 3548817.892 - 220 iterations time 0.012
Result - Linear relaxation infeasible
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.02
Time (Wallclock Seconds): 0.02
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.03 (Wallclock seconds): 0.03

Infeasible3.mps file - Output from CBC solver

At line 2 NAME MODEL
At line 3 ROWS
At line 1288 COLUMNS
At line 20639 RHS
At line 21923 BOUNDS
At line 25149 ENDATA
Problem MODEL has 1283 rows, 3225 columns and 16125 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Presolve 954 (-329) rows, 2804 (-421) columns and 13093 (-3032) elements
0 Obj 288960.24 Primal inf 1344.4765 (520) Dual inf 3648671.9 (2804)
94 Obj 3768335.7 Primal inf 228.64093 (277)
188 Obj 3707134.9 Primal inf 100.93063 (233)
282 Obj 3667195.5 Primal inf 45.82908 (161)
323 Obj 3658292.6 Primal inf 27.469666 (125)
Primal infeasible - objective value 3658292.6
Presolved problem not optimal, resolve after postsolve
After Postsolve, objective 3658292.6, infeasibilities - dual 389.14423 (2), primal 183.49188 (125)
0 Obj 3658606.1 Primal inf 31.181091 (126) Dual inf 1427.2373 (2)
2 Obj 3658866.1 Primal inf 31.246957 (129)
Primal infeasible - objective value 3658866.1
PrimalInfeasible objective 3658866.106 - 325 iterations time 0.012, Presolve 0.00
Result - Linear relaxation infeasible
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.02
Time (Wallclock Seconds): 0.02
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.03 (Wallclock seconds): 0.03

If I use lpsolve package in R, all 3 problems are feasible with the corresponding optimal values = [4093513, 3518700, 3644587].

[tle4336]

@jjhforrest Thank you so much for your help on trying different solvers. Did you still get 'Infeasible' status with Infeasible1.mps AND Infeasible3.mps files with those different solvers? Because if that is the case, the problem now is actually with the lpsolve package in R. I will check the two above mentioned constraints in R to ensure this is the case.

Another question though: how were you able to identify those two identical constraints? Going through the .mps file to carve out such identical constraints seems not feasible to me, so I guess we have to look at the .lp file?

[tle4336]

Do the other solvers say the same thing for Infeasible1.mps and Infeasible3.mps? I am trying to reinforce why the two packages lpsolve and CBC came to different conclusions on the same optimization problem (still verifying on the lpsolve side now on those 2 constraints that you pointed out!!)

[tle4336]

@jjhforrest Do you have any ways to read this '.lp' file into Python and call CBC solver to solve it? This '.lp' file is generated by R, but my thorough inspection shows that it is mathematically equivalent to the LP in 'Infeasible2.mps' file.
ProblemR.zip

[tkralphs]

CyLP will read in MPS files and solve them in Cbc (but not LP, unfortunately). See here.

[tle4336]

@tkralphs Thank you.
@jjhforrest I have a quick question: how do we invoke the loglevel 3 message to display which constraint is violated in an infeasible problem? That would be super helpful for me to know why the problem in the OP is still infeasible by CBC solver on my local machine.

[tle4336]

@jjhforrest Hi Dr. Forrest, I figured out the above problem by turning off the presolve thanks to the help of @chmduquesne . I have another question though: is the bug that you found for .fromMPS() function fixed? I meant, should I trust that function to work properly if I need to read an .mps file into Python? Or should I opt for the CyLP package introduced by @tkralphs ?

@tkralphs Have you ever tested your .primal() solver to see if it gives the same result as CbC? I know you mentioned that it used CbC, but I failed to see it on the github page of CyLP. Any assistance you could offer would be greatly appreciated.