Re: [Help-glpk] Non-sparse problems and other questions

[Erik de Castro Lopo]

On Sun, 2 Jun 2002 12:00:48 +0400
"Andrew Makhorin" <address@hidden> wrote:

> If you know (or can estimate) numerical values of variables at some
> point, even if this point is close to the optimal one, this is useless
> for the simplex method. 

OK. Are you thinking of implementing any other solvers which would allow
the feature I am after?

> In order to start from a given point the simplex
> method needs to know so called basic solution, i.e. you should tell it
> which constraints are active (i.e. for which the corresponding auxiliary
> and structural variables are placed on their lower or upper bounds) and
> which are non-active. 

OK, I have finally understood the idea of the "basic solution". 

> This information is passed to the simplex method
> via the routines lpx_set_row_stat and lpx_set_col_stat and *implicitly*
> defines numerical values of variables at the corresponding point (which
> can be computed using the routine lpx_warm_up).

Unfortunately, I can't see this possibility being of very much use in my 
situation. I will investigate it though.

> In principle, it possible to identify a basic solution that corresponds
> to some interior point solution (as in your case), however this feature
> is not implemented yet (in glpk). 

Is it planned? Any idea when you might have the time to do it?

> Nevertheless it can be efficiently
> done only if you know both primal solution, i.e. values of variables,
> and dual solution, i.e. lagrange multipliers for active constraints.

That sounds like there may be some more hurdles :-).

> You can look at the document "GLPK Implementation of the Revised Simplex
> Method" included in the distribution, where more detailed explanations
> are given.

I'll have a look at this but I fear that its going to take a *LOT* of
head scratching on my part to just come up to speed on this :-).

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  address@hidden (Yes it's valid)
+-----------------------------------------------------------+
"I've got an idea! Sun, Oracle, and IBM hold down MS while Linux 
gets to kick them!" -- Lou Grinzo on LinuxToday.com