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
516 stars 90 forks source link

Infeasible solution when preprocess is enabled #191

Closed ericgtkb closed 2 years ago

ericgtkb commented 3 years ago

Describe the bug With the same problem (using CBC) when preprocess is set to 1, the solution always fails when calling check_optimization_results(). Same problem when running with preprocess to 0 passed the check_optimization_results() call.

To Reproduce Code:

import mip

model = mip.Model(solver_name=mip.CBC)
model.read('example.lp')
model.preprocess = 1

status = model.optimize(max_seconds=200)
print(f'Objective = {model.objective_value}')
model.check_optimization_results()

One example of this is attached here example.zip. Output when setting model.preprocess = 0:

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 2012 (-4020) rows, 1391 (-3573) columns and 8081 (-8734) elements
Clp0014I Perturbing problem by 0.001% of 56.411717 - largest nonzero change 0.00015613524 ( 25.958206%) - largest zero change 0.00015610141
Clp0000I Optimal - objective value 361894.06
Coin0511I After Postsolve, objective 361894.06, infeasibilities - dual 0 (0), primal 0 (0)
Clp0032I Optimal objective 361894.0628 - 1382 iterations time 0.062, Presolve 0.01

Starting MIP optimization
Coin3009W Conflict graph built in 0.003 seconds, density: 0.003%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
Cbc0038I Initial state - 139 integers unsatisfied sum - 9.82522
Cbc0038I Pass   1: (0.21 seconds) suminf.    0.00000 (0) obj. 441030 iterations 299
Cbc0038I Solution found of 441030
Cbc0038I Relaxing continuous gives 441030
Cbc0038I Before mini branch and bound, 1128 integers at bound fixed and 2915 continuous
Cbc0038I Full problem 6032 rows 4964 columns, reduced to 342 rows 178 columns
Cbc0038I Mini branch and bound improved solution from 441030 to 424067 (0.84 seconds)
Cbc0038I Round again with cutoff of 423048
Cbc0038I Pass   2: (0.88 seconds) suminf.    0.18016 (3) obj. 423048 iterations 21
Cbc0038I Pass   3: (0.89 seconds) suminf.    0.18016 (3) obj. 423048 iterations 21
Cbc0038I Pass   4: (0.91 seconds) suminf.    0.88760 (3) obj. 419048 iterations 181
Cbc0038I Pass   5: (0.92 seconds) suminf.    0.18016 (3) obj. 423048 iterations 45
Cbc0038I Pass   6: (0.95 seconds) suminf.    0.61540 (7) obj. 423048 iterations 126
Cbc0038I Pass   7: (0.97 seconds) suminf.    0.18016 (3) obj. 423048 iterations 46
Cbc0038I Pass   8: (0.98 seconds) suminf.    0.88760 (3) obj. 419048 iterations 33
Cbc0038I Pass   9: (1.00 seconds) suminf.    0.18016 (3) obj. 423048 iterations 71
Cbc0038I Pass  10: (1.02 seconds) suminf.    0.18016 (3) obj. 423048 iterations 33
Cbc0038I Pass  11: (1.04 seconds) suminf.    0.88760 (3) obj. 419048 iterations 31
Cbc0038I Pass  12: (1.07 seconds) suminf.    4.19891 (14) obj. 423048 iterations 116
Cbc0038I Pass  13: (1.08 seconds) suminf.    3.05612 (9) obj. 423048 iterations 49
Cbc0038I Pass  14: (1.10 seconds) suminf.    0.58016 (5) obj. 423048 iterations 2
Cbc0038I Pass  15: (1.11 seconds) suminf.    0.18016 (3) obj. 423048 iterations 2
Cbc0038I Pass  16: (1.12 seconds) suminf.    1.18774 (3) obj. 417351 iterations 14
Cbc0038I Pass  17: (1.14 seconds) suminf.    0.18016 (3) obj. 423048 iterations 5
Cbc0038I Pass  18: (1.15 seconds) suminf.    1.18774 (3) obj. 417351 iterations 13
Cbc0038I Pass  19: (1.17 seconds) suminf.    1.59422 (5) obj. 413988 iterations 72
Cbc0038I Pass  20: (1.19 seconds) suminf.    0.18016 (3) obj. 423048 iterations 51
Cbc0038I Pass  21: (1.19 seconds) suminf.    0.18016 (3) obj. 423048 iterations 0
Cbc0038I Pass  22: (1.21 seconds) suminf.    1.18774 (3) obj. 417351 iterations 26
Cbc0038I Pass  23: (1.23 seconds) suminf.    1.60000 (7) obj. 413988 iterations 48
Cbc0038I Pass  24: (1.24 seconds) suminf.    3.04369 (9) obj. 423048 iterations 34
Cbc0038I Pass  25: (1.26 seconds) suminf.    2.99172 (8) obj. 423048 iterations 30
Cbc0038I Pass  26: (1.28 seconds) suminf.    1.59422 (5) obj. 413988 iterations 19
Cbc0038I Pass  27: (1.29 seconds) suminf.    0.18016 (3) obj. 423048 iterations 2
Cbc0038I Pass  28: (1.29 seconds) suminf.    0.18016 (3) obj. 423048 iterations 0
Cbc0038I Pass  29: (1.31 seconds) suminf.    1.18774 (3) obj. 417351 iterations 26
Cbc0038I Pass  30: (1.33 seconds) suminf.    0.18016 (3) obj. 423048 iterations 44
Cbc0038I Pass  31: (1.34 seconds) suminf.    0.18016 (3) obj. 423048 iterations 31
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 1123 integers at bound fixed and 2912 continuous
Cbc0038I Full problem 6032 rows 4964 columns, reduced to 343 rows 180 columns
Cbc0038I Mini branch and bound did not improve solution (1.89 seconds)
Cbc0038I After 1.89 seconds - Feasibility pump exiting with objective of 424067 - took 1.65 seconds
Cbc0012I Integer solution of 424067.13 found by feasibility pump after 0 iterations and 0 nodes (1.92 seconds)
Cbc0038I Full problem 6032 rows 4964 columns, reduced to 342 rows 178 columns
Cbc0031I 134 added rows had average density of 21.813433
Cbc0013I At root node, 134 cuts changed objective from 413880.6 to 424067.1 in 10 passes
Cbc0014I Cut generator 0 (Probing) - 19 row cuts average 2.4 elements, 12 column cuts (60 active)  in 0.025 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 515 row cuts average 60.9 elements, 0 column cuts (0 active)  in 0.045 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 6 row cuts average 2.5 elements, 0 column cuts (0 active)  in 0.063 seconds - new frequency is 2
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is 1000
Cbc0014I Cut generator 4 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is 1000
Cbc0014I Cut generator 5 (MixedIntegerRounding2) - 3 row cuts average 2.0 elements, 0 column cuts (0 active)  in 0.016 seconds - new frequency is 3
Cbc0014I Cut generator 6 (FlowCover) - 5 row cuts average 2.4 elements, 0 column cuts (0 active)  in 0.051 seconds - new frequency is 2
Cbc0014I Cut generator 7 (TwoMirCuts) - 554 row cuts average 41.8 elements, 0 column cuts (0 active)  in 0.092 seconds - new frequency is 1
Cbc0014I Cut generator 8 (ZeroHalf) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1000
Cbc0011I Exiting as integer gap of 0.028294959 less than 1e-10 or 0.01%
Cbc0001I Search completed - best objective 424067.1272500008, took 713 iterations and 0 nodes (3.38 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Total time (CPU seconds):       3.15   (Wallclock seconds):       3.44

Objective = 424067.12725000083

Output when setting model.preprocess = 1:

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 2012 (-4020) rows, 1391 (-3573) columns and 8081 (-8734) elements
Clp0014I Perturbing problem by 0.001% of 56.411717 - largest nonzero change 0.00015613524 ( 25.958206%) - largest zero change 0.00015610141
Clp0000I Optimal - objective value 361894.06
Coin0511I After Postsolve, objective 361894.06, infeasibilities - dual 0 (0), primal 0 (0)
Clp0032I Optimal objective 361894.0628 - 1382 iterations time 0.062, Presolve 0.02

Starting MIP optimization
Cgl0003I 4 fixed, 0 tightened bounds, 27 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 27 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 27 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 27 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 27 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 24 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 24 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 24 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 24 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 24 strengthened rows, 0 substitutions
Cgl0004I processed model has 224 rows, 165 columns (140 integer (140 of which binary)) and 941 elements
Coin3009W Conflict graph built in 0.000 seconds, density: 2.829%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
Cbc0038I Initial state - 135 integers unsatisfied sum - 9.60053
Cbc0038I Pass   1: suminf.    0.00000 (0) obj. 491917 iterations 130
Cbc0038I Solution found of 491917
Cbc0038I Relaxing continuous gives 491917
Cbc0038I Before mini branch and bound, 1 integers at bound fixed and 1 continuous
Cbc0038I Full problem 224 rows 165 columns, reduced to 223 rows 162 columns - 0 fixed gives 223, 162 - still too large
Cbc0038I Mini branch and bound did not improve solution (0.38 seconds)
Cbc0038I Round again with cutoff of 484114
Cbc0038I Pass   2: suminf.    0.92011 (2) obj. 484114 iterations 1
Cbc0038I Pass   3: suminf.    0.92011 (2) obj. 484114 iterations 0
Cbc0038I Pass   4: suminf.    0.00000 (0) obj. 474955 iterations 3
Cbc0038I Solution found of 474955
Cbc0038I Relaxing continuous gives 474955
Cbc0038I Before mini branch and bound, 1 integers at bound fixed and 1 continuous
Cbc0038I Full problem 224 rows 165 columns, reduced to 223 rows 162 columns - 1 fixed gives 217, 156 - still too large
Cbc0038I Mini branch and bound did not improve solution (0.39 seconds)
Cbc0038I Round again with cutoff of 462740
Cbc0038I Pass   5: suminf.    0.83968 (3) obj. 462740 iterations 3
Cbc0038I Pass   6: suminf.    0.00000 (0) obj. 457992 iterations 6
Cbc0038I Solution found of 457992
Cbc0038I Relaxing continuous gives 457992
Cbc0038I Before mini branch and bound, 2 integers at bound fixed and 1 continuous
Cbc0038I Full problem 224 rows 165 columns, reduced to 222 rows 160 columns - 1 fixed gives 216, 154 - still too large
Cbc0038I Mini branch and bound did not improve solution (0.40 seconds)
Cbc0038I Round again with cutoff of 444759
Cbc0038I Pass   7: suminf.    1.78016 (5) obj. 444759 iterations 6
Cbc0038I Pass   8: suminf.    1.78016 (5) obj. 444759 iterations 0
Cbc0038I Pass   9: suminf.    0.00000 (0) obj. 441030 iterations 6
Cbc0038I Solution found of 441030
Cbc0038I Relaxing continuous gives 441030
Cbc0038I Before mini branch and bound, 3 integers at bound fixed and 1 continuous
Cbc0038I Full problem 224 rows 165 columns, reduced to 221 rows 158 columns - 1 fixed gives 215, 152 - still too large
Cbc0038I Mini branch and bound did not improve solution (0.40 seconds)
Cbc0038I Round again with cutoff of 432885
Cbc0038I Pass  10: suminf.    2.81036 (7) obj. 432885 iterations 1
Cbc0038I Pass  11: suminf.    1.44048 (7) obj. 432885 iterations 13
Cbc0038I Pass  12: suminf.    0.88760 (3) obj. 419048 iterations 11
Cbc0038I Solution found of 424067
Cbc0038I Relaxing continuous gives 424067
Cbc0038I Before mini branch and bound, 3 integers at bound fixed and 0 continuous
Cbc0038I Full problem 224 rows 165 columns, reduced to 221 rows 159 columns - 1 fixed gives 215, 153 - still too large
Cbc0038I Mini branch and bound did not improve solution (0.41 seconds)
Cbc0038I Round again with cutoff of 419993
Cbc0038I Reduced cost fixing fixed 3 variables on major pass 6
Cbc0038I Pass  13: suminf.    1.25138 (9) obj. 419993 iterations 3
Cbc0038I Pass  14: suminf.    0.72064 (4) obj. 419993 iterations 9
Cbc0038I Pass  15: suminf.    0.88760 (3) obj. 419048 iterations 7
Cbc0038I Pass  16: suminf.    1.57593 (7) obj. 417351 iterations 39
Cbc0038I Pass  17: suminf.    0.72064 (5) obj. 419993 iterations 23
Cbc0038I Pass  18: suminf.    1.92106 (8) obj. 417563 iterations 17
Cbc0038I Pass  19: suminf.    1.18774 (8) obj. 417351 iterations 6
Cbc0038I Pass  20: suminf.    2.64927 (8) obj. 413988 iterations 36
Cbc0038I Pass  21: suminf.    1.02636 (3) obj. 418264 iterations 25
Cbc0038I Pass  22: suminf.    0.72064 (3) obj. 419993 iterations 2
Cbc0038I Pass  23: suminf.    1.18774 (3) obj. 417351 iterations 15
Cbc0038I Pass  24: suminf.    0.72064 (3) obj. 419993 iterations 17
Cbc0038I Pass  25: suminf.    1.18774 (3) obj. 417351 iterations 10
Cbc0038I Pass  26: suminf.    2.11897 (7) obj. 414601 iterations 14
Cbc0038I Pass  27: suminf.    1.18774 (3) obj. 417351 iterations 15
Cbc0038I Pass  28: suminf.    1.79084 (8) obj. 413988 iterations 16
Cbc0038I Pass  29: suminf.    0.72064 (4) obj. 419993 iterations 25
Cbc0038I Pass  30: suminf.    0.72064 (4) obj. 419993 iterations 0
Cbc0038I Pass  31: suminf.    1.18774 (3) obj. 417351 iterations 3
Cbc0038I Pass  32: suminf.    1.59422 (6) obj. 413988 iterations 34
Cbc0038I Pass  33: suminf.    0.72064 (3) obj. 419993 iterations 29
Cbc0038I Pass  34: suminf.    0.72064 (3) obj. 419993 iterations 0
Cbc0038I Pass  35: suminf.    0.88760 (3) obj. 419048 iterations 4
Cbc0038I Pass  36: suminf.    1.05457 (6) obj. 419993 iterations 13
Cbc0038I Pass  37: suminf.    2.01474 (8) obj. 415265 iterations 31
Cbc0038I Pass  38: suminf.    1.16928 (3) obj. 417456 iterations 24
Cbc0038I Pass  39: suminf.    0.72064 (6) obj. 419993 iterations 13
Cbc0038I Pass  40: suminf.    1.74502 (9) obj. 413890 iterations 10
Cbc0038I Pass  41: suminf.    0.72064 (6) obj. 419993 iterations 7
Cbc0038I Pass  42: suminf.    1.69560 (7) obj. 413881 iterations 37
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 3 integers at bound fixed and 0 continuous
Cbc0038I Full problem 224 rows 165 columns, reduced to 221 rows 159 columns - 1 fixed gives 215, 153 - still too large
Cbc0038I Mini branch and bound did not improve solution (0.44 seconds)
Cbc0038I After 0.44 seconds - Feasibility pump exiting with objective of 424067 - took 0.06 seconds
Cbc0012I Integer solution of 424067.13 found by feasibility pump after 0 iterations and 0 nodes (0.44 seconds)
Cbc0031I 53 added rows had average density of 24.962264
Cbc0013I At root node, 53 cuts changed objective from 413880.6 to 424067.12 in 100 passes
Cbc0014I Cut generator 0 (Probing) - 6772 row cuts average 15.0 elements, 0 column cuts (0 active)  in 0.184 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 2954 row cuts average 49.5 elements, 0 column cuts (0 active)  in 0.077 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 2 row cuts average 3.0 elements, 0 column cuts (0 active)  in 0.031 seconds - new frequency is 8
Cbc0014I Cut generator 3 (Clique) - 2 row cuts average 3.5 elements, 0 column cuts (0 active)  in 0.014 seconds - new frequency is 8
Cbc0014I Cut generator 4 (OddWheel) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.033 seconds - new frequency is 1000
Cbc0014I Cut generator 5 (MixedIntegerRounding2) - 181 row cuts average 23.3 elements, 0 column cuts (0 active)  in 0.092 seconds - new frequency is 1
Cbc0014I Cut generator 6 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.025 seconds - new frequency is 1000
Cbc0014I Cut generator 7 (TwoMirCuts) - 393 row cuts average 19.4 elements, 0 column cuts (0 active)  in 0.022 seconds - new frequency is 1
Cbc0014I Cut generator 8 (ZeroHalf) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.127 seconds - new frequency is 1000
Cbc0011I Exiting as integer gap of 0.011692918 less than 1e-10 or 0.01%
Cbc0001I Search completed - best objective 424067.1332500006, took 6952 iterations and 0 nodes (2.14 seconds)
Cbc0035I Maximum depth 0, 3 variables fixed on reduced cost
Cgl0013I Postprocessed model is infeasible - possible tolerance issue - try without preprocessing
Total time (CPU seconds):       2.13   (Wallclock seconds):       2.24

Objective = 424067.1332500006
Traceback (most recent call last):
  File "example.py", line 9, in <module>
    model.check_optimization_results()
  File "/usr/local/lib/python3.7/site-packages/mip/model.py", line 1483, in check_optimization_results
    self.status,
mip.exceptions.InfeasibleSolution: Constraint constr(2431):
constr(2431): -10.0 x2472 -1.0 x109 -10.0 x2469 -20.0 x2470 -10.0 x2471 = -4.0
 is violated.Computed violation is 4.0.Tolerance for infeasibility is 1e-06.Solution status is OptimizationStatus.OPTIMAL.

Expected behavior Both with or without enabling preprocess should end up with the same optimal solution. Enabling preprocessing reduces runtime but in many cases, the results contain violated constraints.

Desktop (please complete the following information):

Additional context Is there any parameters that can help prevent this from happening when preprocessing is on?

sebheger commented 2 years ago

Works with preprocess=1 and preprocess=0 on cbc@2.10.7, so will be considered as fixed for next release

sebheger commented 2 years ago

Fixed by https://github.com/coin-or/python-mip/milestone/2