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

[Ted Ralphs]

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

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

If you just want to ensure that a single unique solution is produced every
time (and not necessarily that the solution process itself is identical),
some variant of what you suggest should work. If you are going to actually
implement this, though, you want to make it as easy on yourself as possible
and try not give up any efficiency.  The easiest way I can think of off the
top of my head is to have a secondary objective function for breaking ties
among alternative optima, which is essentially what you were suggesting.

Is this a pure integer problem with integer coefficients in the objective?
If so, you know that there is a difference of at least 1 between the value
of any optimal solution and any suboptimal solution. In that case, you could
add a small multiple of the secondary objective to the first objective in
such a way that the same set of all optimal solution is produced, but one of
them is favored due to the small perturbations in cost. Of course, it would
be hard to absolutely guarantee that this will work, sine you could have
ties in the secondary objective, too, but the probability of that is low.

Otherwise, you could sole the problem, then impose the objective function
value as a constraint like you suggest and re-solve one more time with the
secondary objective. This may cause some numerical difficulties in the
second sole, but you could try it. Beyond that, there are even more
sophisticated methods of optimizing with lexicographic objective functions
that are efficient, but would require mucking around in the code. These
methods are somewhat closely related to what is done in multi-objective
optimization. Hope this helps get you started.

Cheers,

Ted
-- 
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/9f390459/attachment.html>