Re: [Help-glpk] enumerating multiple optimal solutions

[Robert Anderson]

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