[Coin-discuss] SYMPHONY speedup

[Michael Hennebry]

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