Incorrect optimal solution for binary MIP problem #723
Description
Tested using three versions of cbc on both Windows 11 and Ubuntu with the latest being 2.10.12 (Aug 20 2024).
cbc reports objective value of 181 while both HiGHS and SCIP report 180. I've validated the 180 solution is a valid solution.
cbc and HiGHS agree on over 60_000 variants of this same model (with only two bounds changing) and this particular one is the only one not matching.
$ bin/cbc subset_selection_model.mps.txt solve
Welcome to the CBC MILP Solver
Version: 2.10.12
Build Date: Aug 20 2024
command line - bin/cbc subset_selection_model.mps.txt solve (default strategy 1)
At line 1 NAME subset_select
At line 2 ROWS
At line 503 COLUMNS
At line 2352 RHS
At line 2355 BOUNDS
At line 3160 ENDATA
Problem subset_select has 499 rows, 804 columns and 1576 elements
Coin0008I subset_select read with 0 errors
Continuous objective value is 179.654 - 0.00 seconds
Cgl0004I processed model has 376 rows, 459 columns (459 integer (459 of which binary)) and 1122 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0038I Initial state - 12 integers unsatisfied sum - 4.84615
Cbc0038I Pass 1: suminf. 0.12500 (1) obj. 181.375 iterations 154
Cbc0038I Pass 2: suminf. 0.12500 (1) obj. 181.375 iterations 0
Cbc0038I Solution found of 184
Cbc0038I Rounding solution of 183 is better than previous of 184
Cbc0038I Before mini branch and bound, 444 integers at bound fixed and 0 continuous
Cbc0038I Full problem 376 rows 459 columns, reduced to 12 rows 14 columns
Cbc0038I Mini branch and bound improved solution from 183 to 182 (0.00 seconds)
Cbc0038I Round again with cutoff of 180.865
Cbc0038I Reduced cost fixing fixed 15 variables on major pass 2
Cbc0038I Pass 3: suminf. 1.31272 (5) obj. 180.865 iterations 48
Cbc0038I Pass 4: suminf. 1.31272 (5) obj. 180.865 iterations 0
Cbc0038I Pass 5: suminf. 0.45179 (2) obj. 180.865 iterations 84
Cbc0038I Pass 6: suminf. 0.45179 (2) obj. 180.865 iterations 82
Cbc0038I Pass 7: suminf. 0.03363 (1) obj. 180.865 iterations 91
Cbc0038I Pass 8: suminf. 0.25000 (1) obj. 180 iterations 12
Cbc0038I Pass 9: suminf. 2.30100 (8) obj. 180.865 iterations 131
Cbc0038I Pass 10: suminf. 1.03810 (6) obj. 180.865 iterations 38
Cbc0038I Pass 11: suminf. 1.25298 (5) obj. 180.865 iterations 75
Cbc0038I Pass 12: suminf. 1.25298 (5) obj. 180.865 iterations 57
Cbc0038I Pass 13: suminf. 1.70908 (5) obj. 180.865 iterations 117
Cbc0038I Pass 14: suminf. 1.38453 (4) obj. 180.865 iterations 56
Cbc0038I Pass 15: suminf. 0.33333 (2) obj. 180.583 iterations 61
Cbc0038I Pass 16: suminf. 0.21151 (2) obj. 180.865 iterations 22
Cbc0038I Pass 17: suminf. 0.53363 (3) obj. 180.865 iterations 25
Cbc0038I Pass 18: suminf. 1.00376 (6) obj. 180.865 iterations 128
Cbc0038I Pass 19: suminf. 0.67255 (9) obj. 180.865 iterations 171
Cbc0038I Pass 20: suminf. 0.96190 (6) obj. 180.865 iterations 92
Cbc0038I Pass 21: suminf. 0.66369 (2) obj. 180.865 iterations 51
Cbc0038I Pass 22: suminf. 0.31726 (2) obj. 180.865 iterations 82
Cbc0038I Pass 23: suminf. 0.51458 (2) obj. 180.865 iterations 61
Cbc0038I Pass 24: suminf. 0.28363 (1) obj. 180.865 iterations 9
Cbc0038I Pass 25: suminf. 0.31250 (1) obj. 180.75 iterations 10
Cbc0038I Pass 26: suminf. 1.19897 (8) obj. 180.865 iterations 131
Cbc0038I Pass 27: suminf. 1.19897 (8) obj. 180.865 iterations 11
Cbc0038I Pass 28: suminf. 0.69881 (3) obj. 180.865 iterations 90
Cbc0038I Pass 29: suminf. 0.58333 (2) obj. 180.75 iterations 82
Cbc0038I Pass 30: suminf. 0.78363 (3) obj. 180.865 iterations 17
Cbc0038I Pass 31: suminf. 0.78363 (3) obj. 180.865 iterations 8
Cbc0038I Pass 32: suminf. 0.62182 (2) obj. 180.865 iterations 24
Cbc0038I Rounding solution of 181 is better than previous of 182
Cbc0038I Before mini branch and bound, 401 integers at bound fixed and 0 continuous
Cbc0038I Full problem 376 rows 459 columns, reduced to 28 rows 41 columns
Cbc0038I Mini branch and bound did not improve solution (0.02 seconds)
Cbc0038I Round again with cutoff of 179.931
Cbc0038I Reduced cost fixing fixed 131 variables on major pass 3
Cbc0038I Pass 32: suminf. 0.64726 (4) obj. 179.931 iterations 6
Cbc0038I Pass 33: suminf. 0.47474 (5) obj. 179.931 iterations 167
Cbc0038I Pass 34: suminf. 0.64726 (4) obj. 179.931 iterations 93
Cbc0038I Pass 35: suminf. 1.14003 (8) obj. 179.931 iterations 89
Cbc0038I Pass 36: suminf. 0.86880 (7) obj. 179.931 iterations 40
Cbc0038I Pass 37: suminf. 0.92822 (7) obj. 179.931 iterations 102
Cbc0038I Pass 38: suminf. 6.47023 (14) obj. 179.931 iterations 102
Cbc0038I Pass 39: suminf. 4.23007 (13) obj. 179.931 iterations 29
Cbc0038I Pass 40: suminf. 4.23007 (13) obj. 179.931 iterations 0
Cbc0038I Pass 41: suminf. 5.50300 (17) obj. 179.931 iterations 99
Cbc0038I Pass 42: suminf. 5.50300 (17) obj. 179.931 iterations 0
Cbc0038I Pass 43: suminf. 5.50300 (17) obj. 179.931 iterations 28
Cbc0038I Pass 44: suminf. 6.47023 (14) obj. 179.931 iterations 16
Cbc0038I Pass 45: suminf. 4.23007 (13) obj. 179.931 iterations 35
Cbc0038I Pass 46: suminf. 4.23007 (13) obj. 179.931 iterations 0
Cbc0038I Pass 47: suminf. 5.50300 (17) obj. 179.931 iterations 101
Cbc0038I Pass 48: suminf. 5.50300 (17) obj. 179.931 iterations 0
Cbc0038I Pass 49: suminf. 5.50300 (17) obj. 179.931 iterations 34
Cbc0038I Pass 50: suminf. 6.25482 (14) obj. 179.931 iterations 50
Cbc0038I Pass 51: suminf. 6.25482 (14) obj. 179.931 iterations 13
Cbc0038I Pass 52: suminf. 5.50300 (17) obj. 179.931 iterations 126
Cbc0038I Pass 53: suminf. 4.79834 (13) obj. 179.931 iterations 50
Cbc0038I Pass 54: suminf. 4.79834 (13) obj. 179.931 iterations 24
Cbc0038I Pass 55: suminf. 6.25134 (14) obj. 179.931 iterations 43
Cbc0038I Pass 56: suminf. 4.79834 (13) obj. 179.931 iterations 17
Cbc0038I Pass 57: suminf. 4.79834 (13) obj. 179.931 iterations 27
Cbc0038I Pass 58: suminf. 6.87982 (20) obj. 179.931 iterations 19
Cbc0038I Pass 59: suminf. 6.75482 (15) obj. 179.931 iterations 7
Cbc0038I Pass 60: suminf. 6.75482 (15) obj. 179.931 iterations 1
Cbc0038I Pass 61: suminf. 5.84196 (22) obj. 179.931 iterations 142
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 401 integers at bound fixed and 0 continuous
Cbc0038I Full problem 376 rows 459 columns, reduced to 34 rows 42 columns
Cbc0038I Mini branch and bound did not improve solution (0.05 seconds)
Cbc0038I After 0.05 seconds - Feasibility pump exiting with objective of 181 - took 0.05 seconds
Cbc0012I Integer solution of 181 found by feasibility pump after 0 iterations and 0 nodes (0.05 seconds)
Cbc0038I Full problem 376 rows 459 columns, reduced to 15 rows 16 columns
Cbc0031I 1 added rows had average density of 195
Cbc0013I At root node, 16 cuts changed objective from 179.65385 to 180.20966 in 4 passes
Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 17 column cuts (17 active) in 0.001 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.002 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 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) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 22 row cuts average 183.5 elements, 0 column cuts (0 active) in 0.007 seconds - new frequency is -100
Cbc0001I Search completed - best objective 181, took 58 iterations and 0 nodes (0.07 seconds)
Cbc0035I Maximum depth 0, 128 variables fixed on reduced cost
Cuts at root node changed objective from 179.654 to 180.21
Probing was tried 4 times and created 17 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
Gomory was tried 4 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.002 seconds)
Knapsack was tried 4 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 4 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 4 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 4 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 4 times and created 22 cuts of which 0 were active after adding rounds of cuts (0.007 seconds)
ZeroHalf was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Result - Optimal solution found
Objective value: 181.00000000
Enumerated nodes: 0
Total iterations: 58
Time (CPU seconds): 0.07
Time (Wallclock seconds): 0.08
Total time (CPU seconds): 0.07 (Wallclock seconds): 0.08