[Cbc] CBC Performance on Rostering Problem
Haroldo Gambini Santos
haroldo.santos at gmail.com
Tue Jul 25 13:45:13 EDT 2017
Hi Pieter,
Em 25-07-2017 05:22, Pieter Zieschang1 escreveu:
> Hello,
> i'd like to use COIN CBC for solving a Rostering Problem, but
> performance is either bad or it won't solve at all.
"won't solve at all" means (i) no feasible solution found or (ii)
optimality not proved ?
>
> Below is the log with the best parameters i happened to find.
> Preprocessing with the standard SOS might geht stuck at 1e+9, which is
> also commented with "Possible Preprocessing Problem - try without".
>
> Can someone please suggest parameters which might work better?
I found that the option
*multiple 2*
Is quite useful, since an different fractional solutions are generated
at the root note and more cuts (and rounding heuristics) are executed
*zero ifmo**ve**
*zero half cuts are usually good too
It would be good too look at your .lp
> Thanks.
>
> I also compared it with CPLEX, and it solves to optimality in 70
> seconds at default settings.
>
>
> The MPS file is 27 MB so i can't add it to a pastebin. Zipped it's
> still 2,5 MB.
>
>
>
> $ ./cbc 23844-T1_0.mps -threads=4 timemode=elapsed -seconds=4000
> -keepNames=on -dualt=1e-06 -perturb=on -pertvalue=59 -constraint=on
> -cuts=on -clique=forceon -zero=forceon -preprocess=aggregate
> -probing=forceonstrong -passt=30 -ratiogap=0.001 -solve
> -solution=23844-T1_0.solution.txt
> Welcome to the CBC MILP Solver
> Version: 2.9
> Build Date: Jul 18 2017
> Revision Number: 2339
>
> command line - ./cbc 23844-T1_0.mps -threads=4 timemode=elapsed
> -seconds=4000 -keepNames=on -dualt=1e-06 -perturb=on -pertvalue=59
> -constraint=on -cuts=on -clique=forceon -zero=forceon
> -preprocess=aggregate -probing=forceonstrong -passt=30 -ratiogap=0.001
> -solve -solution=23844-T1_0.solution.txt (default strategy 1)
> At line 1 NAME ES FREE
> At line 2 ROWS
> At line 60579 COLUMNS
> At line 665087 RHS
> At line 725663 RANGES
> At line 725664 BOUNDS
> At line 729233 ENDATA
> Problem ES has 60575 rows, 47237 columns and 589221 elements
> Coin0008I ES read with 0 errors
> threads was changed from 0 to 4
> Option for timeMode changed from cpu to elapsed
> seconds was changed from 1e+100 to 4000
> dualTolerance was changed from 1e-07 to 1e-06
> pertValue was changed from 50 to 59
> Option for constraintfromCutoff changed from off to on
> Option for cliqueCuts changed from on to forceOn
> Option for zeroHalfCuts changed from off to forceOn
> Option for preprocess changed from sos to aggregate
> Option for probingCuts changed from on to forceOnStrong
> passTreeCuts was changed from 10 to 30
> ratioGap was changed from 0 to 0.001
> Continuous objective value is 376993 - 15.42 seconds
> Cgl0012I Added 426 variables (from 216 rows) with 3468 elements
> Cgl0011I 15201 variables made integer
> Cgl0002I 3215 variables fixed
> Cgl0003I 0 fixed, 8618 tightened bounds, 17171 strengthened rows, 1527
> substitutions
> Cgl0003I 0 fixed, 0 tightened bounds, 13450 strengthened rows, 0
> substitutions
> Cgl0003I 0 fixed, 0 tightened bounds, 11586 strengthened rows, 0
> substitutions
> Cgl0003I 0 fixed, 0 tightened bounds, 9864 strengthened rows, 0
> substitutions
> Cgl0003I 0 fixed, 0 tightened bounds, 8234 strengthened rows, 0
> substitutions
> Cgl0003I 0 fixed, 0 tightened bounds, 6963 strengthened rows, 0
> substitutions
> Cgl0003I 0 fixed, 0 tightened bounds, 5873 strengthened rows, 0
> substitutions
> Cgl0003I 0 fixed, 0 tightened bounds, 4780 strengthened rows, 0
> substitutions
> Cgl0003I 0 fixed, 0 tightened bounds, 3741 strengthened rows, 0
> substitutions
> Cgl0004I processed model has 24369 rows, 20513 columns (20424 integer
> (11796 of which binary)) and 271657 elements
> Cbc0038I Initial state - 1079 integers unsatisfied sum - 328.79
> Cbc0038I Pass 1: (109.12 seconds) suminf. 6.66667 (20) obj.
> 8.04436e+08 iterations 17817
> Cbc0038I Pass 2: (109.16 seconds) suminf. 6.66667 (20) obj.
> 8.04436e+08 iterations 202
> Cbc0038I Pass 3: (109.19 seconds) suminf. 0.00000 (0) obj.
> 8.04417e+08 iterations 46
> Cbc0038I Solution found of 8.04417e+08
> Cbc0038I Relaxing continuous gives 8.04417e+08
> Cbc0038I Cleaned solution of 8.04417e+08
> Cbc0038I Before mini branch and bound, 18679 integers at bound fixed
> and 9229 continuous of which 12 were internal integer and 0 internal
> continuous
> Cbc0038I Full problem 24369 rows 20513 columns, reduced to 2217 rows
> 1443 columns
> Cbc0038I Mini branch and bound improved solution from 8.04417e+08 to
> 2.00979e+08 (109.64 seconds)
> Cbc0038I Round again with cutoff of 1.80919e+08
> Cbc0038I Pass 4: (111.38 seconds) suminf. 6.89402 (21) obj.
> 1.80919e+08 iterations 210
> Cbc0038I Pass 5: (111.44 seconds) suminf. 6.89402 (21) obj.
> 1.80919e+08 iterations 222
> Cbc0038I Pass 6: (111.52 seconds) suminf. 0.00000 (0) obj.
> 1.80919e+08 iterations 225
> Cbc0038I Solution found of 1.80919e+08
> Cbc0038I Branch and bound needed to clear up 2 general integers
> Cbc0038I Full problem 24371 rows 20513 columns, reduced to 0 rows 0
> columns
> Cbc0038I Cleaned solution of 1.03622e+08
> Cbc0038I Before mini branch and bound, 18716 integers at bound fixed
> and 9266 continuous of which 12 were internal integer and 0 internal
> continuous
> Cbc0038I Full problem 24369 rows 20513 columns, reduced to 2170 rows
> 1396 columns
> Cbc0038I Mini branch and bound improved solution from 1.03622e+08 to
> 813382 (112.36 seconds)
> Cbc0038I Round again with cutoff of 726105
> Cbc0038I Reduced cost fixing fixed 2 variables on major pass 3
> Cbc0038I Pass 7: (124.61 seconds) suminf. 70.08127 (177) obj.
> 726105 iterations 9037
> Cbc0038I Pass 8: (128.18 seconds) suminf. 23.89949 (102) obj.
> 726105 iterations 4469
> Cbc0038I Pass 9: (135.43 seconds) suminf. 0.97161 (416) obj.
> 726105 iterations 10848
> Cbc0038I Pass 10: (148.48 seconds) suminf. 0.01724 (8) obj. 726105
> iterations 16355
> Cbc0038I No solution found this major pass
> Cbc0038I After 148.48 seconds - Feasibility pump exiting with
> objective of 813382 - took 51.20 seconds
> Cbc0012I Integer solution of 813382 found by feasibility pump after 0
> iterations and 0 nodes (148.50 seconds)
> Cbc0038I Full problem 24369 rows 20513 columns, reduced to 1740 rows
> 960 columns
> Cbc0012I Integer solution of 786632 found by RINS after 0 iterations
> and 0 nodes (154.70 seconds)
> Cbc0031I 79 added rows had average density of 97.139241
> Cbc0013I At root node, 79 cuts changed objective from 376997.5 to
> 382210 in 10 passes
> Cbc0014I Cut generator 0 (Probing) - 314 row cuts average 10.7
> elements, 125 column cuts (198 active) in 27.244 seconds - new
> frequency is 1
> Cbc0014I Cut generator 1 (Gomory) - 358 row cuts average 332.1
> elements, 0 column cuts (0 active) in 4.132 seconds - new frequency is 1
> Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements,
> 0 column cuts (0 active) in 0.259 seconds - new frequency is 1000
> Cbc0014I Cut generator 3 (Clique) - 14 row cuts average 3.8 elements,
> 0 column cuts (0 active) in 0.044 seconds - new frequency is 1
> Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 6 row cuts average
> 131.5 elements, 0 column cuts (0 active) in 0.384 seconds - new
> frequency is 2
> Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0
> elements, 0 column cuts (0 active) in 0.153 seconds - new frequency
> is 1000
> Cbc0014I Cut generator 6 (TwoMirCuts) - 385 row cuts average 90.3
> elements, 0 column cuts (0 active) in 3.520 seconds - new frequency is 1
> Cbc0014I Cut generator 7 (ZeroHalf) - 20 row cuts average 5.1
> elements, 0 column cuts (0 active) in 9.168 seconds - new frequency is 1
> Cbc0010I After 0 nodes, 1 on tree, 786632 best solution, best possible
> 382210 (248.85 seconds)
> Cbc0012I Integer solution of 737006 found by heuristic after 153897
> iterations and 41 nodes (384.76 seconds)
> Cbc0012I Integer solution of 646257 found by heuristic after 170222
> iterations and 49 nodes (396.54 seconds)
> Cbc0012I Integer solution of 403185 found by heuristic after 241273
> iterations and 92 nodes (462.37 seconds)
> Cbc0010I After 100 nodes, 55 on tree, 403185 best solution, best
> possible 382309.99 (472.13 seconds)
> Cbc0010I After 200 nodes, 105 on tree, 403185 best solution, best
> possible 382309.99 (598.06 seconds)
> Cbc0012I Integer solution of 397585 found by heuristic after 599679
> iterations and 295 nodes (726.93 seconds)
> Cbc0012I Integer solution of 382710 found by heuristic after 605611
> iterations and 297 nodes (731.82 seconds)
> Cbc0010I After 300 nodes, 62 on tree, 382710 best solution, best
> possible 382309.99 (733.95 seconds)
> Cbc0010I After 400 nodes, 103 on tree, 382710 best solution, best
> possible 382309.99 (826.14 seconds)
> Cbc0010I After 500 nodes, 133 on tree, 382710 best solution, best
> possible 382309.99 (928.93 seconds)
> Cbc0010I After 600 nodes, 156 on tree, 382710 best solution, best
> possible 382309.99 (1020.12 seconds)
> Cbc0010I After 700 nodes, 173 on tree, 382710 best solution, best
> possible 382309.99 (1102.31 seconds)
> Cbc0010I After 800 nodes, 203 on tree, 382710 best solution, best
> possible 382309.99 (1183.09 seconds)
> Cbc0010I After 900 nodes, 228 on tree, 382710 best solution, best
> possible 382309.99 (1263.68 seconds)
> Cbc0010I After 1000 nodes, 247 on tree, 382710 best solution, best
> possible 382309.99 (1334.03 seconds)
> ...
> Cbc0010I After 5700 nodes, 440 on tree, 382710 best solution, best
> possible 382309.99 (3730.53 seconds)
> Cbc0010I After 5800 nodes, 437 on tree, 382710 best solution, best
> possible 382309.99 (3765.98 seconds)
> Cbc0010I After 5900 nodes, 446 on tree, 382710 best solution, best
> possible 382309.99 (3812.35 seconds)
> Cbc0010I After 6000 nodes, 440 on tree, 382710 best solution, best
> possible 382309.99 (3854.76 seconds)
> Cbc0010I After 6100 nodes, 431 on tree, 382710 best solution, best
> possible 382309.99 (3890.37 seconds)
> Cbc0030I Thread 0 used 1485 times, waiting to start 2.8537025, 9193
> locks, 3.2881584 locked, 0.05332756 waiting for locks
> Cbc0030I Thread 1 used 1611 times, waiting to start 18.775235, 9954
> locks, 3.5816755 locked, 0.032725334 waiting for locks
> Cbc0030I Thread 2 used 1578 times, waiting to start 22.087676, 9821
> locks, 3.5143106 locked, 0.039180279 waiting for locks
> Cbc0030I Thread 3 used 1517 times, waiting to start 47.964042, 9311
> locks, 3.4258959 locked, 0.03879118 waiting for locks
> Cbc0030I Main thread 3671.0922 waiting for threads, 12458 locks,
> 0.03922987 locked, 0.0096375942 waiting for locks
> Cbc0020I Exiting on maximum time
> Cbc0005I Partial search - best objective 382710 (best possible
> 382309.99), took 6815530 iterations and 6188 nodes (3929.06 seconds)
> Cbc0032I Strong branching done 25448 times (2168378 iterations),
> fathomed 135 nodes and fixed 1192 variables
> Cbc0035I Maximum depth 51, 296493 variables fixed on reduced cost
> Cuts at root node changed objective from 376998 to 382210
> Probing was tried 6524 times and created 155973 cuts of which 365 were
> active after adding rounds of cuts (713.728 seconds)
> Gomory was tried 1480 times and created 4739 cuts of which 0 were
> active after adding rounds of cuts (853.292 seconds)
> Knapsack was tried 55 times and created 14 cuts of which 0 were active
> after adding rounds of cuts (1.879 seconds)
> Clique was tried 6359 times and created 9244 cuts of which 0 were
> active after adding rounds of cuts (55.088 seconds)
> MixedIntegerRounding2 was tried 3192 times and created 221 cuts of
> which 0 were active after adding rounds of cuts (263.052 seconds)
> FlowCover was tried 55 times and created 0 cuts of which 0 were active
> after adding rounds of cuts (0.871 seconds)
> TwoMirCuts was tried 1480 times and created 2398 cuts of which 0 were
> active after adding rounds of cuts (94.707 seconds)
> ZeroHalf was tried 6359 times and created 8295 cuts of which 0 were
> active after adding rounds of cuts (17913.959 seconds)
> ImplicationCuts was tried 109 times and created 158 cuts of which 0
> were active after adding rounds of cuts (0.483 seconds)
>
> Result - Stopped on time limit
>
> Objective value: 382710.00000000
> Lower bound: 382309.993
> Gap: 0.00
> Enumerated nodes: 6188
> Total iterations: 6815530
> Time (CPU seconds): 14185.91
> Time (Wallclock seconds): 3933.92
>
> Total time (CPU seconds): 14186.18 (Wallclock seconds): 3934.22
>
>
>
>
>
>
>
> *Pieter Zieschang*
> pieter.zieschang1 (at) de.ibm.com
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> Modis IT Outsourcing GmbH . Ein Unternehmen der internationalen Adecco
> Gruppe
> Geschäftsführer: Andreas Buchelt . Martin Wimmer. Amtsgericht
> Düsseldorf HRB 78227
> Hauptsitz der Gesellschaft: Niederkasseler Lohweg 18, 40547 Düsseldorf
>
>
>
>
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> https://urldefense.proofpoint.com/v2/url?u=https-3A__list.coin-2Dor.org_mailman_listinfo_cbc&d=DwICAg&c=Ngd-ta5yRYsqeUsEDgxhcqsYYY1Xs5ogLxWPA_2Wlc4&r=pLOfVNEEHf-xhIqn1-uzYcZ6Q7UefG6Bg6rXCKTMiAA&m=j-3RLRIDdQTNED2_J5RbaqZ46PE1Ns6BxmcD9Jek86Q&s=IydX2sIJzOq0qgLsiBhjOZ8Q5vNqzs57_3DHdXy613w&e=
--
==================================================
Haroldo Gambini Santos
D.Sc, Computer Science
Universidade Federal de Ouro Preto
http://www.decom.ufop.br/haroldo/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20170725/8009fefe/attachment-0001.html>
More information about the Cbc
mailing list