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

[Andrew Makhorin]

>I am continuing on my quest to improve the speed of the solver. Currently
>I think the biggest gains in this area are to be achieved by supplying the
>solver with a near-feasible initial solution.
>
>I have looked at the routines lpx_set_row_stat() and lpx_set_col_stat()
>and I do not think they can help me placing an initial solution into the
>solver. This may simply be a reflection on my poor understanding of the
>LP terminology and process.

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

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

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