[Cbc] CBC vs. CPLEX Example
John Forrest
john.forrest at fastercoin.com
Sun Jan 16 05:17:54 EST 2011
Christoph,
How are you calling Cbc? Try using standalone solver and see what that
does. If that seems faster, try adapting Cbc/examples/driver4.cpp.
0.22 seconds doesn't seem too slow - how fast do you want it to be?
John Forrest
--------------------------------
command line - bin/cbc /tmp/a3-20842-wcet_analysis_0.lp (default
strategy 1)
### WARNING: CoinLpIO::readLp(): Maximization problem reformulated as
minimization
Continuous objective value is -45533.2 - 0.01 seconds
Cgl0003I 0 fixed, 0 tightened bounds, 7 strengthened rows, 0
substitutions
Cgl0004I processed model has 57 rows, 113 columns (113 integer) and 330
elements
Objective coefficients multiple of 1
Cutoff increment increased from 1e-05 to 0.999
Cbc0038I Pass 1: suminf. 0.75862 (2) obj. -45532.1 iterations 1
Cbc0038I Solution found of -43981
Cbc0038I Rounding solution of -45047 is better than previous of -43981
Cbc0038I Before mini branch and bound, 109 integers at bound fixed and 0
continuous
Cbc0038I Full problem 57 rows 113 columns, reduced to 0 rows 0 columns
Cbc0038I Mini branch and bound did not improve solution (-0.00 seconds)
Cbc0038I Round again with cutoff of -45097
Cbc0038I Pass 2: suminf. 0.75862 (2) obj. -45532.1 iterations 0
Cbc0038I Pass 3: suminf. 0.89316 (2) obj. -45097 iterations 8
Cbc0038I Pass 4: suminf. 0.00000 (0) obj. -45411 iterations 22
Cbc0038I Solution found of -45411
Cbc0038I Before mini branch and bound, 81 integers at bound fixed and 0
continuous
Cbc0038I Full problem 57 rows 113 columns, reduced to 1 rows 9 columns
Cbc0038I Mini branch and bound improved solution from -45411 to -45515
(0.01 seconds)
Cbc0038I Round again with cutoff of -45520
Cbc0038I Reduced cost fixing fixed 24 variables on major pass 3
Cbc0038I Pass 5: suminf. 0.75862 (2) obj. -45532.1 iterations 0
Cbc0038I Pass 6: suminf. 0.76831 (2) obj. -45520 iterations 8
Cbc0038I Pass 7: suminf. 1.84821 (4) obj. -45520 iterations 11
Cbc0038I Pass 8: suminf. 0.34483 (2) obj. -45527.1 iterations 5
Cbc0038I Pass 9: suminf. 0.35054 (2) obj. -45520 iterations 11
Cbc0038I Pass 10: suminf. 1.00000 (3) obj. -45520 iterations 19
Cbc0038I Pass 11: suminf. 1.00000 (3) obj. -45520 iterations 0
Cbc0038I Pass 12: suminf. 0.81376 (2) obj. -45520 iterations 10
Cbc0038I Pass 13: suminf. 0.81376 (2) obj. -45520 iterations 5
Cbc0038I Pass 14: suminf. 0.89655 (2) obj. -45520.2 iterations 13
Cbc0038I Pass 15: suminf. 0.89636 (2) obj. -45520 iterations 15
Cbc0038I Pass 16: suminf. 1.30769 (4) obj. -45520 iterations 21
Cbc0038I Pass 17: suminf. 1.04545 (4) obj. -45520 iterations 4
Cbc0038I Pass 18: suminf. 0.20690 (2) obj. -45525.5 iterations 6
Cbc0038I Pass 19: suminf. 0.20690 (2) obj. -45525.5 iterations 0
Cbc0038I Pass 20: suminf. 0.21128 (2) obj. -45520 iterations 15
Cbc0038I Pass 21: suminf. 0.20690 (2) obj. -45525.5 iterations 11
Cbc0038I Pass 22: suminf. 1.08333 (4) obj. -45520 iterations 7
Cbc0038I Pass 23: suminf. 1.08333 (4) obj. -45520 iterations 4
Cbc0038I Pass 24: suminf. 0.84540 (2) obj. -45520 iterations 16
Cbc0038I Pass 25: suminf. 0.84540 (2) obj. -45520 iterations 1
Cbc0038I Pass 26: suminf. 1.33750 (4) obj. -45520 iterations 15
Cbc0038I Pass 27: suminf. 1.14583 (4) obj. -45520 iterations 4
Cbc0038I Pass 28: suminf. 0.57960 (2) obj. -45520 iterations 16
Cbc0038I Pass 29: suminf. 0.55172 (2) obj. -45529.6 iterations 13
Cbc0038I Pass 30: suminf. 0.55942 (2) obj. -45520 iterations 16
Cbc0038I Pass 31: suminf. 0.91667 (4) obj. -45520 iterations 21
Cbc0038I Pass 32: suminf. 0.89636 (2) obj. -45520 iterations 14
Cbc0038I Pass 33: suminf. 0.89655 (2) obj. -45520.2 iterations 13
Cbc0038I Pass 34: suminf. 0.89636 (2) obj. -45520 iterations 16
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 75 integers at bound fixed and 0
continuous
Cbc0038I Full problem 57 rows 113 columns, reduced to 13 rows 24 columns
Cbc0038I Mini branch and bound did not improve solution (0.06 seconds)
Cbc0038I After 0.06 seconds - Feasibility pump exiting with objective of
-45515 - took 0.06 seconds
Cbc0012I Integer solution of -45515 found by feasibility pump after 0
iterations and 0 nodes (0.06 seconds)
Cbc0038I Full problem 57 rows 113 columns, reduced to 1 rows 4 columns
Cbc0038I Full problem 57 rows 113 columns, reduced to 0 rows 0 columns
Cbc0031I 4 added rows had average density of 87
Cbc0013I At root node, 4 cuts changed objective from -45533.154 to
-45523.236 in 100 passes
Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 0
column cuts (0 active) in 0.016 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 124 row cuts average 88.1 elements,
0 column cuts (4 active) in 0.008 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0
column cuts (0 active) in 0.008 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.008 seconds - new frequency
is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements,
0 column cuts (0 active) in -0.000 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 37 row cuts average 84.6
elements, 0 column cuts (0 active) in 0.004 seconds - new frequency is
-100
Cbc0010I After 0 nodes, 1 on tree, -45515 best solution, best possible
-45523.236 (0.15 seconds)
Cbc0016I Integer solution of -45523 found by strong branching after 311
iterations and 5 nodes (0.16 seconds)
Cbc0001I Search completed - best objective -45523, took 311 iterations
and 5 nodes (0.16 seconds)
Cbc0032I Strong branching done 78 times (178 iterations), fathomed 1
nodes and fixed 0 variables
Cbc0035I Maximum depth 4, 26 variables fixed on reduced cost
Cuts at root node changed objective from -45533.2 to -45523.2
Probing was tried 105 times and created 0 cuts of which 0 were active
after adding rounds of cuts (0.016 seconds)
Gomory was tried 100 times and created 124 cuts of which 4 were active
after adding rounds of cuts (0.008 seconds)
Knapsack was tried 100 times and created 0 cuts of which 0 were active
after adding rounds of cuts (0.008 seconds)
Clique was tried 100 times and created 0 cuts of which 0 were active
after adding rounds of cuts (-0.000 seconds)
MixedIntegerRounding2 was tried 100 times and created 0 cuts of which 0
were active after adding rounds of cuts (0.008 seconds)
FlowCover was tried 100 times and created 0 cuts of which 0 were active
after adding rounds of cuts (-0.000 seconds)
TwoMirCuts was tried 100 times and created 37 cuts of which 0 were
active after adding rounds of cuts (0.004 seconds)
Result - Optimal solution found
Objective value: -45523.00000000
Enumerated nodes: 5
Total iterations: 311
Time (seconds): 0.20
Total time: 0.22
On Mon, 2011-01-10 at 07:45 +0100, Christoph Cullmann wrote:
> Hi,
>
> have here a "small ILP" which takes ages solving via cbc, but is finished in
> seconds with CPLEX. Is the ILP formulation of the WCET for some small program.
> Perhaps it is a interesting test for the solver or there is some obvious
> suboptimality. If you have any advice how to speed up solving time, I would be
> happy ;)
>
> Greetings
> Christoph
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/cbc
More information about the Cbc
mailing list