[Symphony] results of parallel computation
Ted Ralphs
ted at lehigh.edu
Sun Apr 5 20:56:05 EDT 2009
Hi David,
It's difficult to tell what's going on from just the output. SYMPHONY
does not have a deterministic parallel execution mode, as I believe
CPLEX does, so there is likely to be more variation in results. For a
single instance solved just once, anything can happen---what's more
indicative is the trend across a number of instances from the same
class. The results here do seem a bit out of the ordinary, but the
difference could be because CPLEX has much better primal heuristics
that are aiding the production of solutions early in the search. If
you can send me the instance off-line, I will have a look and try to
see what's happening. You could also try CHiPPS
(http://projects.coin-or.org/CHiPPS), which is a new parallel search
framework we are working on that also has a parallel MILP solver
called BLIS included. If you send me the instance, I'll try with both.
Cheers,
Ted
On Wed, Mar 25, 2009 at 3:53 AM, David Pas <david.pas at student.upr.si> wrote:
> Hello,
>
> we have solved some IP problem on different architectures.
> Below are given the results for a single, two, and sixteen
> processor machine. We have expected that the parallelization
> will decrease the running time, however we noticed that it
> _remained_the_same_. Instead the number of analyzed nodes
> increased proportionally with the number of employed CPUs.
> The parameters were set such to make symphony stop on the
> first found feasible solution. Can someone please clarify
> how symphony partitions the work?
>
> Does someone have an idea how we could tell symphony to
> use the processors to find the solution faster rather than
> to explore more nodes. If we run CPLEX on the same problem
> on the same hardware than it indeed returns the result
> much faster when more processors are used. That's why
> we were surprised to see that with symphony there is
> no difference.
>
> Further, does anyone know what is the
> "Ramp Up Time (TM)" and the "Ramp Up Time (LP)"
> and what is the difference between the two?
> They both have always the same value.
>
>
>
> ============= Other Parameter Settings =============
>
> find_first_feasible 1
> gap_limit 1.0
>
> ****************************************************
> * Stopping After Finding First Feasible Solution *
> * Now displaying stats and best solution found... *
> ****************************************************
>
>
>
> SINGLE CPU:
> ===========
>
> ======================= CP Timing ===========================
> Cut Pool 0.000
> ====================== LP/CG Timing =========================
> LP Solution Time 4491.760
> Variable Fixing 0.000
> Pricing 0.000
> Strong Branching 1542.970
> Separation 2497.400
> =================== Parallel Overhead ======================
> Communication 1.570
> Ramp Up Time (TM) 0.006
> Ramp Up Time (LP) 0.006
> Ramp Down Time 0.000
> Idle Time (Node Pack) 0.006
> Idle Time (Nodes) 0.000
> Idle Time (Names) 0.000
> Idle Time (Diving) 0.009
> Idle Time (Cuts) 0.000
> Total User Time 8534.970
> Total Wallclock Time 8569.264
>
> ====================== Statistics =========================
> Number of created nodes : 225
> Number of analyzed nodes: 113
> Depth of tree: 112
> Size of the tree: 225
> Number of Chains: 1
> Number of Diving Halts: 0
> Number of cuts in cut pool: 0
> Lower Bound in Root: 3504021.331
>
> Current Upper Bound: 3507742.745
> Current Lower Bound: 3504024.121
> Gap Percentage: 0.11
>
> Solution Found: Node 224, Level 112
> Solution Cost: 3507742.745
>
>
> 2 CPUs:
> ======
>
> ======================= CP Timing ===========================
> Cut Pool 0.000
> ====================== LP/CG Timing =========================
> LP Solution Time 6552.920
> Variable Fixing 0.000
> Pricing 0.000
> Strong Branching 2703.080
> Separation 4420.730
> =================== Parallel Overhead ======================
> Communication 2.850
> Ramp Up Time (TM) 1958.151
> Ramp Up Time (LP) 1958.217
> Ramp Down Time 0.000
> Idle Time (Node Pack) 0.015
> Idle Time (Nodes) 0.000
> Idle Time (Names) 0.000
> Idle Time (Diving) 0.028
> Idle Time (Cuts) 0.000
> Total User Time 13680.820
> Total Wallclock Time 7857.234
>
> ====================== Statistics =========================
> Number of created nodes : 399
> Number of analyzed nodes: 200
> Depth of tree: 103
> Size of the tree: 399
> Number of Chains: 2
> Number of Diving Halts: 0
> Number of cuts in cut pool: 0
> Lower Bound in Root: 3504021.331
>
> Current Upper Bound: 3506535.850
> Current Lower Bound: 3504044.208
> Gap Percentage: 0.07
>
> Solution Found: Node 395, Level 97
> Solution Cost: 3506535.850
>
>
>
> 16 CPUs:
> =======
>
> ======================= CP Timing ===========================
> Cut Pool 0.000
> ====================== LP/CG Timing =========================
> LP Solution Time 30619.620
> Variable Fixing 0.180
> Pricing 0.000
> Strong Branching 18797.330
> Separation 32774.290
> =================== Parallel Overhead ======================
> Communication 21.880
> Ramp Up Time (TM) 32763.929
> Ramp Up Time (LP) 32764.187
> Ramp Down Time 0.000
> Idle Time (Node Pack) 0.618
> Idle Time (Nodes) 0.000
> Idle Time (Names) 0.000
> Idle Time (Diving) 814.878
> Idle Time (Cuts) 0.000
> Total User Time 82214.540
> Total Wallclock Time 7384.543
>
> ====================== Statistics =========================
> Number of created nodes : 2295
> Number of analyzed nodes: 1148
> Depth of tree: 80
> Size of the tree: 2295
> Number of Chains: 16
> Number of Diving Halts: 0
> Number of cuts in cut pool: 0
> Lower Bound in Root: 3504021.331
>
> Current Upper Bound: 3506568.896
> Current Lower Bound: 3504084.831
> Gap Percentage: 0.07
>
> Solution Found: Node 2262, Level 72
> Solution Cost: 3506568.896
>
>
> Thank you in advance,
> David
>
>
>
> ----------------------------------------------------------------
> This message was sent using IMP, the Internet Messaging Program.
>
>
> _______________________________________________
> Symphony mailing list
> Symphony at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/symphony
>
--
Dr. Ted Ralphs
Associate Professor, Lehigh University (permanent)
Visiting Professor, Monash University (current)
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted
Sent from Caulfield East, Victoria, Australia
More information about the Symphony
mailing list