Re: [Help-glpk] restart interior point method

[Andrew Makhorin]

>Ok, I will try the hacking.
>I guess that the general methodology for the hacking would be:
>
> - create a structure type that can hold solver information (as
>spx1,spx2,etc...) as for instance the symbolic factorisation and a flag
>to tell to keep it or recompute it
> - when entering glp_call_ipm1 check the flag and maybe avoid symbolic
>factorisation going straight to the iteration

In general you are right. However I suggest an easier way.

When you call the interior point solver the following calling sequence
is used (filenames correspond to glpk 3.0.5):

your program -> glp_call_ipm1 (glpapi3.c) ->
             -> ipm1_driver (glpipm2.c) ->
             -> ipm1 (glpipm1.c)

glp_call_ipm1 is api routine that copies input data from LPI to
internal data structures, passes them to ipm1_driver, and copies an
obtained solution back to LPI.

ipm1_driver accepts the original lp problem, transforms it to the
standard formulation (min Z = c'x; A*x = b; x >= 0), calls the interior
point solver, and converts the obtained solution of the transformed
problem back to the solution of the original problem.

ipm1 is the interior point solver itself.

You need to change only the file 'glpipm1.c' in the following way (line
numbers correspond to glpk 3.0.5):

1. Copy the file 'glpipm1.c' to your own directory.

2. Find the fragment (lines 151-152)

      static ADAT *adat;
      /* Cholesky factorization of the matrix A*D*A' */

   and replace it by

      ADAT *adat = NULL;
      /* Cholesky factorization of the matrix A*D*A' */

3. Find the fragment (line 254)

      adat = create_adat(A);

   and replace it by

      if (adat == NULL) adat = create_adat(A);

4. Find the fragment (line 824)

      delete_adat(adat);

   and replace it by

      /* delete_adat(adat); */

5. Compile your program specifying explicitly the changed version of
   the file 'glpipm1.c':

      gcc main.c glpipm1.c ... -lglpk ...

That's all.

Thus, the symbolic factorization will be computed only once on the
first call to glp_call_ipm1. Note that you *must not* to change the
pattern (i.e. distribution of non-zero elements) of the constraint
matrix as well as types of rows and columns after the first call to
glp_call_ipm1, because this involves changing the pattern of the
constraint matrix of the transformed problem and therefore makes the
symbolic factorization invalid; only numerical values of constraint
coefficients and, of course, other numerical components like values of
objective coefficients and bounds of rows and columns may be changed.

In order to cancel the symbolic factorization (if necessary), you need
to include the following fragment somewhere in your program:

      #include "glpchol.h"
      ...
      extern ADAT *adat;
      ...
      /* cancel the symbolic factorization */
      assert(adat != NULL);
      delete_adat(adat);
      adat = NULL;
      ...

>Could you send me asap (before WE if possible) any additional doc that
>would be nice I have  that is not in the source of glpk-3.0.5 ?

Unfortunately not, because currently a description of the glpk interior
point implementation is only in Russian :+(