[Coin-discuss] SYMPHONY speedup

[Ted Ralphs]

Yes, of course, I did not mean to imply that symmetry is a good thing
because it leads to efficient parallelization. If you know that
symmetry is present and you have an effective method of breaking it,
then by all means use it, whether or not you are using a parallel
solver. On the other hand, though there has been a lot of excellent
recent work on how to deal with symmetric integer programs, this
methodology has not been fully absorbed into solvers and we are still
some way from being able to detect and break symmetry in an
unstructured, generic MILP. It is relatively easy to generate
instances that are symmetric or "almost symmetric" and that will be
difficult even for the best of solvers when used off the shelf. In
such cases, parallelization may help.

Cheers,

Ted

On Wed, Apr 29, 2009 at 1:51 AM, Michael Hennebry
<hennebry at web.cs.ndsu.nodak.edu> wrote:
> On Tue, 28 Apr 2009, Ted Ralphs wrote:
>
>> 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,
>
> Symmetry is more likely to be a pain than a boon.
> Ten sets of equivalent variables could have a large
> multiple of 3628800 equivalent almost-soltuions.
> Even four loosely-coupled sets with a thousand almost-
> solutions each could have 10**12 almost solutions.
>
> As a rule, symmetry is something that needs to be broken,
> preferebly with application-specific knowledge.
>
> --
> Michael   hennebry at web.cs.ndsu.NoDak.edu
> "Pessimist: The glass is half empty.
> Optimist:   The glass is half full.
> Engineer:   The glass is twice as big as it needs to be."
>



-- 
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 Melbourne, Victoria, Australia