[Cbc] CBC spends much time after having found a solution within specified tolerance

Fri Jun 26 05:31:21 EDT 2015

Dear CBC community,

I found the reason for the behaviour described above and a (partial) 
resolution working for me:
After checking the source of the cbcmain1 function, I suspect that in my 
instances, considerable time was spent for re-solving the original model 
after having solved a model modified by preprocessing.
Thus, by turning off preprocessing, the described behaviour disappears. 
For my instances, the overall solution time is much shorter (and more 
predictable) when turning off preprocessing.

Best regards

Michael

Am 25.06.2015 um 19:16 schrieb Michael Römer:
> Dear CBC users,
>
> using CBC for a time-critical application, I observe the following
> behaviour (I call CBC from C++ using cbcmain1), having set the ratio
> parameter (relative mipgap) to 0.02 and the strategy parameter to 0: CBC
> finds an integer solution within the tolerance rather quickly (e.g. in
> 48 seconds, see log below). After this, it outputs some statistics on
> cuts and then, seemingly nothing happens for quite a while until
> finally, after 154 seconds wallclock time, CBC stops running and outputs
> the final statistics.
>
> Is it possible so save the waiting time of 100 seconds by setting some
> parameter?
>
> thank you and best regards,
>
> Michael Römer
>
> PS: Please find below the output log after having solved the LP using
> barrier solver ---
>
> ratioGap was changed from 0 to 0.02
> Continuous objective value is 1734.85 - 0.02 seconds
> Cgl0003I 0 fixed, 2105 tightened bounds, 0 strengthened rows, 0
> substitutions
> Cgl0003I 0 fixed, 1036 tightened bounds, 0 strengthened rows, 0
> substitutions
> Cgl0003I 0 fixed, 166 tightened bounds, 0 strengthened rows, 0 substitutions
> Cgl0003I 0 fixed, 18 tightened bounds, 0 strengthened rows, 0 substitutions
> Cgl0003I 0 fixed, 3 tightened bounds, 0 strengthened rows, 0 substitutions
> Cgl0004I processed model has 7632 rows, 31409 columns (5801 integer
> (3799 of which binary)) and 127372 elements
> Cbc0038I Initial state - 82 integers unsatisfied sum - 24.2206
> Cbc0038I Pass   1: (5.97 seconds) suminf.    3.06858 (7) obj. 1775.65
> iterations 1703
> Cbc0038I Solution found of 1775.65
> Cbc0038I Branch and bound needed to clear up 7 general integers
> Cbc0038I Full problem 7632 rows 31409 columns, reduced to 5683 rows
> 23745 columns - too large
> Cbc0038I Mini branch and bound could not fix general integers
> Cbc0038I No solution found this major pass
> Cbc0038I After 11.09 seconds - Feasibility pump exiting - took 5.88 seconds
> Cbc0013I At root node, 0 cuts changed objective from 1734.8473 to
> 1734.8473 in 1 passes
> Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 26
> column cuts (26 active)  in 0.042 seconds - new frequency is 1
> Cbc0014I Cut generator 1 (Gomory) - 0 row cuts average 0.0 elements, 0
> column cuts (0 active)  in 0.023 seconds - new frequency is -100
> Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0
> column cuts (0 active)  in 0.020 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.004 seconds - new frequency
> is -100
> Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements,
> 0 column cuts (0 active)  in 0.016 seconds - new frequency is -100
> Cbc0010I After 0 nodes, 1 on tree, 1e+050 best solution, best possible
> 1734.8473 (12.82 seconds)
> Cbc0004I Integer solution of 1736.0821 found after 13396 iterations and
> 30 nodes (48.42 seconds)
> Cbc0011I Exiting as integer gap of 1.2348315 less than 1e-010 or 2%
> Cbc0001I Search completed - best objective 1736.082130858523, took 13463
> iterations and 31 nodes (48.65 seconds)
> Cbc0032I Strong branching done 590 times (23681 iterations), fathomed 0
> nodes and fixed 0 variables
> Cbc0035I Maximum depth 16, 2420 variables fixed on reduced cost
> Cuts at root node changed objective from 1734.85 to 1734.85
> Probing was tried 13 times and created 57 cuts of which 0 were active
> after adding rounds of cuts (0.117 seconds)
> Gomory was tried 1 times and created 0 cuts of which 0 were active after
> adding rounds of cuts (0.023 seconds)
> Knapsack was tried 1 times and created 0 cuts of which 0 were active
> after adding rounds of cuts (0.020 seconds)
> Clique was tried 1 times and created 0 cuts of which 0 were active after
> adding rounds of cuts (0.000 seconds)
> MixedIntegerRounding2 was tried 1 times and created 0 cuts of which 0
> were active after adding rounds of cuts (0.004 seconds)
> FlowCover was tried 1 times and created 0 cuts of which 0 were active
> after adding rounds of cuts (0.016 seconds)
> TwoMirCuts was tried 1 times and created 0 cuts of which 0 were active
> after adding rounds of cuts (0.058 seconds)
>
> Result - Optimal solution found (within gap tolerance)
>
> Objective value:                1736.08213086
> Lower bound:                    1734.847
> Gap:                            0.00
> Enumerated nodes:               31
> Total iterations:               13463
> Time (CPU seconds):             154.43
> Time (Wallclock seconds):       154.43
>
> Total time (CPU seconds):       161.81   (Wallclock seconds): 161.81
>
>
>

-- 
Lehrstuhl für Wirtschaftsinformatik und Operations Research
Juristische und Wirtschaftswissenschaftliche Fakultät

Martin-Luther-Universität Halle-Wittenberg
Universitätsring 3
06108 Halle / Saale

Tel. (+49) 345 - 55 23 404
Fax (+49) 345 - 55 27 194

mailto:michael.roemer at wiwi.uni-halle.de