[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Andrew Makhorin
Subject: Re: [Help-glpk] Many basic vars = 0, many non-basic are on upper-bound
Date: Fri, 12 Jun 2009 16:46:25 +0300

> 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 .
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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]