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 _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
