Open tle4336 opened 1 year ago
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 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).
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 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\MYNAME~1\AppData\Local\Temp\0cc2907b024549d8bfc512c207f4076d-pulp.mps max timeMode elapsed branch printingOptions all solution C:\Users\MYNAME~1\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
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)?
@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.
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 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
@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].
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 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?
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
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!!)
@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 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.
@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.
I am currently encountering a very weird issue with the
PULP_CBC_CMD
solver viapulp
package in Python (CBC MILP Solver version 2.10.3). Despite playing around with the parameter optionsgapAbs
andfracGap
, I had no way to make the CBC MILP solver to avoid running intoinfeasible
status. However, the optimization model is actually feasible (the model is an LP problem, with all variables being continuous between 0 and 1), as it was solved quickly and easily vialpsolve
package in R. I then compared the two models and could confirm that they are identical (so, the part of building the model in 2 languages is fine). I am wondering if anyone could help me figure out how to fix this incorrect issue?Attached is the model in
.lp
and.mps
format, exported from both Python and R (you can see the filename to determine which one is exported from Python). I also include the.txt
log file given by the CBC run. I also compute the values of the constraints as well as their corresponding slacks below:log.txt Downloads.zip