[Symphony] Same version of symphony built with different -O options produces different solutions

[Ted Ralphs]

Hi Pete,

Do the differences you are observing have to do with changes in the optimal
solution value or just what (alternative) optimal solution is actually
produced and/or how long it takes to produce it (what the search tree looks
like)? Differences in the search with different
compilers/platforms/optimization levels are going to occur with any solver.
Ideally, those differences should not lead to differences in the resulting
solution value, but differences in which of the optima are produced is
inevitable. You are correct that it is at least partially due to differences
in floating point values and also differences in the ways ties get
arbitrarily broken with different optimization levels and with different
compilers. This should not affect correctness of the algorithm, just the
order in which operations are done. Things get even messier when parallelism
is involved.

There are isolated cases in which numerical difficulties can lead to
incorrect solutions being produced. There have been experiments showing that
even the commercial solvers can end up producing different solution values
for the same problem. In general, this should not happen for "well-behaved"
instances. I would be surprised to see it with a 0, +1, -1 matrix. Feel free
to pass on the instances to me. If nothing else, they may provide good test
cases for us.

Cheers,

Ted

On Thu, Sep 15, 2011 at 12:44 AM, Peter Moceyunas <moce at stretchinc.com>wrote:

> Hi,
>
> I have built symphony 5.4.0 on the same machine 5 different ways each using
> the same gcc compiler (3.4.4) but with different optimization flags: -g,
> -O0, -O1, -O2 and -O3.
>
> I have models in which symphony produces different results across 1 or more
> of the different symphony executables.
> I am guessing that this is occurring because of differences in floating
> point values due to the different register spills generated by the different
> optimization levels but not sure how to confirm this.
>
> Further different compilers I have tried will generate different results -
> this is an issue as we would like our tool to produce the same result across
> linux and windows.
>
> The models have a large number of constraints (20K-30K) and
> variables(10-30K) but typically solve fast (<few minutes) with no branching.
> I believe all the coefficients in constraints and objective function of the
> LP are either 1 or -1
>
> I can send examples if you are interested.
>
> Any thoughts or suggestions ?
>
> Pete
>
> ______________________________**_________________
> Symphony mailing list
> Symphony at list.coin-or.org
> http://list.coin-or.org/**mailman/listinfo/symphony<http://list.coin-or.org/mailman/listinfo/symphony>
>



-- 
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/symphony/attachments/20110915/1f12848b/attachment.html>