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