[Coin-symphony] Best form for constraints
Mark Williams
mark at stretchinc.com
Thu Jan 17 19:53:15 EST 2008
On 1/17/2008 2:55 PM, Ashutosh Mahajan wrote:
> hi Mark,
>
> On Wed, 16 Jan 2008, Mark Williams wrote:
>
>> I have a program which is generating models using sym_explicit_load_problem,
>> and then trying to solve them.
>>
>> Some of the models take a long time to solve, and I was trying to figure out why.
>>
>> I picked a model that was taking around 1000s to solve, wrote it out using
>> sym_write_lp, and tried solving it using the symphony executable. It solved
>> in around 5 seconds.
>
> is it possible mail me or post on some web-server, the lp file and the code that
> you used with the sym_explicit_load_problem? i can take a look and see what is
> causing such a discrepancy.
Sorry, no, I cant provide the executable. But since MPS format preserves the range constraints (rather than splitting them into two), I can reproduce the problem by writing out an LPT model, and an MPS model (which I can give you).
However, I've been refining the models, and now Im finding that in most cases, using a single range constraint is better than using two separate constraints - the reverse of what I was seeing previously.
I have a model which takes 288s to solve the .LPT, and 17 seconds to solve the .MPS (the two files were generated from the same symphony model, by calling sym_write_lp, followed by sym_write_mps).
You can get model_1.MPS, model_1.LPT, and foo.par by public ftp from ftp.myosotissp.com.
% symphony -v 0 -F model_1.MPS -f foo.par
...
> Solving...
>
> done: 16 left: 13 ub: 8435.00 lb: 8416.06 gap: 0.22 time: 6
> done: 32 left: 17 ub: 8435.00 lb: 8425.97 gap: 0.11 time: 11
> done: 51 left: 17 ub: 8435.00 lb: 8429.23 gap: 0.07 time: 17
>
> ****************************************************
> * Optimal Solution Found *
> * Now displaying stats and best solution found... *
> ****************************************************
>
> ======================= CP Timing ===========================
> Cut Pool 0.000
> ====================== LP/CG Timing =========================
> LP Solution Time 6.000
> Variable Fixing -0.000
> Pricing 0.000
> Strong Branching 3.710
> Separation 7.530
> Total User Time 17.270
> Total Wallclock Time 18.439
>
> ====================== Statistics =========================
> Number of created nodes : 83
> Number of analyzed nodes: 58
> Depth of tree: 11
> Size of the tree: 83
> Number of Chains: 20
> Number of Diving Halts: 0
> Number of cuts in cut pool: 0
> Lower Bound in Root: 8397.457
>
> Solution Found: Node 79, Level 9
> Solution Cost: 8433.000
% symphony -v 0 -L model_1.LPT -f foo.par
...
> Solving...
>
> done: 16 left: 15 ub: 8441.00 lb: 8401.85 gap: 0.46 time: 5
> done: 33 left: 25 ub: 8441.00 lb: 8408.29 gap: 0.39 time: 11
> done: 52 left: 42 ub: 8441.00 lb: 8408.60 gap: 0.38 time: 16
> done: 73 left: 59 ub: 8441.00 lb: 8411.21 gap: 0.35 time: 23
> done: 95 left: 74 ub: 8441.00 lb: 8411.44 gap: 0.35 time: 30
> done: 119 left: 91 ub: 8441.00 lb: 8412.42 gap: 0.34 time: 36
> done: 135 left: 101 ub: 8441.00 lb: 8412.96 gap: 0.33 time: 42
> done: 157 left: 119 ub: 8441.00 lb: 8412.96 gap: 0.33 time: 48
> done: 177 left: 131 ub: 8441.00 lb: 8412.96 gap: 0.33 time: 54
> done: 193 left: 143 ub: 8441.00 lb: 8414.61 gap: 0.31 time: 59
> done: 212 left: 153 ub: 8440.00 lb: 8414.61 gap: 0.30 time: 64
> done: 235 left: 166 ub: 8440.00 lb: 8414.61 gap: 0.30 time: 72
> done: 255 left: 180 ub: 8440.00 lb: 8414.61 gap: 0.30 time: 78
> done: 269 left: 187 ub: 8440.00 lb: 8414.61 gap: 0.30 time: 84
> done: 287 left: 195 ub: 8440.00 lb: 8415.45 gap: 0.29 time: 89
> done: 309 left: 209 ub: 8440.00 lb: 8415.45 gap: 0.29 time: 95
> done: 331 left: 222 ub: 8436.00 lb: 8415.45 gap: 0.24 time: 100
> done: 349 left: 227 ub: 8436.00 lb: 8415.45 gap: 0.24 time: 105
> done: 370 left: 227 ub: 8435.00 lb: 8418.33 gap: 0.20 time: 110
> done: 397 left: 242 ub: 8435.00 lb: 8418.33 gap: 0.20 time: 116
> done: 426 left: 254 ub: 8435.00 lb: 8418.33 gap: 0.20 time: 121
> done: 444 left: 261 ub: 8435.00 lb: 8418.33 gap: 0.20 time: 127
> done: 467 left: 269 ub: 8435.00 lb: 8418.33 gap: 0.20 time: 133
> done: 485 left: 273 ub: 8435.00 lb: 8418.33 gap: 0.20 time: 138
> done: 506 left: 280 ub: 8435.00 lb: 8418.33 gap: 0.20 time: 143
> done: 525 left: 286 ub: 8435.00 lb: 8418.33 gap: 0.20 time: 149
> done: 543 left: 288 ub: 8435.00 lb: 8418.33 gap: 0.20 time: 154
> done: 562 left: 282 ub: 8435.00 lb: 8418.33 gap: 0.20 time: 159
> done: 582 left: 288 ub: 8435.00 lb: 8418.33 gap: 0.20 time: 164
> done: 609 left: 292 ub: 8434.00 lb: 8418.33 gap: 0.19 time: 170
> done: 631 left: 294 ub: 8434.00 lb: 8418.33 gap: 0.19 time: 175
> done: 654 left: 297 ub: 8434.00 lb: 8418.33 gap: 0.19 time: 180
> done: 682 left: 293 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 185
> done: 706 left: 300 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 191
> done: 727 left: 295 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 196
> done: 753 left: 303 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 202
> done: 779 left: 315 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 208
> done: 808 left: 329 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 214
> done: 836 left: 328 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 219
> done: 863 left: 332 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 225
> done: 892 left: 333 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 230
> done: 919 left: 329 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 236
> done: 942 left: 331 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 241
> done: 967 left: 329 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 247
> done: 995 left: 331 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 252
> done: 1022 left: 333 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 257
> done: 1049 left: 332 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 262
> done: 1075 left: 327 ub: 8434.00 lb: 8419.85 gap: 0.17 time: 268
> done: 1102 left: 328 ub: 8434.00 lb: 8420.30 gap: 0.16 time: 273
> done: 1129 left: 316 ub: 8434.00 lb: 8420.30 gap: 0.16 time: 278
> done: 1161 left: 314 ub: 8433.00 lb: 8420.30 gap: 0.15 time: 283
> done: 1192 left: 305 ub: 8433.00 lb: 8420.30 gap: 0.15 time: 288
> done: 1227 left: 285 ub: 8433.00 lb: 8420.30 gap: 0.15 time: 293
> done: 1267 left: 267 ub: 8433.00 lb: 8420.30 gap: 0.15 time: 298
> done: 1308 left: 248 ub: 8433.00 lb: 8420.30 gap: 0.15 time: 304
> done: 1352 left: 215 ub: 8433.00 lb: 8420.30 gap: 0.15 time: 309
>
> ****************************************************
> * Optimal Solution Found *
> * Now displaying stats and best solution found... *
> ****************************************************
>
> ======================= CP Timing ===========================
> Cut Pool 0.000
> ====================== LP/CG Timing =========================
> LP Solution Time 90.650
> Variable Fixing 0.020
> Pricing 0.000
> Strong Branching 67.110
> Separation 130.680
> Total User Time 288.680
> Total Wallclock Time 313.763
>
> ====================== Statistics =========================
> Number of created nodes : 1853
> Number of analyzed nodes: 1403
> Depth of tree: 29
> Size of the tree: 1853
> Number of Chains: 535
> Number of Diving Halts: 0
> Number of cuts in cut pool: 0
> Lower Bound in Root: 8401.847
>
> Solution Found: Node 1693, Level 24
> Solution Cost: 8433.000
Mark Williams
More information about the Symphony
mailing list