search

coin-or / python-mip

Python-MIP: collection of Python tools for the modeling and solution of Mixed-Integer Linear programs
Eclipse Public License 2.0
525 stars 92 forks source link

Optimization does not finish #138

Closed AF018 closed 2 years ago

AF018 commented 4 years ago

Describe the bug Hi, first thanks for all your work ! I have a mixed integer linear program I solve with CBC, and I encountered an instance which apparently causes Python to freeze. I have to kill it with the terminal kill command.

Here is what MIP outputs when verbose is set to 1, once I start the optimization:

Welcome to the CBC MILP Solver
Version: Trunk
Build Date: Aug  5 2020

Starting solution of the Linear programming relaxation problem using Dual Simplex

Coin0506I Presolve 310 (-40) rows, 215 (0) columns and 861 (-77) elements
Clp0014I Perturbing problem by 0.001% of 1781.7197 - largest nonzero change 0.00097460045 ( 0.00020618913%) - largest zero change 0.00096084324
Clp0000I Optimal - objective value -16913.571
Coin0511I After Postsolve, objective -16913.571, infeasibilities - dual 0 (0), primal 0 (0)
Clp0032I Optimal objective -16913.57066 - 163 iterations time 0.002, Presolve 0.00

Starting MIP optimization
Cgl0003I 9 fixed, 0 tightened bounds, 69 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 19 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 17 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 1 strengthened rows, 0 substitutions
Cgl0004I processed model has 262 rows, 169 columns (40 integer (40 of which binary)) and 785 elements
Coin3009W Conflict graph built in 0.000 seconds, density: 0.070%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
Cbc0038I Initial state - 7 integers unsatisfied sum - 0.683534
Cbc0038I Pass   1: suminf.    0.09800 (2) obj. -16859.6 iterations 15
Cbc0038I Pass   2: suminf.    0.00000 (0) obj. -16859.6 iterations 3
Cbc0038I Solution found of -16859.6
Cbc0038I Relaxing continuous gives -16859.7
Cbc0038I Before mini branch and bound, 32 integers at bound fixed and 93 continuous
Cbc0038I Full problem 262 rows 169 columns, reduced to 51 rows 38 columns
Cbc0038I Mini branch and bound did not improve solution (0.02 seconds)
Cbc0038I Round again with cutoff of -16863.4
Cbc0038I Reduced cost fixing fixed 1 variables on major pass 2
Cbc0038I Pass   3: suminf.    0.10373 (3) obj. -16863.4 iterations 3
Cbc0038I Pass   4: suminf.    0.09552 (1) obj. -16863.4 iterations 29
Cbc0038I Pass   5: suminf.    0.00562 (1) obj. -16863.4 iterations 2
Cbc0038I Pass   6: suminf.    0.83276 (14) obj. -16863.4 iterations 39
Cbc0038I Pass   7: suminf.    0.62485 (5) obj. -16863.4 iterations 3
Cbc0038I Pass   8: suminf.    0.16746 (3) obj. -16863.4 iterations 3
Cbc0038I Pass   9: suminf.    0.34194 (2) obj. -16863.4 iterations 10
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 21 integers at bound fixed and 73 continuous
Cbc0038I Full problem 262 rows 169 columns, reduced to 73 rows 53 columns
Cbc0038I Mini branch and bound did not improve solution (0.04 seconds)
Cbc0038I After 0.04 seconds - Feasibility pump exiting with objective of -16859.7 - took 0.02 seconds
Cbc0012I Integer solution of -16859.668 found by feasibility pump after 0 iterations and 0 nodes (0.04 seconds)
Cbc0012I Integer solution of -16861.071 found by DiveCoefficient after 0 iterations and 0 nodes (0.04 seconds)
Cbc0038I Full problem 262 rows 169 columns, reduced to 57 rows 45 columns

