Re: [Help-glpk] Many basic vars = 0, many non-basic are on upper-bound

[Andrew Makhorin]

> My decision variables are all binary.  During the solve process (for
> the relaxation) many of the basic variables have a value of 0.0.  This
> implies degeneracy, which I feel somewhat comfortable with.  At the same
> time, many of my non-basic variables return GLP_NU (non-basic variable on
> its upper bound, i.e. primal value is 1) when I try glp_get_col_stat(). 
> I'm trying to get a better understanding of what this means.

> Nothing in my model is broken and the GLPK chugs along and provides
> the correct answer, so I guess I'm just asking for a little clarification
> on what "non-basic on its upper bound" means in terms of the simplex
> algorithm. 

You can find a version of the simplex method for variables with upper
bounds in George Dantzig's book (Chap. 18, Variables with Upper Bounds);
see http://lists.gnu.org/archive/html/help-glpk/2009-01/msg00010.html .
All modern simplex-based LP solvers provide this feature.

> My variables are often part of a convex combination, so the sum of
> some subset of them needs to be 1.  It seems odd that one of them from
> this subset would be basic with a value of zero and another is non-basic
> with a value of 1.  I'm trying to understand what algorithmic paths might
> be taken to get to such a solution.

> I know the question is a tad vague, but any insight is appreciated.