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

[Peter Moceyunas]

On 9/15/2011 8:58 AM, Ted Ralphs wrote:
> 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)?
The objective function values are identical, so I am seeing alternate 
optimal solutions. The alternate solutions are correct.

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

I think this would find a unique solution, but the problem is that it is 
too slow given the number of variables:

1. Find the initial non-unique solution
2. Change the objective function of the model to a constraint using the 
objective function value found by step 1 as the rhs
3. Iterate over each variable: set the objective function to be that 
variable, find a solution, set that variable to the minimum value found

Any suggestions on other approaches to  that may lead to a unique 
solution ?

>
> 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.
I will send you some test cases.
>
> Cheers,
>
> Ted
>
> On Thu, Sep 15, 2011 at 12:44 AM, Peter Moceyunas <moce at stretchinc.com 
> <mailto: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 <mailto:Symphony at list.coin-or.org>
>     http://list.coin-or.org/mailman/listinfo/symphony
>
>
>
>
> -- 
> Dr. Ted Ralphs
> Associate Professor, Lehigh University
> (610) 628-1280 <tel:%28610%29%20628-1280>
> ted 'at' lehigh 'dot' edu
> coral.ie.lehigh.edu/~ted <http://coral.ie.lehigh.edu/%7Eted>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/symphony/attachments/20110915/99509956/attachment.html>