[Coin-discuss] SYMPHONY speedup

Thu Apr 30 04:53:56 EDT 2009

I've now posted this tech report. You can get it from my personal Web site:

http://coral.ie.lehigh.edu/~ted/files/papers/CHiPPS-Rev.pdf

or from optimization online:

http://www.optimization-online.org/DB_HTML/2007/09/1786.html

Cheers,

Ted

On Wed, Apr 29, 2009 at 12:56 AM, Jack Bryan <dtustudy68 at hotmail.com> wrote:
> 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. Check it out.

-- 
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