To Reproduce The MILP I used has been exported to the file failure_example.txt (the actual format is lp but github didn't let me keep it)

import mip

m = mip.Model(sense=mip.MINIMIZE, solver_name=mip.CBC)
m.read('failure_example.lp')
m.pump_passes = 7
m.optimize()

Putting the number of the pump feasibility heuristic uses to 5 or 6 also produces the bug, I haven't tested for lower values but for 8 the optimization finishes and reaches the optimum.

Expected behavior I expect the optimization to finish and reach the optimum.

Desktop (please complete the following information):

uurriola commented 3 years ago

I reproduced the issue with the given file and mip version 1.12.0. Setting "preprocess" to 0 (instead of default value of -1) in model solves the issue.

I tried to solve the LP directly with CBC (using CLI) and it worked with CBC v2.9.9, with and without preprocess, . I haven't been able to compile the "devel" version which seems to be used through MIP.

Here is the output with CBC v2.9.9 called through CLI:


Welcome to the CBC MILP Solver
Version: 2.9.9
Build Date: Aug 21 2017

command line - cbc failure_example.lp PassF 7 solve solu sol.txt (default strategy 1)
passFeasibilityPump was changed from 30 to 7
Continuous objective value is -16913.6 - 0.01 seconds
Cgl0003I 9 fixed, 0 tightened bounds, 101 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 22 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 17 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 2 strengthened rows, 0 substitutions
Cgl0004I processed model has 259 rows, 169 columns (40 integer (40 of which binary)) and 779 elements
Cbc0038I Initial state - 7 integers unsatisfied sum - 0.681085
Cbc0038I Pass   1: suminf.    0.09810 (2) obj. -16859.6 iterations 11
Cbc0038I Pass   2: suminf.    0.00000 (0) obj. -16859.6 iterations 3
Cbc0038I Solution found of -16859.6
Cbc0038I Relaxing continuous gives -16859.7
Cbc0038I Before mini branch and bound, 32 integers at bound fixed and 91 continuous
Cbc0038I Full problem 259 rows 169 columns, reduced to 52 rows 39 columns
Cbc0038I Mini branch and bound improved solution from -16859.7 to -16885.5 (0.12 seconds)
Cbc0038I Round again with cutoff of -16886.6
Cbc0038I Reduced cost fixing fixed 3 variables on major pass 2
Cbc0038I Pass   3: suminf.    0.13919 (3) obj. -16886.6 iterations 1
Cbc0038I Pass   4: suminf.    0.23193 (1) obj. -16886.6 iterations 30
Cbc0038I Pass   5: suminf.    0.04098 (1) obj. -16886.6 iterations 2
Cbc0038I Pass   6: suminf.    0.82904 (15) obj. -16886.6 iterations 31
Cbc0038I Pass   7: suminf.    0.04300 (2) obj. -16886.6 iterations 10
Cbc0038I Pass   8: suminf.    0.39848 (2) obj. -16886.6 iterations 28
Cbc0038I Pass   9: suminf.    0.57895 (17) obj. -16886.6 iterations 24
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 17 integers at bound fixed and 57 continuous
Cbc0038I Full problem 259 rows 169 columns, reduced to 89 rows 63 columns
Cbc0038I Mini branch and bound improved solution from -16885.5 to -16885.5 (0.20 seconds)
Cbc0038I Round again with cutoff of -16888.6
Cbc0038I Reduced cost fixing fixed 3 variables on major pass 3
Cbc0038I Pass   9: suminf.    0.14224 (3) obj. -16888.6 iterations 0
Cbc0038I Pass  10: suminf.    0.17400 (1) obj. -16888.6 iterations 30
Cbc0038I Pass  11: suminf.    0.04403 (1) obj. -16888.6 iterations 2
Cbc0038I Pass  12: suminf.    0.73132 (15) obj. -16888.6 iterations 64
Cbc0038I Pass  13: suminf.    0.58156 (4) obj. -16888.6 iterations 14
Cbc0038I Pass  14: suminf.    0.45084 (4) obj. -16888.6 iterations 4
Cbc0038I Pass  15: suminf.    0.45084 (4) obj. -16888.6 iterations 0
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 20 integers at bound fixed and 71 continuous
Cbc0038I Full problem 259 rows 169 columns, reduced to 69 rows 50 columns
Cbc0038I Mini branch and bound did not improve solution (0.25 seconds)
Cbc0038I After 0.25 seconds - Feasibility pump exiting with objective of -16885.5 - took 0.17 seconds
Cbc0012I Integer solution of -16885.489 found by feasibility pump after 0 iterations and 0 nodes (0.26 seconds)
Cbc0038I Full problem 259 rows 169 columns, reduced to 57 rows 45 columns
Cbc0012I Integer solution of -16885.744 found by DiveCoefficient after 18 iterations and 0 nodes (0.34 seconds)
Cbc0031I 12 added rows had average density of 7.9166667
Cbc0013I At root node, 12 cuts changed objective from -16896.61 to -16885.765 in 5 passes
Cbc0014I Cut generator 0 (Probing) - 14 row cuts average 2.4 elements, 6 column cuts (6 active)  in 0.008 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 9 row cuts average 12.9 elements, 0 column cuts (0 active)  in 0.003 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.005 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 4 row cuts average 2.0 elements, 0 column cuts (0 active)  in 0.003 seconds - new frequency is 1
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.004 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 11 row cuts average 10.9 elements, 0 column cuts (0 active)  in 0.006 seconds - new frequency is -100
Cbc0001I Search completed - best objective -16885.74407304303, took 18 iterations and 0 nodes (0.35 seconds)
Cbc0032I Strong branching done 2 times (10 iterations), fathomed 1 nodes and fixed 0 variables
Cbc0035I Maximum depth 0, 3 variables fixed on reduced cost
Cuts at root node changed objective from -16896.6 to -16885.7
Probing was tried 5 times and created 20 cuts of which 0 were active after adding rounds of cuts (0.008 seconds)
Gomory was tried 5 times and created 9 cuts of which 0 were active after adding rounds of cuts (0.003 seconds)
Knapsack was tried 5 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.005 seconds)
Clique was tried 5 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 5 times and created 4 cuts of which 0 were active after adding rounds of cuts (0.003 seconds)
FlowCover was tried 5 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.004 seconds)
TwoMirCuts was tried 5 times and created 11 cuts of which 0 were active after adding rounds of cuts (0.006 seconds)

Result - Optimal solution found

Objective value:                -16885.74407304
Enumerated nodes:               0
Total iterations:               18
Time (CPU seconds):             0.37
Time (Wallclock seconds):       0.10

Total time (CPU seconds):       0.38   (Wallclock seconds):       0.11

Any idea @h-g-s ?

h-g-s commented 3 years ago

Hi @AF018 , what strange bug ! Reproduced it running from python3 and pypy3. However, if I run in debug mode (pudb) a different error happens. Also, when I run using only the C interface in CBC (which would be easier to debug), the error does not happens ...

jerak commented 3 years ago

Hi @h-g-s , I'm experiencing the exact same issue in some of the problems I want to have solved. Unfortunately this only happens when I run the solver multiple times in a loop, making it harder to reproduce. Do you by any chance already have more information on what causes this issue? I already tried switching off the preprocessing step, which works for some of the problem files, but not for all. Thank you in advance!

sebheger commented 2 years ago

The provided .lp file runs well with latest release 1.14.0. I will consider this bug as not reproducible and i close the issue.