Re: [Help-glpk] How glpsol works

[Andrew Makhorin]

> I wanted to know roughly how glpsol works.

> It generates every constraints
> it creates original LP
> it creates presolved LP
> it finds an optimal solution.

> What I want to know is how it uses memory. What is the LP table ? Does
> it copy table deleting empty rows and columns ? And so on...

> Just to understand a little bit how I could optimise my memory use.

When you invoke glpsol with option '-m', the following things happen:

1. The mathprog translator reads model and data sections and translates
   them to an internal data structures (translator database).

2. Glpsol extracts lp/mip components (i.e. rows, columns, constraint
   coefficients, etc.) from the translator database and builds the
   problem object (glp_prob). The translator database is not deallocated
   at this stage.

3. Glpsol calls glp_simplex to solve lp relaxation passing to it the
   original glp_prob object.

4. By default the lp presolver is enabled, so glp_simplex calls the lp
   presolver, which builds another, presolved problem object (glp_prob),
   and keeps information needed to restore original solution components.

5. Glp_simplex transforms the presolved problem object to an internal
   representation used by the simplex solver. The latter solves the lp
   instance, and glp_simplex copies components of the solution back to
   the presolved problem object.

6. The lp presolver reads solution components of the presolved instance,
   builds solution components of the original instance, and store them
   in the original problem object.

7. Glp_simplex deallocates the presolved problem object and returns
   to glpsol.

9. In case of mip, glpsol calls glp_intopt to find mip solution.

10.Then glpsol extracts solution components from the problem object and
   passes them to the mathprog translator to perform optional statements
   that may follow the solve statement.

11.Finally glpsol deallocates the translator database and the problem
   object.

For more details about glpsol program logic please see src/glplpx20.c.