Robert Anderson wrote: > On 10/18/05, Brady Hunsaker <[EMAIL PROTECTED]> 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 _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
