Re: [Help-glpk] Initial Basis

[Brady Hunsaker]

Ulrich Spörlein wrote:
> Hello all,
> 
> I have some trouble understanding how I can pass an initial basis to
> GLPK. First of all, with my LP-class, roughly 80-90% of the time is
> spent with constructing an initial feasible solution. Now of course I'd
> like to improve this time.
> 
> Since I am load balancing a number of flows in a graph, all my variables
> (except one!) are bound by [0, 1]. And all variables of one load
> balancing group have to add up to 100%.
> 
> Now, I can *always* give an initial feasible solution by setting all the
> variables of one LB-group to 1/x. That is, use 50:50 or 33:33:33 as load
> balancing scheme.
> 
> Thus I immediately have a working, but far from optimal, solution. Now I
> could let the LP solver improve upon that solution, and if I'm
> restricted by a run time of, say, 10 minutes, I get an acceptable
> solution.
> 
> You see, it is better for me, to have a somewhat working solution after a
> short period, than to wait 90% of the time (hours!) to get the first
> workable solution (which is very, very good already, but the run time
> ...)
> 
> Now I read the GLPK manual and I know that I can only set the status of
> a variable, not the actual value. What I don't know is, what a basic and
> a non-basic variable is. What's the difference of an active and
> non-active constraint? As you already guessed, Linear Programming is not
> my field of expertise. Any pointers are greatly appreciated!
> 
> Ulrich Spoerlein
> 
> 

For more information on the simplex algorithm, one starting point is
http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html

Briefly (and simplifying a bit), the simplex algorithm only considers
certain solutions, called basic feasible solutions.  Geometrically,
these are the corner points of the polyhedron formed by the feasible
solutions.  You can't just feed in any feasible solution; you must give
it a basic solution.

An active constraint is one that is tight---it is satisfied as an
equality.  A corner point in n dimensions must have at least n
constraints that are active/tight.  To specify such a point, declare n
of the tight constraints to be non-basic and the rest to be basic
(actually, the n you pick need to be linearly independent also).  You
don't have to specify the coordinates, just say which constraints are
non-basic.

It is not trivial to find a basic solution "near" a solution that isn't
basic, but this might be good code to add to GLPK in the future.
Compared to other needs, however, I would rate it as low priority.  So
if you want to specify your solution, you need to find a basic one and
specify it as I indicated above.

Brady