WaldemarGrauberger
commented
3 years ago Hi gt6989b, I have the same issue. Have you been able to find a solution?
Open gt6989b opened 3 years ago
WaldemarGrauberger
commented
3 years ago Hi gt6989b, I have the same issue. Have you been able to find a solution?
gt6989b
commented
3 years ago Hi gt6989b, I have the same issue. Have you been able to find a solution?
@WaldemarGrauberger not really, unfortunately. I am more troubled by the fact that this has not gotten any attention for almost a year... the beauty of using a free product...
tkralphs
commented
2 years ago This is not an issue with python-mip, but with the solver you're using (Cbc). You would probably have had more success if you posted the issue there. I'll just go ahead and transfer it for you. But yes, this is open source and it's not wlays the case that someone has the time to debug these things when they come in. We're volunteers doing this in our spare time.
jjhforrest
commented
2 years ago Thank you for your detailed bug report.
Running stable standalone Cbc on worst.mps, I am unable to reproduce the bug - I obtain a solution of -38477.82864000 without any difficulties. The output looks similar up until the code adds cuts at root node.
It may take me some time to set up python-mip. What happens if you add "-cuts off" to the command line?
John Forrest
On 29/11/2021 23:01, gt6989b wrote:
Short DescriptionI have created a MIP formulation, which the solver classifies infeasible. I have also a solution for the problem, which the solver agrees is a valid solution, but cannot improve on. In my Excel simulator, I can improve on the solution but cannot quite produce a solution that the solver would take as a starting value.
To Reproduce Archive DescriptionUnzip the archive bugReport.zip https://github.com/coin-or/python-mip/files/5623833/bugReport.zip. It contains
- |run.py| - a python utility to execute a problem with a possible starting solution.
- |worst.mps| - the MPS formulation of the problem that can be used to reproduce results
- |problem.lp| - the LP formulation of the problem that can be used by the human eye
- |initGuess.psv| - a feasible initial guess as a pipe-separated file
|betterGuess.psv| - my attempt at creating a better feasible guess as a pipe-separated file
Feasibility problemExecute just the problem first, without the initial solution, to get:
|11:14:42 ~/Temp/ETF/bug1124> ./run.py worst.mps 2 -> [./run.py worst.mps] Coin0001I At line 1 NAME ETFCreat FREE Coin0001I At line 2 ROWS Coin0001I At line 8299 COLUMNS Coin0001I At line 33343 RHS Coin0001I At line 33344 BOUNDS Coin0001I At line 39993 ENDATA Coin0002I Problem ETFCreat has 8295 rows, 6500 columns and 45103 elements Coin0008I ETFCreat read with 0 errors Welcome to the CBC MILP Solver Version: devel Build Date: Nov 15 2020 Starting solution of the Linear programming relaxation problem using Dual Simplex Coin0506I Presolve 2222 (-6073) rows, 1269 (-5231) columns and 6162 (-38941) elements Clp0014I Perturbing problem by 0.001% of 18.578329 - largest nonzero change 0.00099752473 ( 3.7983111%) - largest zero change 0.00098555124 Clp0000I Optimal - objective value -49094.743 Coin0511I After Postsolve, objective -49094.743, infeasibilities - dual 0 (0), primal 1.9999501e-06 (1) Coin0512I Presolved model was optimal, full model needs cleaning up Clp0000I Optimal - objective value -49094.743 Clp0032I Optimal objective -49094.74339 - 791 iterations time 0.032, Presolve 0.02 Starting MIP optimization Cgl0002I 86 variables fixed Cgl0003I 3 fixed, 0 tightened bounds, 13 strengthened rows, 276 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 4 strengthened rows, 44 substitutions Cgl0004I processed model has 307 rows, 310 columns (310 integer (265 of which binary)) and 2011 elements Coin3009W Conflict graph built in 0.000 seconds, density: 0.219% Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated Cbc0038I Initial state - 76 integers unsatisfied sum - 19.4016 Cbc0038I Pass 1: suminf. 14.49588 (56) obj. -41584.9 iterations 93 Cbc0038I Pass 2: suminf. 12.07972 (51) obj. -41584.9 iterations 5 Cbc0038I Pass 3: suminf. 9.52161 (37) obj. -38755.8 iterations 60 Cbc0038I Pass 4: suminf. 8.55705 (39) obj. -38130.4 iterations 22 Cbc0038I Pass 5: suminf. 10.62801 (41) obj. -36384.6 iterations 50 Cbc0038I Pass 6: suminf. 9.49806 (41) obj. -36205.5 iterations 8 Cbc0038I Pass 7: suminf. 10.53977 (37) obj. -35705.4 iterations 30 Cbc0038I Pass 8: suminf. 8.79920 (35) obj. -35687.4 iterations 8 Cbc0038I Pass 9: suminf. 9.45722 (36) obj. -35498.2 iterations 44 Cbc0038I Pass 10: suminf. 8.01042 (34) obj. -35510.9 iterations 21 Cbc0038I Pass 11: suminf. 9.22139 (38) obj. -35846.3 iterations 28 Cbc0038I Pass 12: suminf. 8.13945 (38) obj. -35846.3 iterations 8 Cbc0038I Pass 13: suminf. 9.64528 (37) obj. -35492 iterations 38 Cbc0038I Pass 14: suminf. 8.34862 (36) obj. -35489.3 iterations 21 Cbc0038I Pass 15: suminf. 13.69146 (51) obj. -31617.4 iterations 83 Cbc0038I Pass 16: suminf. 11.99226 (46) obj. -31237.6 iterations 19 Cbc0038I Pass 17: suminf. 11.51526 (44) obj. -31232.9 iterations 3 Cbc0038I Pass 18: suminf. 8.06168 (34) obj. -29881 iterations 54 Cbc0038I Pass 19: suminf. 7.60347 (34) obj. -29879.4 iterations 24 Cbc0038I Pass 20: suminf. 9.42337 (34) obj. -29970.2 iterations 19 Cbc0038I Pass 21: suminf. 8.81058 (34) obj. -29967.3 iterations 18 Cbc0038I Pass 22: suminf. 8.58966 (34) obj. -30010.7 iterations 27 Cbc0038I Pass 23: suminf. 16.71082 (58) obj. -23657.9 iterations 71 Cbc0038I Pass 24: suminf. 10.77713 (41) obj. -22890 iterations 30 Cbc0038I Pass 25: suminf. 10.09361 (37) obj. -22784.8 iterations 17 Cbc0038I Pass 26: suminf. 8.78241 (33) obj. -23101.7 iterations 37 Cbc0038I Pass 27: suminf. 7.10134 (29) obj. -23108.3 iterations 23 Cbc0038I Pass 28: suminf. 8.87870 (33) obj. -23101.7 iterations 25 Cbc0038I Pass 29: suminf. 7.19763 (29) obj. -23108.3 iterations 23 Cbc0038I Pass 30: suminf. 15.09668 (55) obj. -30051.4 iterations 70 Cbc0038I No solution found this major pass Cbc0038I Before mini branch and bound, 109 integers at bound fixed and 0 continuous Cbc0038I Full problem 307 rows 310 columns, reduced to 186 rows 173 columns - too large Cbc0038I Mini branch and bound did not improve solution (0.58 seconds) Cbc0038I After 0.58 seconds - Feasibility pump exiting - took 0.04 seconds Cbc0031I 68 added rows had average density of 3.6764706 Cbc0013I At root node, 290 cuts changed objective from -43764.135 to 1.1765264e+08 in 2 passes Cbc0014I Cut generator 0 (Probing) - 173 row cuts average 2.2 elements, 1 column cuts (1 active) in 0.004 seconds - new frequency is 1 Cbc0014I Cut generator 1 (Gomory) - 126 row cuts average 18.8 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1 Cbc0014I Cut generator 2 (Knapsack) - 33 row cuts average 4.3 elements, 0 column cuts (0 active) in 0.004 seconds - new frequency is 1 Cbc0014I Cut generator 3 (Clique) - 6 row cuts average 2.8 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1 Cbc0014I Cut generator 4 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1000 Cbc0014I Cut generator 5 (MixedIntegerRounding2) - 71 row cuts average 5.9 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1 Cbc0014I Cut generator 6 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1000 Cbc0014I Cut generator 7 (TwoMirCuts)
- 188 row cuts average 22.2 elements, 0 column cuts (0 active) in 0.004 seconds - new frequency is -100 Cbc0014I Cut generator 8 (ZeroHalf) - 4 row cuts average 2.8 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1 Cbc0001I Search completed - best objective 1e+50, took 302 iterations and 0 nodes (0.62 seconds) Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost Total time (CPU seconds): 0.60 (Wallclock seconds): 0.62 ERROR: RuntimeError: Optimization Failed:The problem is infeasible Traceback (most recent call last): File "./run.py", line 133, in
sys.exit(main()) File "./run.py", line 122, in main solver.runProblem(guessFile = guessFile) File "./run.py", line 92, in runProblem raise RuntimeError('Optimization Failed:' + rCodeMsg) RuntimeError: Optimization Failed:The problem is infeasible | Now you can execute this with the initial solution provided to see that the solver recognizes this as a valid solution, rendering the problem feasible:
|11:19:23 ~/Temp/ETF/bug1124> ./run.py worst.mps initGuess.psv 3 -> [./run.py worst.mps initGuess.psv] Coin0001I At line 1 NAME ETFCreat FREE Coin0001I At line 2 ROWS Coin0001I At line 8299 COLUMNS Coin0001I At line 33343 RHS Coin0001I At line 33344 BOUNDS Coin0001I At line 39993 ENDATA Coin0002I Problem ETFCreat has 8295 rows, 6500 columns and 45103 elements Coin0008I ETFCreat read with 0 errors Read the initial guess from initGuess.psv Welcome to the CBC MILP Solver Version: devel Build Date: Nov 15 2020 Starting solution of the Linear programming relaxation problem using Dual Simplex Coin0506I Presolve 2222 (-6073) rows, 1269 (-5231) columns and 6162 (-38941) elements Clp0014I Perturbing problem by 0.001% of 18.578329 - largest nonzero change 0.00099752473 ( 3.7983111%) - largest zero change 0.00098555124 Clp0000I Optimal - objective value -49094.743 Coin0511I After Postsolve, objective -49094.743, infeasibilities - dual 0 (0), primal 1.9999501e-06 (1) Coin0512I Presolved model was optimal, full model needs cleaning up Clp0000I Optimal - objective value -49094.743 Clp0032I Optimal objective -49094.74339 - 791 iterations time 0.032, Presolve 0.01 Starting MIP optimization Cgl0002I 86 variables fixed Cgl0003I 3 fixed, 0 tightened bounds, 13 strengthened rows, 276 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 4 strengthened rows, 44 substitutions Cgl0004I processed model has 307 rows, 310 columns (310 integer (265 of which binary)) and 2011 elements Coin3009W Conflict graph built in 0.000 seconds, density: 0.219% Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated Cbc0045I MIPStart provided solution with cost -8733.74 Cbc0012I Integer solution of -8733.7404 found by Reduced search after 0 iterations and 0 nodes (0.55 seconds) Cbc0038I Full problem 307 rows 310 columns, reduced to 223 rows 211 columns - too large Cbc0031I 68 added rows had average density of 3.6764706 Cbc0013I At root node, 290 cuts changed objective from -43764.135 to 1.1765253e+08 in 2 passes Cbc0014I Cut generator 0 (Probing) - 173 row cuts average 2.2 elements, 1 column cuts (1 active) in 0.004 seconds - new frequency is 1 Cbc0014I Cut generator 1 (Gomory) - 126 row cuts average 18.9 elements, 0 column cuts (0 active) in 0.004 seconds - new frequency is 1 Cbc0014I Cut generator 2 (Knapsack) - 33 row cuts average 4.3 elements, 0 column cuts (0 active) in 0.004 seconds - new frequency is 1 Cbc0014I Cut generator 3 (Clique) - 6 row cuts average 2.8 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1 Cbc0014I Cut generator 4 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1000 Cbc0014I Cut generator 5 (MixedIntegerRounding2) - 71 row cuts average 5.9 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1 Cbc0014I Cut generator 6 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1000 Cbc0014I Cut generator 7 (TwoMirCuts) - 188 row cuts average 22.3 elements, 0 column cuts (0 active) in 0.008 seconds - new frequency is -100 Cbc0014I Cut generator 8 (ZeroHalf) - 4 row cuts average 2.8 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1 Cbc0001I Search completed - best objective -8733.740437999997, took 299 iterations and 0 nodes (0.61 seconds) Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost Total time (CPU seconds): 0.66 (Wallclock seconds): 0.66 |
Improving the starting solutionI have an Excel simulation of the problem, which we have formulated, and I can manipulate it manually to see the numbers can definitely be improved. I tried to create a better solution by hand, but when I try to submit the better solution, the solver shows
|11:17:07 ~/Temp/ETF/bug1124> ./run.py worst.mps betterGuess.psv 3 -> [./run.py worst.mps betterGuess.psv] Coin0001I At line 1 NAME ETFCreat FREE Coin0001I At line 2 ROWS Coin0001I At line 8299 COLUMNS Coin0001I At line 33343 RHS Coin0001I At line 33344 BOUNDS Coin0001I At line 39993 ENDATA Coin0002I Problem ETFCreat has 8295 rows, 6500 columns and 45103 elements Coin0008I ETFCreat read with 0 errors Read the initial guess from betterGuess.psv Welcome to the CBC MILP Solver Version: devel Build Date: Nov 15 2020 Starting solution of the Linear programming relaxation problem using Dual Simplex Coin0506I Presolve 2222 (-6073) rows, 1269 (-5231) columns and 6162 (-38941) elements Clp0014I Perturbing problem by 0.001% of 18.578329 - largest nonzero change 0.00099752473 ( 3.7983111%) - largest zero change 0.00098555124 Clp0000I Optimal - objective value -49094.743 Coin0511I After Postsolve, objective -49094.743, infeasibilities - dual 0 (0), primal 1.9999501e-06 (1) Coin0512I Presolved model was optimal, full model needs cleaning up Clp0000I Optimal - objective value -49094.743 Clp0032I Optimal objective -49094.74339 - 791 iterations time 0.032, Presolve 0.02 Starting MIP optimization Cgl0002I 86 variables fixed Cgl0003I 3 fixed, 0 tightened bounds, 13 strengthened rows, 276 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 4 strengthened rows, 44 substitutions Cgl0004I processed model has 307 rows, 310 columns (310 integer (265 of which binary)) and 2011 elements Coin3009W Conflict graph built in 0.000 seconds, density: 0.219% Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated Cbc0045I MIPStart solution provided values for 133 of 310 integer variables, 1 variables are still fractional. Cbc0045I Warning: mipstart values could not be used to build a solution. |
and proceeds to solve the problem without the starting solution, declaring it infeasible as above. I could not track down which integer variable does the solver think is still fractional, but if I know what the variable name is, I would be able to track it down and provide the corresponding value. Is there a way to find out what variable is still fractional?
Desktop (please complete the following information):
- Operating System, version: |uname -a| returns |Linux GODZILLA 4.4.0-141-generic coin-or/python-mip#167-Ubuntu SMP Wed Dec 5 10:40:15 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux|
- Python version: 3.7.8
Python-MIP version (we recommend you to test with the latest version): 1.13.0
Additional context
Similar content in another submitted issue 161 https://github.com/coin-or/python-mip/issues/161 but not sure if related.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/coin-or/Cbc/issues/461, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABWJYHH2KFDIAIIFO5XVQRTUOQA6NANCNFSM5JAJZ2EQ. Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.
jjhforrest
commented
2 years ago I am not sure how to respond as I have no knowledge of Python-MIP and do not understand how the version using Cbc stable was built. I am unable to reproduce the problem using standalone Cbc. My previous suggestion of not using cuts made the code run for avery long time.
Using master and copying over the libraries - the problem vanishes. As for for finding out which variable stopped the initial guess - I have modified code to print out offending variables if less than 5. I may check that in to Cbc master.
Doing that I get
Cbc0045I MIPStart solution provided values for 133 of 310 integer variables, 1 variables are still fractional. Cbc0045I Variable 215 BBG007PZ2KQ4.use has value 0.0381219 Cbc0045I Warning: mipstart values could not be used to build a solution. (215 is sequence number in preprocessed problem)
using anotherGuess.psv guess.zip
Cbc0045I MIPStart provided solution with cost -38477.8
John Forrest
Short Description
I have created a MIP formulation, which the solver classifies infeasible. I have also a solution for the problem, which the solver agrees is a valid solution, but cannot improve on. In my Excel simulator, I can improve on the solution but cannot quite produce a solution that the solver would take as a starting value.
To Reproduce
Archive Description
Unzip the archive bugReport.zip. It contains
run.py- a python utility to execute a problem with a possible starting solution.worst.mps- the MPS formulation of the problem that can be used to reproduce resultsproblem.lp- the LP formulation of the problem that can be used by the human eyeinitGuess.psv- a feasible initial guess as a pipe-separated filebetterGuess.psv- my attempt at creating a better feasible guess as a pipe-separated fileFeasibility problem
Execute just the problem first, without the initial solution, to get:
Now you can execute this with the initial solution provided to see that the solver recognizes this as a valid solution, rendering the problem feasible:
Improving the starting solution
I have an Excel simulation of the problem, which we have formulated, and I can manipulate it manually to see the numbers can definitely be improved. I tried to create a better solution by hand, but when I try to submit the better solution, the solver shows
and proceeds to solve the problem without the starting solution, declaring it infeasible as above. I could not track down which integer variable does the solver think is still fractional, but if I know what the variable name is, I would be able to track it down and provide the corresponding value. Is there a way to find out what variable is still fractional?
Desktop (please complete the following information):
uname -areturnsLinux GODZILLA 4.4.0-141-generic coin-or/python-mip#167-Ubuntu SMP Wed Dec 5 10:40:15 UTC 2018 x86_64 x86_64 x86_64 GNU/LinuxAdditional context
Similar content in another submitted issue 161 but not sure if related.