Re: [Help-glpk] enumerating multiple optimal solutions

[Brady Hunsaker]

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

Robert Anderson wrote:
> On 10/18/05, Gabor Retvari <address@hidden> wrote:
> 
>>On Tuesday 18 October 2005 18:20, Teri Nava-Vaughn wrote:
>>
>>>I have a need to find all optimal solutions for a LP problem I am solving.
>>>
>>>I found this post from 2002:
>>>
>>>http://lists.gnu.org/archive/html/help-glpk/2002-01/msg00002.html
>>>
>>>But I don't follow it very well.  Have the proposed API additions in
>>>this message been implemented?
>>
>>if you refer to these words of Andrew: "I'm going to include two API routines
>>for computing rows and columns of the tableau in the next subversion of
>>glpk", then these two routines might be:
>>
>>int lpx_eval_tab_row(LPX *lp, int k, int ind[], double val[]);
>>/* compute row of the simplex table */
>>
>>int lpx_eval_tab_col(LPX *lp, int k, int ind[], double val[]);
>>/* compute column of the simplex table */
>>
>>see glplpx.h and the reference manual.
>>
>> good luck: gabor
> 
> 
> I suspected that might be, however I am still lost as to how to
> implement what he described in that post (I am no LP expert).
> 
> "you need to look at non-basic variables whose dual activity is ~0"
> 
> Forgive my ignorance but I find nothing in the reference manual about
> querying "dual activity" or even any "activity" at all for non-MIP
> problems:
> 
> $ grep activity refman.latex
> \subsection{{\tt lpx\_get\_mip\_row} --- obtain row activity for MIP
> \subsection{{\tt lpx\_get\_mip\_col} --- obtain column activity for MIP
> 
> I have done some googling to try to figure it out, but the literature
> around this subject seems to use a wide variety of synonyms.  It would
> certainly be helpful if the discussion used the terminology used
> within glpk's documentation.  If there is nothing in the API, the
> reference manuals, nor the output files listed as "dual activity" it
> makes the discussion harder to follow for a "layperson."  I see
> "Activity" listed in the solution file, but no "Dual Activity".
> 
> "If you'd know the column of the simplex tableau, which corresponds to
> (xN)j, the issue would be exhausted, because you'd be able to perform
> the primal simplex iteration and determine the adjacent vertex"
> 
> Given that I've found such a variable (non-basic, ~0 dual activity),
> it is not clear to me how to find the "column of the simplex tableau
> corresponding to (xN)j" using the eval_tab_row or eval_tab_column
> routines.
> 
> Given that I'd found the relevant column of the simplex tableau, it is
> still unclear how to use the API to "perform the primal simplex
> iteration" - there doesn't seem to be any API method for performing a
> primal simplex iteration.  Or perhaps I just don't recognize it.
> 
> Thanks for your patience and any further guidance.
> 
> Bob
>