[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] enumerating multiple optimal solutions
From: |
Brady Hunsaker |
Subject: |
Re: [Help-glpk] enumerating multiple optimal solutions |
Date: |
Fri, 18 Nov 2005 22:38:21 -0500 |
User-agent: |
Debian Thunderbird 1.0.7 (X11/20051017) |
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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- Re: [Help-glpk] enumerating multiple optimal solutions,
Brady Hunsaker <=