<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
On 9/15/2011 8:58 AM, Ted Ralphs wrote:
<blockquote
cite="mid:CA+GYycvRk-yJv7fQvy9QRcPt2_7cL2goEvGP4XXHdrrJYD+UFA@mail.gmail.com"
type="cite">Hi Pete,
<div><br>
</div>
<div>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)? </div>
</blockquote>
The objective function values are identical, so I am seeing
alternate optimal solutions. The alternate solutions are correct.<br>
<br>
<blockquote
cite="mid:CA+GYycvRk-yJv7fQvy9QRcPt2_7cL2goEvGP4XXHdrrJYD+UFA@mail.gmail.com"
type="cite">
<div>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. <br>
</div>
</blockquote>
<br>
I think this would find a unique solution, but the problem is that
it is too slow given the number of variables:<br>
<br>
1. Find the initial non-unique solution <br>
2. Change the objective function of the model to a constraint using
the objective function value found by step 1 as the rhs<br>
3. Iterate over each variable: set the objective function to be that
variable, find a solution, set that variable to the minimum value
found<br>
<br>
Any suggestions on other approaches to that may lead to a unique
solution ? <br>
<br>
<blockquote
cite="mid:CA+GYycvRk-yJv7fQvy9QRcPt2_7cL2goEvGP4XXHdrrJYD+UFA@mail.gmail.com"
type="cite">
<div><br>
</div>
<div>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.</div>
</blockquote>
I will send you some test cases.<br>
<blockquote
cite="mid:CA+GYycvRk-yJv7fQvy9QRcPt2_7cL2goEvGP4XXHdrrJYD+UFA@mail.gmail.com"
type="cite">
<div><br>
</div>
<div>Cheers,</div>
<div><br>
</div>
<div>Ted</div>
<div>
<br>
<div class="gmail_quote">On Thu, Sep 15, 2011 at 12:44 AM, Peter
Moceyunas <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:moce@stretchinc.com" target="_blank">moce@stretchinc.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi,<br>
<br>
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.<br>
<br>
I have models in which symphony produces different results
across 1 or more of the different symphony executables.<br>
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.<br>
<br>
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.<br>
<br>
The models have a large number of constraints (20K-30K) and
variables(10-30K) but typically solve fast (<few minutes)
with no branching.<br>
I believe all the coefficients in constraints and objective
function of the LP are either 1 or -1<br>
<br>
I can send examples if you are interested.<br>
<br>
Any thoughts or suggestions ?<br>
<br>
Pete<br>
<br>
_______________________________________________<br>
Symphony mailing list<br>
<a moz-do-not-send="true"
href="mailto:Symphony@list.coin-or.org" target="_blank">Symphony@list.coin-or.org</a><br>
<a moz-do-not-send="true"
href="http://list.coin-or.org/mailman/listinfo/symphony"
target="_blank">http://list.coin-or.org/mailman/listinfo/symphony</a><br>
</blockquote>
</div>
<br>
<br clear="all">
<div><br>
</div>
-- <br>
Dr. Ted Ralphs<br>
Associate Professor, Lehigh University<br>
<a moz-do-not-send="true" href="tel:%28610%29%20628-1280"
value="+16106281280" target="_blank">(610) 628-1280</a><br>
ted 'at' lehigh 'dot' edu<br>
<a moz-do-not-send="true"
href="http://coral.ie.lehigh.edu/%7Eted" target="_blank">coral.ie.lehigh.edu/~ted</a><br>
<br>
</div>
</blockquote>
<br>
</body>
</html>