Re: [Help-glpk] How to find more than one optimal solution?

[Andrew Makhorin]

>I am new to glpk and LP, and would like to know how to 
>find more than one optimal solution with GLPK in
>a simple LP problem?

glpk has no special features to enumerate multiple optimal solutions.
However if you really need to do that, I could suggest the following
way (it is not elegant at all, but should work :+).

After obtaining a basic optimal solution of your problem you need to
look at non-basic variables whose dual activitiy (i.e. Lagrange
multiplier) is close to zero, for instance, in the range [-1e-6,+1e-6].
If there are no such variables, the optimal solution is unique.
Otherwise the problem has multiple optimal solutions (due to dual
degeneracy). Let (xN)j be a non-basic variable, whose dual activity
dj is close to zero. If (xN)j is on its lower (upper) bound, you can
increase (decrease) it without changing the objective function.
Changing (xN)j involves changing basic variables, and the issue is how
to detect the basic variable, which reaches its bound before other
basic variables. 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, which would be an alternative optimal basic solution.
But this is impossible in the current version (btw, I'm going to
include two API routines for computing rows and columns of the tableau
in the next subversion of glpk). However, instead that you can just
*decrease* (if (xN)j is on its lower bound) or *increase* (if (xN)j is
on its upper bound) the objective coefficient (cN)j at (xN)j by some
quantity, say, delta (assuming that the objective should be minimized.)
(xN)j is non-basic and dj = (cN)j + Nj inv(B') cB, therefore changing
(cN)j by delta involves changing dj by the same quantity, and dual
values of other non-basic variables are not changed. Geometrically you
just incline the anti-gradient to the edge of the polyhedron, which
corresponds to (xN)j. Since now the angle between the anti-gradient and
the edge becomes less than pi/2, the primal simplex needs to go along
this edge (in order to restore dual feasibility) to an adjacent vertex,
which is alternative optimal solution. Although the new objective with
perturbed coefficient at (xN)j will decrease, the original objective
will keep the same value as in the initial point. Finally (after the
adjacent solution will be obtained) the perturbed coefficient should be
replaced by its original value (note that in the adjacent vertex (xN)j
will become basic with zero dual value). In principle, repeating this
process allows you to enumerate all optimal basic solutions.