search

coin-or / Cbc.old

This is a mirror of the subversion repository on COIN-OR
https://projects.coin-or.org/Cbc
Other
89 stars 30 forks source link

[Trac #107] CBC 2.6 returns infeasible for feasible model #97

Open s-c-e opened 5 years ago

s-c-e commented 5 years ago

image

Attachment: https://github.com/s-c-e/cbc-trac-migration-attachments/blob/master/trac-ticket-107.zip

For the attached small MIP model CBC 2.6 returns (proven) infeasible but the model is feasible (the 0 solution is a valid solution).

Thanks,

Marcel

s-c-e commented 5 years ago

Here is the log from running this model with the standalone CBC solver like this:

a@A:~/Documents/cbc-debug$ cbc -import par4.lp solve > log.log 2>&1
Welcome to the CBC MILP Solver 
Version: 2.8.12 
Build Date: Feb 22 2016 

command line - cbc -import par4.lp solve (default strategy 1)
Continuous objective value is -0.999992 - 0.00 seconds
Cgl0004I processed model has 2 rows, 8 columns (7 integer) and 15 elements
Cbc0038I Pass   1: suminf.    0.00000 (0) obj. -0.861659 iterations 1
Cbc0038I Solution found of -0.861659
Cbc0038I Before mini branch and bound, 6 integers at bound fixed and 0 continuous
Cbc0038I Full problem 2 rows 8 columns, reduced to 0 rows 0 columns
Cbc0038I Mini branch and bound did not improve solution (0.00 seconds)
Cbc0038I Round again with cutoff of -0.875501
Cbc0038I Reduced cost fixing fixed 1 variables on major pass 2
Cbc0038I Pass   2: suminf.    0.02679 (1) obj. -0.875501 iterations 1
Cbc0038I Pass   3: suminf.    0.34342 (1) obj. -0.875501 iterations 2
Cbc0038I Pass   4: suminf.    0.45642 (1) obj. -0.875501 iterations 1
Cbc0038I Pass   5: suminf.    0.45905 (1) obj. -0.875501 iterations 4
Cbc0038I Pass   6: suminf.    0.45905 (1) obj. -0.875501 iterations 0
Cbc0038I Pass   7: suminf.    0.14070 (1) obj. -0.999992 iterations 2
Cbc0038I Pass   8: suminf.    0.25370 (1) obj. -0.875501 iterations 1
Cbc0038I Pass   9: suminf.    0.00000 (0) obj. -0.875501 iterations 2
Cbc0038I Solution found of -0.875501
Cbc0038I Before mini branch and bound, 3 integers at bound fixed and 0 continuous
Cbc0038I Full problem 2 rows 8 columns, reduced to 2 rows 5 columns
Cbc0038I Mini branch and bound improved solution from -0.875501 to -0.951659 (0.00 seconds)
Cbc0038I Round again with cutoff of -0.961333
Cbc0038I Reduced cost fixing fixed 1 variables on major pass 3
Cbc0038I Pass  10: suminf.    0.19292 (1) obj. -0.961333 iterations 0
Cbc0038I Pass  11: suminf.    0.34342 (1) obj. -0.961333 iterations 2
Cbc0038I Pass  12: suminf.    0.37851 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  13: suminf.    0.07594 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  14: suminf.    0.04085 (1) obj. -0.999992 iterations 1
Cbc0038I Pass  15: suminf.    0.07594 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  16: suminf.    0.37246 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  17: suminf.    0.33737 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  18: suminf.    0.37246 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  19: suminf.    0.03830 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  20: suminf.    0.19607 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  21: suminf.    0.37246 (1) obj. -0.961333 iterations 2
Cbc0038I Pass  22: suminf.    0.04085 (1) obj. -0.961333 iterations 2
Cbc0038I Pass  23: suminf.    0.04085 (1) obj. -0.961333 iterations 0
Cbc0038I Pass  24: suminf.    0.34342 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  25: suminf.    0.37851 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  26: suminf.    0.34342 (1) obj. -0.999992 iterations 1
Cbc0038I Pass  27: suminf.    0.04085 (1) obj. -0.999992 iterations 1
Cbc0038I Pass  28: suminf.    0.07594 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  29: suminf.    0.04085 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  30: suminf.    0.36006 (1) obj. -0.961333 iterations 2
Cbc0038I Pass  31: suminf.    0.32497 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  32: suminf.    0.36006 (1) obj. -0.999992 iterations 1
Cbc0038I Pass  33: suminf.    0.35552 (1) obj. -0.999992 iterations 2
Cbc0038I Pass  34: suminf.    0.39061 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  35: suminf.    0.35552 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  36: suminf.    0.32736 (1) obj. -0.961333 iterations 5
Cbc0038I Pass  37: suminf.    0.22542 (1) obj. -0.999992 iterations 2
Cbc0038I Pass  38: suminf.    0.26051 (1) obj. -0.961333 iterations 1
Cbc0038I Pass  39: suminf.    0.22542 (1) obj. -0.961333 iterations 1
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 1 integers at bound fixed and 0 continuous
Cbc0038I Full problem 2 rows 8 columns, reduced to 2 rows 7 columns
Cbc0038I Mini branch and bound improved solution from -0.951659 to -0.964992 (0.01 seconds)
Cbc0038I Round again with cutoff of -0.975499
Cbc0038I Reduced cost fixing fixed 1 variables on major pass 4
Cbc0038I Pass  39: suminf.    0.22034 (1) obj. -0.975499 iterations 0
Cbc0038I Pass  40: suminf.    0.34342 (1) obj. -0.975499 iterations 2
Cbc0038I Pass  41: suminf.    0.36565 (1) obj. -0.975499 iterations 1
Cbc0038I Pass  42: suminf.    0.22034 (1) obj. -0.975499 iterations 1
Cbc0038I Pass  43: suminf.    0.04085 (1) obj. -0.999992 iterations 3
Cbc0038I Pass  44: suminf.    0.06308 (1) obj. -0.975499 iterations 1
Cbc0038I Pass  45: suminf.    0.04085 (1) obj. -0.975499 iterations 1
Cbc0038I Pass  46: suminf.    0.04085 (1) obj. -0.975499 iterations 0
Cbc0038I Pass  47: suminf.    0.34342 (1) obj. -0.975499 iterations 1
Cbc0038I Pass  48: suminf.    0.34342 (1) obj. -0.975499 iterations 0
Cbc0038I Pass  49: suminf.    0.34342 (1) obj. -0.975499 iterations 0
Cbc0038I Pass  50: suminf.    0.05588 (1) obj. -0.975499 iterations 2
Cbc0038I Pass  51: suminf.    0.16287 (1) obj. -0.975499 iterations 1
Cbc0038I Pass  52: suminf.    0.04085 (1) obj. -0.999992 iterations 2
Cbc0038I Pass  53: suminf.    0.36006 (1) obj. -0.999992 iterations 2
Cbc0038I Pass  54: suminf.    0.33783 (1) obj. -0.975499 iterations 1
Cbc0038I Pass  55: suminf.    0.36006 (1) obj. -0.975499 iterations 1
Cbc0038I Pass  56: suminf.    0.36006 (1) obj. -0.975499 iterations 0
Cbc0038I Pass  57: suminf.    0.15326 (1) obj. -0.975499 iterations 2
Cbc0038I Pass  58: suminf.    0.17549 (1) obj. -0.999992 iterations 1
Cbc0038I Pass  59: suminf.    0.15326 (1) obj. -0.975499 iterations 1
Cbc0038I Pass  60: suminf.    0.02034 (1) obj. -0.975499 iterations 3
Cbc0038I Pass  61: suminf.    0.02034 (1) obj. -0.975499 iterations 0
Cbc0038I Pass  62: suminf.    0.43722 (1) obj. -0.975499 iterations 2
Cbc0038I Pass  63: suminf.    0.45945 (1) obj. -0.975499 iterations 1
Cbc0038I Pass  64: suminf.    0.34741 (1) obj. -0.975499 iterations 2
Cbc0038I Pass  65: suminf.    0.14070 (1) obj. -0.999992 iterations 2
Cbc0038I Pass  66: suminf.    0.16293 (1) obj. -0.975499 iterations 1
Cbc0038I Pass  67: suminf.    0.22542 (1) obj. -0.975499 iterations 4
Cbc0038I Pass  68: suminf.    0.24765 (1) obj. -0.975499 iterations 1
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 1 integers at bound fixed and 0 continuous
Cbc0038I Full problem 2 rows 8 columns, reduced to 2 rows 7 columns
Cbc0038I Mini branch and bound did not improve solution (0.01 seconds)
Cbc0038I After 0.01 seconds - Feasibility pump exiting with objective of -0.964992 - took 0.01 seconds
Cbc0012I Integer solution of -0.96499214 found by feasibility pump after 0 iterations and 0 nodes (0.01 seconds)
Cbc0038I Full problem 2 rows 8 columns, reduced to 2 rows 5 columns
Cbc0038I Full problem 2 rows 8 columns, reduced to 2 rows 6 columns
Cbc0031I 4 added rows had average density of 4.5
Cbc0013I At root node, 11 cuts changed objective from -0.999992 to -0.96499214 in 7 passes
Cbc0014I Cut generator 0 (Probing) - 2 row cuts average 2.0 elements, 1 column cuts (1 active)  in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 17 row cuts average 5.0 elements, 0 column cuts (3 active)  in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 9 row cuts average 3.4 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is 1
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) - 7 row cuts average 7.4 elements, 0 column cuts (1 active)  in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 6 (TwoMirCuts) - 28 row cuts average 5.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0001I Search completed - best objective -0.96499214, took 29 iterations and 0 nodes (0.01 seconds)
Cbc0035I Maximum depth 0, 1 variables fixed on reduced cost
Cuts at root node changed objective from -0.999992 to -0.964992
Probing was tried 7 times and created 3 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 7 times and created 17 cuts of which 3 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 7 times and created 9 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 7 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 7 times and created 7 cuts of which 1 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 7 times and created 28 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                -0.96499214
Enumerated nodes:               0
Total iterations:               29
Time (CPU seconds):             0.01
Time (Wallclock seconds):       0.01

Total time (CPU seconds):       0.01   (Wallclock seconds):       0.01
s-c-e commented 5 years ago

@tkralphs and @h-g-s because this model returns as optimal under a newer version of CBC, I think this ticket can be marked as resolved/closed.