<br><div class="gmail_quote">On Thu, Sep 15, 2011 at 12:20 PM, Peter Moceyunas <span dir="ltr"><<a href="mailto:moce@stretchinc.com">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;">
<div bgcolor="#FFFFFF" text="#000000"><div class="im">I think this would find a unique solution, but the problem is that
it is too slow given the number of variables:</div>
<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 ? </div></blockquote><div><br></div><div>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. </div>
<div><br></div><div>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. </div>
<div><br></div><div>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.</div>
<div><br></div><div>Cheers,</div><div><br></div><div>Ted</div><div>-- </div></div>Dr. Ted Ralphs<br>Associate Professor, Lehigh University<br>(610) 628-1280<br>ted 'at' lehigh 'dot' edu<br><a href="http://coral.ie.lehigh.edu/~ted" target="_blank">coral.ie.lehigh.edu/~ted</a><br>
<br>