Re: [Help-glpk] enumerating multiple optimal solutions

[Robert Anderson]

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