Re: [Help-glpk] Selection rules on degenerate solutions

[Brady Hunsaker]

On Tue, 2004-10-05 at 08:47, Panajotis Papazoglou wrote:
> Hello, 
> 
> I am a newbie on GLPK and Linear Programming having the following
> questions: 
> 
> Given is a LP or MILP problem with a degenerate optimum, that is at
> least two solutions exist with the same optimal value and I call them
> BLUE and RED. Lets assume that I know the two solutions.
> 
> According to which rules does GLPK select one of them? Is there a way
> I can deduce from the equation, constraints and the starting point of
> the search why GLPK found BLUE and not RED? 
> 
When using the simplex algorithm, the two (or more) optimal solutions
are different extreme points (corners) of the feasible polyhedron. 
Which one is arrived at depends on the path of extreme points that was
followed during simplex pivots.  This depends on the initial basis and
pivoting rule.  Since you say you are new to LP, this might not make
much sense.  In any case, I would not recommend trying to adjust either
of these parameters in an effort to favor a particular optimal
solution.  I'm not sure it's possible.

> Alternatively: How can I tell GLPK to choose BLUE in any case a
> degenerate solution exists and not RED? How could I insert some
> ordering or naming rules which do not have an effect on the optimal
> solution but which help to make the solution unambiguous?
> 
This is more reasonable, but depends on the instances you are working
with.  Another poster gave one approach that works if you know that two
variables are symmetric (that is, the columns are identical).  

If you can predict the types of solutions that will be optimal, then you
may be able to add small epsilon values to the objective coefficients to
favor one over the other.  A challenge is determining how small the
epsilon should be so that the result is optimal for the original values
while still favoring one solution over another. This approach has the
advantage that it only requires changing the model.
 
Another option is to examine the output to check whether there are
alternative optimal solutions and explicitly pivot to them.  I don't
think this is done often, and I don't recommend it in your case.

Brady