[Cbc] CBC Performance on Rostering Problem

Wed Jul 26 04:20:30 EDT 2017

Hi Haroldo,

Thanks for you help.

"Won't solve at all" means no feasible solution found.
Bad Performance means optimality will never be proven. Even after 10 
hours.

I uploaded the mps test file at mega, so you can have a look.

https://mega.nz/#!pvwDCC4A!GQBkhIZxkTdYaasgv_zGJwtIa1xQnWA98zisqsb2G-Q

Test with the suggested multiple=2 parameter:

Solution found by heuristics improved somewhat, but doesn't prove 
optimality too.

Cbc0012I Integer solution of 382870 found by heuristic after 962994 
iterations and 600 nodes (1181.97 seconds)
...
Cbc0010I After 1100 nodes, 305 on tree, 382785 best solution, best 
possible 382334.99 (1600.36 seconds)

Zerohalfcuts were on forceon before, so that should be ok i think?

Thanks

Mit freundlichen Grüßen / Kind regards

Pieter Zieschang

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

From:   Haroldo Gambini Santos <haroldo.santos at gmail.com>
To:     Pieter Zieschang1 <Pieter.Zieschang1 at de.ibm.com>, 
cbc at list.coin-or.org
Date:   25.07.2017 19:45
Subject:        Re: [Cbc] CBC Performance on Rostering Problem

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 ifmove
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/20170726/833e191e/attachment-0001.html>