[Cbc] CBC not returning the best solution it found
Jack Vreeken
jack at vreeken.me
Tue Oct 1 05:47:27 EDT 2019
I'm running into a weird case with CBC (master), and feel like it's maybe
something obvious that I missed. I set an initial solution using
setBestSolution() before starting B&B with CbcMain1. I set a timeout of 120
seconds, and then I see the following two things happening:
- It terminates at about ~104 seconds, instead of 120 seconds. This ~15 second
difference is there also for say a maximum runtime of 30 seconds (will
terminate after 15 seconds)
- It often (?) returns the wrong solution. I have attached two logs below of
two runs of (very similiar, if not equal) problems. Most of the time it does
a "Restoring heuristic best solution", returning a solution that is actually
worse than the one it found during B&B. In those cases it also returns a
secondaryStatus of 0 instead of 4.
*******************************************************************************
Run 1 - Timeout too early, but returns right result
*******************************************************************************
Coin0506I Presolve 7046 (-15058) rows, 1946 (-5629) columns and 15810 (-30899) elements
Clp0006I 0 Obj 0 Primal inf 1725.6262 (1546)
Clp0006I 215 Obj 0.11201553 Primal inf 577.62577 (1451)
Clp0006I 430 Obj 0.33153121 Primal inf 616.57147 (1321)
Clp0006I 645 Obj 0.57757338 Primal inf 1098 (1196)
Clp0006I 860 Obj 0.73695562 Primal inf 525.21976 (1125)
Clp0006I 1075 Obj 0.77262032 Primal inf 336.03453 (1044)
Clp0006I 1290 Obj 0.78551133 Primal inf 611.58542 (907)
Clp0006I 1505 Obj 0.79084443 Primal inf 12061.126 (1145)
Clp0006I 1720 Obj 0.84797638 Primal inf 2369.8756 (882)
Clp0006I 1935 Obj 0.87578934 Primal inf 1592.1243 (551)
Clp0006I 2150 Obj 0.87585535 Primal inf 464.0705 (401)
Clp0006I 2365 Obj 0.87588966 Primal inf 1723.0034 (606)
Clp0006I 2580 Obj 0.87591826 Primal inf 1095.0581 (431)
Clp0006I 2795 Obj 0.87685215 Primal inf 3226.9799 (472)
Clp0006I 3010 Obj 0.88625324 Primal inf 165.86053 (174)
Clp0006I 3138 Obj 0.88929057
Clp0006I 3138 Obj 0.88912208 Dual inf 5.150592e-06 (2)
Clp0000I Optimal - objective value 0.88912208
Coin0511I After Postsolve, objective 0.88912208, infeasibilities - dual 1.2566177e-05 (2), primal 0 (0)
Coin0512I Presolved model was optimal, full model needs cleaning up
Clp0006I 0 Obj 0.88912208 Dual inf 5.150592e-06 (2)
Clp0000I Optimal - objective value 0.88912208
Clp0032I Optimal objective 0.8891220839 - 3138 iterations time 0.292, Presolve 0.03
Cbc0045I Solution with objective value 0.889122 saved
Welcome to the CBC MILP Solver
Version: Trunk (unstable)
Build Date: Oct 1 2019
command line - CbcInterface -cuts off -loglevel 1 -seconds 120 -solve -quit (default strategy 1)
seconds was changed from 1e+100 to 120
Continuous objective value is -3.15e-14 - 0.55 seconds
Cgl0003I 0 fixed, 0 tightened bounds, 1938 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 589 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 407 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 179 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 57 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 35 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 15 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 9 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 6 strengthened rows, 0 substitutions
Cgl0004I processed model has 13254 rows, 4075 columns (665 integer (665 of which binary)) and 33971 elements
Cbc0038I Full problem 13254 rows 4075 columns, reduced to 9732 rows 2923 columns - too large
Cbc0010I After 0 nodes, 1 on tree, 0.88912208 best solution, best possible 0 (20.27 seconds)
Cbc0038I Full problem 13254 rows 4075 columns, reduced to 9323 rows 2789 columns - too large
Cbc0038I Full problem 13254 rows 4075 columns, reduced to 9045 rows 2673 columns - too large
Cbc0010I After 100 nodes, 76 on tree, 0.88912208 best solution, best possible 0 (56.58 seconds)
Cbc0038I Full problem 13254 rows 4075 columns, reduced to 8593 rows 2548 columns - too large
Cbc0010I After 200 nodes, 144 on tree, 0.88912208 best solution, best possible 0 (77.12 seconds)
Cbc0038I Full problem 13254 rows 4075 columns, reduced to 8095 rows 2378 columns - too large
Cbc0010I After 300 nodes, 211 on tree, 0.88912208 best solution, best possible 0 (92.39 seconds)
Cbc0004I Integer solution of 0.036708457 found after 135829 iterations and 311 nodes (94.44 seconds)
Cbc0020I Exiting on maximum time
Cbc0005I Partial search - best objective 0.036708457 (best possible 0), took 157432 iterations and 331 nodes (103.93 seconds)
Cbc0032I Strong branching done 2472 times (157180 iterations), fathomed 0 nodes and fixed 33 variables
Cbc0035I Maximum depth 199, 0 variables fixed on reduced cost
Cuts at root node changed objective from 0 to 0
Cgl0013I Postprocessed model is infeasible - possible tolerance issue - try without preprocessing
Result - Stopped on time limit
Objective value: 0.03597342
Lower bound: 0.000
Gap: inf
Enumerated nodes: 331
Total iterations: 157432
Time (CPU seconds): 104.90
Time (Wallclock seconds): 104.90
Total time (CPU seconds): 104.90 (Wallclock seconds): 104.91
provenOptimal: 0, status: 1, secondaryStatus: 4
*******************************************************************************
Run 2 - Timeout too early, and returns wrong result
*******************************************************************************
Coin0506I Presolve 7046 (-15058) rows, 1946 (-5629) columns and 15810 (-30899) elements
Clp0006I 0 Obj 0 Primal inf 1725.6262 (1546)
Clp0006I 215 Obj 0.11201553 Primal inf 577.62577 (1451)
Clp0006I 430 Obj 0.33153121 Primal inf 616.57147 (1321)
Clp0006I 645 Obj 0.57757338 Primal inf 1098 (1196)
Clp0006I 860 Obj 0.73695562 Primal inf 525.21976 (1125)
Clp0006I 1075 Obj 0.77262032 Primal inf 336.03453 (1044)
Clp0006I 1290 Obj 0.78551133 Primal inf 611.58542 (907)
Clp0006I 1505 Obj 0.79084443 Primal inf 12061.126 (1145)
Clp0006I 1720 Obj 0.84797638 Primal inf 2369.8756 (882)
Clp0006I 1935 Obj 0.87578934 Primal inf 1592.1243 (551)
Clp0006I 2150 Obj 0.87585535 Primal inf 464.0705 (401)
Clp0006I 2365 Obj 0.87588966 Primal inf 1723.0034 (606)
Clp0006I 2580 Obj 0.87591826 Primal inf 1095.0581 (431)
Clp0006I 2795 Obj 0.87685215 Primal inf 3226.9799 (472)
Clp0006I 3010 Obj 0.88625324 Primal inf 165.86053 (174)
Clp0006I 3138 Obj 0.88929057
Clp0006I 3138 Obj 0.88912208 Dual inf 5.150592e-06 (2)
Clp0000I Optimal - objective value 0.88912208
Coin0511I After Postsolve, objective 0.88912208, infeasibilities - dual 1.2566177e-05 (2), primal 0 (0)
Coin0512I Presolved model was optimal, full model needs cleaning up
Clp0006I 0 Obj 0.88912208 Dual inf 5.150592e-06 (2)
Clp0000I Optimal - objective value 0.88912208
Clp0032I Optimal objective 0.8891220839 - 3138 iterations time 0.262, Presolve 0.03
Cbc0045I Solution with objective value 0.889122 saved
Welcome to the CBC MILP Solver
Version: Trunk (unstable)
Build Date: Oct 1 2019
command line - CbcInterface -cuts off -loglevel 1 -seconds 120 -solve -quit (default strategy 1)
seconds was changed from 1e+100 to 120
Continuous objective value is -3.15e-14 - 0.54 seconds
Cgl0003I 0 fixed, 0 tightened bounds, 1938 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 589 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 407 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 179 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 57 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 35 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 15 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 9 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 6 strengthened rows, 0 substitutions
Cgl0004I processed model has 13254 rows, 4075 columns (665 integer (665 of which binary)) and 33971 elements
Cbc0038I Full problem 13254 rows 4075 columns, reduced to 9732 rows 2923 columns - too large
Cbc0010I After 0 nodes, 1 on tree, 0.88912208 best solution, best possible 0 (5.81 seconds)
Cbc0038I Full problem 13254 rows 4075 columns, reduced to 9323 rows 2789 columns - too large
Cbc0038I Full problem 13254 rows 4075 columns, reduced to 9045 rows 2673 columns - too large
Cbc0010I After 100 nodes, 76 on tree, 0.88912208 best solution, best possible 0 (42.97 seconds)
Cbc0038I Full problem 13254 rows 4075 columns, reduced to 8593 rows 2548 columns - too large
Cbc0010I After 200 nodes, 144 on tree, 0.88912208 best solution, best possible 0 (63.64 seconds)
Cbc0038I Full problem 13254 rows 4075 columns, reduced to 8095 rows 2378 columns - too large
Cbc0010I After 300 nodes, 211 on tree, 0.88912208 best solution, best possible 0 (79.02 seconds)
Cbc0004I Integer solution of 0.036708457 found after 135829 iterations and 311 nodes (81.06 seconds)
Cbc0010I After 400 nodes, 230 on tree, 0.036708457 best solution, best possible 0 (105.97 seconds)
Cbc0010I After 500 nodes, 169 on tree, 0.036708457 best solution, best possible 0 (106.45 seconds)
Cbc0010I After 600 nodes, 105 on tree, 0.036708457 best solution, best possible 0 (106.91 seconds)
Cbc0010I After 700 nodes, 38 on tree, 0.036708457 best solution, best possible 0 (107.38 seconds)
Cbc0001I Search completed - best objective 0.03670845686554153, took 190792 iterations and 744 nodes (107.57 seconds)
Cbc0032I Strong branching done 2754 times (191063 iterations), fathomed 0 nodes and fixed 48 variables
Cbc0035I Maximum depth 199, 0 variables fixed on reduced cost
Cuts at root node changed objective from 0 to 0
Restoring heuristic best solution of 0.889122
Result - Optimal solution found
Objective value: 0.88912208
Enumerated nodes: 744
Total iterations: 190792
Time (CPU seconds): 107.61
Time (Wallclock seconds): 107.62
Total time (CPU seconds): 107.62 (Wallclock seconds): 107.63
provenOptimal: 1, status: 0, secondaryStatus: 0
More information about the Cbc
mailing list