Re: [Help-glpk] enumerating multiple optimal solutions

[Brady Hunsaker]

Robert Anderson wrote:
> On 10/18/05, Brady Hunsaker <address@hidden> wrote:
> 
>>Unfortunately, my sense is that enumerating all optimal solutions is a
>>problem where the comparison of difficulty to usefulness to most people
>>has caused it to almost never be implemented.  I know of no
>>implementations in LP solvers.
>>
>>If you really need all solutions, then my recommendation is this:
>>1. use an LP solver to find the optimal objective value
>>2. add a constraint of the form
>>   obj value = optimal value
>>3. use a code for explicit enumeration of all extreme points of the
>>resulting polyhedron.  The only code I know of is lrs:
>>http://cgm.cs.mcgill.ca/~avis/C/lrs.html
>>
>>I haven't ever used it, so I don't whether that will work well for you.
>>
>>Brady
> 
> 
> Thanks for your comments and suggestions.  Just to show I've done a
> little homework on this, I did find that CPLEX, GAMS, and Lindo can
> find alternate optimal solutions.
> 
> I know of two methods in the literature.  One is formulated as a MILP problem:
> 
> Lee, S., C. Phalakornkule, M.D. Domach and I.E. Grossmann, "Recursive
> MILP Model for finding all the Alternate Optima in LP models for
> Metabolic Networks," Computers and Chemical Engineering 24, 711-716
> (2000).
> 
> This one is used in GAMS according to the authors.
> 
> The other uses a search procedure and appears close to what Andrew was
> suggesting:
> 
> http://etd.library.pitt.edu/ETD/available/etd-01302003-141212/
> 
> Both seem possible to implement around glpk, but I am just getting
> spun up on LP in general (my area is PDEs), so I am struggling a
> little to put this together.
> 
> Mostly on the net I see a lot of deflections ("all solutions are equal
> - who cares?"), and I understand that is true in principle, but in
> practice, one may be interested in the various solutions as they may
> have ancillary characteristics which differentiate them, but which are
> not plausible to include in the LP itself.  In addition, the structure
> of the family of optimal solutions can provide insight about the
> problem itself.
> 
> Thanks,
> Bob

Bob,

You make a valid point.  I'm starting to keep a list of possible
improvements to GLPK that grad students I work with may want to do.  I'm
adding this to my list.  That doesn't mean that anyone will work on it
soon, but it might intrigue someone.

Brady