[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Non-sparse problems and other questions
From: |
Erik de Castro Lopo |
Subject: |
Re: [Help-glpk] Non-sparse problems and other questions |
Date: |
Mon, 3 Jun 2002 05:56:55 +1000 |
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