Re: [Help-glpk] Initial Basis

[Michael Hennebry]

On Fri, 18 Nov 2005, Brady Hunsaker wrote:

> Ulrich Spörlein wrote:
> > 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.

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

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

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

Here is something one might try.
Given a useful solution, adjust the variable
bounds to make it a basic feasible solution.

Solve the problem with the adjusted bounds.
If none of the adjusted bounds are active,
the solution is optimal.

Otherwise, replace the adjusted bounds
with the originals and give the variables
that had active adjusted bounds new adjusted
bounds having the opposite sense,
e.g. a variable that has original bounds [0, 1]
and had adjusted bound <=0.7 (effective bounds [0, 0.7])
will have new adjusted bound >=0.7 (effective bounds [0.7, 1]).
Getting GLPK to do this without recomputing
the basis from scratch might not be possible.

Solve the problem with the adjusted bounds....

-- 
Mike   address@hidden
"I AM DEATH, NOT TAXES.  *I* ONLY TURN UP ONCE."  --  Death