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