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

[Lou Hafer]

Joey,

        Two different views, which may help you.
        
        Simplex with bounded variables simply moves the bound constraints from
the constraint system into the algorithm.  You could rewrite your constraint
system with explicit x >= 0 and x <= 1 constraints, all variables free, and
you'll see non-zero duals (active constraints) for the constraints x<j> <= 1 for
exactly the variables that are nonbasic at upper bound.  There should be a
subset of the x<j> that are nonbasic at lower bound; these are the active
constraints for x<j> >= 0.

        Alternate view, from a polyhedral viewpoint.  A problem with binary
variables is a unit cube in n dimensions.  Let n = 3 so you can visualise.
Consider a constraint system which is exactly the unit cube:  upper and lower
bounds, no other constraints.  Simplex finds extreme point solutions, in this
case the extreme points of the unit cube.  The extreme point you reach depends
on your objective.  Now, add a single constraint x<1> + x<2> + x<3> <= 1.  If
you draw the constraint on the cube, it intersects at (0,0,1), (0,1,0), and
(1,0,0).  You have not introduced any additional extreme points.  Any solution
with x<1> + x<2> + x<3> = 1 will still have two variables at zero and one at
one.

        Adding additional constraints can introduce extreme points of the
feasible region which are distinct from the vertices of the unit cube.  Now you
can get fractional solutions.  (But if you're actually solving as a MIP,
additional constraints will be added --- cuts and bounds --- so that ultimately
you shave away the continuous feasible region (convex hull), exposing an integer
extreme point as an extreme point of the convex hull.

                                                                Lou