[Coin-discuss] SYMPHONY speedup

Tue Apr 28 10:56:44 EDT 2009

Dear Dr. Ralphs : 

Thanks for your advices and guidance.

May I have the advance copy of your report ?

I really appreciate your remarks. 

April 28  2009

> Date: Tue, 28 Apr 2009 17:05:37 +1000
> From: ted at lehigh.edu
> To: coin-discuss at list.coin-or.org
> Subject: Re: [Coin-discuss] SYMPHONY speedup
> 
> Since these questions come up frequently, I'd like to add a little
> detail to what's already been said. First, I'm not sure it's even
> possible to make the general statement that the "algorithmic quality"
> of a solver is more important than parallelization (if one can even
> define a relevant notion of "algorithmic quality"). With regard to the
> potential gains from parallelization, there are some limited things
> you can say if you have some knowledge of the properties of the
> problems you would like to solve. For classes of problems that tend to
> generate large, well-balanced trees (perhaps due to symmetry, for
> instance) and for which the processing time of an individual node is
> relatively short, it may be possible to reliably achieve near-linear
> speed-up (depending on the number of processors). For other classes,
> such as difficult set-partitioning models, it can be virtually
> impossible to achieve good speed-up because processing the first few
> levels of the tree (a largely sequential operation) is simply too
> time-consuming. Chances are good that an individual user's experience
> will be somewhere in between these two extremes.
> 
> Another factor that can be very important is the architecture on which
> execution takes place. SYMPHONY can be built for both
> distributed-memory and shared-memory execution. The performance is
> likely to be very different in these two cases. In shared-memory mode
> on an SMP, SYMPHONY's parallel performance will likely be better than
> on a distributed-memory architecture with the same number of
> processors. Execution on a multi-core architecture will be less
> efficient than on a true SMP due to additional resource limitations.
> Of course, the number of processors is a big factor as well.
> SYMPHONY's master-slave implementation probably will  not scale well
> beyond a few dozen processors, whereas BLIS, which is the parallel
> MILP solver that is available as part of the CHiPPS project
> (https://projects.coin-or.org/CHiPPS), is targeted more towards
> massive parallel architectures.
> 
> On top of that is the question of "algorithmic quality" raised by
> Tobias. This phrase is perhaps a little misleading, since quality has
> to be judged with respect to a particular target test bed. If the
> target test bed is unstructured, standard MILP instances solved one at
> a time on a single processor, then it is true that SYMPHONY does not
> have as many of the bells and whistles as some of the other solvers
> mentioned by Tobias. SYMPHONY's strength is in solving difficult
> combinatorial problems for which algorithmic customization is
> important. It also has some specific features that other solvers lack,
> such as basic warm-starting and sensitivity analysis capabilities for
> situations in which a sequence of related MILPs must be solved and the
> ability to handle multiple objectives.
> 
> Finally, there is parameter tuning. Most solvers endeavor to use
> default parameter settings that work well for as wide a range of
> problem types as possible. It's very likely, however, that you can see
> performance gains simply by tuning the parameter settings of a
> particular solver to work well for the instances you are interested
> in. In this way, even "off-the-shelf" testing is not necessarily
> representative of a solver's true capabilities.
> 
> Hopefully, this all gives you some idea that the situation is not very
> simple. Each solver has its strengths and one must test in
> representative operational situations (after appropriate parameter
> tuning) to truly determine the appropriateness of a given solver.
> 
> If you are interested in reading further about parallel solution of
> generic MILPs, we have just finished a tech report detailing our most
> recent experiences with the BLIS parallel MILP solver mentioned above.
> In this report, we try to paint as accurate a picture as possible of
> what one can expect when trying to use a parallel MILP solver off the
> shelf. The picture is anything but clear. The report will be available
> soon, but I can send you an advance copy if you like.
> 
> I hope this helps you understand the difficulty in giving a clear
> answer to your questions.
> 
> Cheers,
> 
> Ted
> 
> On Wed, Apr 22, 2009 at 6:16 PM, Tobias Achterberg <achterberg at zib.de> wrote:
> > Hi Jack,
> >
> > for MILP, your question cannot be answered (LP is a different story). Parallel speedup and
> > performance difference accross different solvers depend on the model.
> >
> > For example, there are models that can be solved by solver A in less than a second but
> > that take forever by another solver B, just because solver B is lacking the important
> > feature (like a cutting plane or a presolving reduction) to solve this particular model.
> > And there may be other models for which the situation is reversed. Finally, there are
> > models that can be solved in roughly the same time by all branch-and-cut MILP solvers.
> >
> > Overall, my experience is that the algorithmic quality of a solver is usually much more
> > important than parallelization. This means, that often solvers like CBC, SCIP, Gurobi,
> > XPress, or CPLEX will be faster than Symphony, even if you use 1000 CPUs for Symphony.
> > But, as I said, some models do not require the sophisticated machinery that these solvers
> > provide and parallelize well. In this setting, Symphony can be really great if you have
> > access to a massively parallel computing environment.
> >
> > So, the short answer is: you just need to test it for your models. You cannot say in advance.
> >
> >
> > Cheers,
> >
> > Tobias
> >
> > Jack Bryan wrote:
> >> Hi ,
> >>
> >> I am a new user of SYMPHONY .
> >>
> >> I need to use it to solve very large mixed integer linear programming
> >> models.
> >>
> >> So, I need to use PVM for SYMPHONY .
> >>
> >> But, I do not know how much speed up I can get from the parallel SYMPHONY ?
> >>
> >> For example, if it takes 100 seconds to solve a MILP model in CPLEX, how
> >> long to solve it in SYMPHONY ?
> >>
> >>
> >> thanks
> >>
> >> Jack
> >>
> >> April 21  2009
> >>
> >> ------------------------------------------------------------------------
> >> Windows Live™ Hotmail®:…more than just e-mail. Check it out.
> >> <http://windowslive.com/online/hotmail?ocid=TXT_TAGLM_WL_HM_more_042009>
> >>
> >>
> >> ------------------------------------------------------------------------
> >>
> >> _______________________________________________
> >> Coin-discuss mailing list
> >> Coin-discuss at list.coin-or.org
> >> http://list.coin-or.org/mailman/listinfo/coin-discuss
> >
> > _______________________________________________
> > Coin-discuss mailing list
> > Coin-discuss at list.coin-or.org
> > http://list.coin-or.org/mailman/listinfo/coin-discuss
> >
> 
> 
> 
> -- 
> 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
> 
> 
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss

_________________________________________________________________
Windows Live™ SkyDrive™: Get 25 GB of free online storage.  
http://windowslive.com/online/skydrive?ocid=TXT_TAGLM_WL_skydrive_042009
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20090428/be4f133c/attachment.html>