Re: [Help-glpk] Two capabilities questions

[Andrew Makhorin]

>Would it be possible for you to provide an example which supplies the
>solver with an intial solution?

LPI problem object, pointer to which is passed to the most glpk api
routines, contains data related to source LP problem data as well as
solution information stored by the solver. In particular, LPI object
contains a basic solution information for every row (auxiliary
variable) and every column (structural variable). This information
(which can be obtained using api routines glp_get_row_soln and
glp_get_col_soln, and also may be changed by the application program
using api routines glp_put_row_soln and glp_put_col_soln) includes:

a) row/column status: 'B' - basic variable, 'L' - non-basic variable on
   its lower bound, 'U' - non-basic variable on its upper bound, 'F' -
   free non-basic variable, 'S' - fixed non-basic variable;

b) row/column primal activity;

c) row/column dual activity.

When the application program calls the simplex solver routine with
default control parameters, on entry the basis information is ignored,
but is stored on exit. However, if you want the solver to start from
some pre-defined initial basis, you should do the following:

1. Specify row/column status for *all* rows and columns of your problem
   using api routines glp_put_row_soln and glp_put_col_soln. Only the
   status should be specified (the parameter tagx), because row/column
   activities are ignored by the solver in any case.

2. Tell the solver to use an initial basis specified in the problem
   object. This is attained by setting the corresponding control
   parameter passed to the solver.

Note that the basis information passed to the solver should define a
valid basis, i.e.

1. Number of basic rows and columns should be equal to number of rows,
   and number of non-basic rows and columns should be equal to number of
   columns;

2. Rows and columns of any type can be basic. But the status of
   every non-basic variable should correspond to its type as follows:

   type = 'F' => tagx = 'F';
   type = 'L' => tagx = 'L';
   type = 'U' => tagx = 'U';
   type = 'D' => tagx = 'L' or 'U';
   type = 'S' => tagx = 'S'.

   (Note that if the application program changes bounds of rows and
   columns using api routines glp_set_row_bnds and glp_set_col_bnds,
   the row/column statuses are *not* changed automatically.

"Warm" start (i.e. using a pre-defined initial basis) is supported only
by the routines glp_simplex1 and glp_simplex2; the routine glp_call_rsm1
doesn't support this feature. In order to activate this feature you
should set the control parameter initb, which is a member of structures
spx1 and spx2 passed to the solver routines (please see comments in the
file 'glpk.h'; you also can look at comments in the file 'glpapi.h' in
order to understand what information is stored in LPI object).

When the solver routine reports that a LP problem has been successfully
solved, the basis information stored in LPI object is valid. If then
you need to modify the problem keeping the basis valid, the following
hints may be useful:

* if you change bounds of rows/columns not changing their type, or if
  you change the type of basic rows/columns, you needn't to change their
  status;

* if you change the type of non-basic rows/columns, you should change
  their status correspondingly keeping them non-basic (for instance, if
  a non-basic column had only a lower bound, but now you make it having
  an upper bound, you should change its current status 'L' to 'U');

* if you add a new row to the problem, you should mark it as basic, i.e.
  set its status to 'B';

* if you add a new column to the problem, you should mark it
  as non-basic, i.e. set its status to 'L', 'U', 'F', or 'S' depending
  on its type;

* removing a basic row or a non-basic column from the problem keeps the
  basis valid;

* removing a non-basic row or a basic column makes the basis invalid.
  Therefore before doing that you should make all non-basic rows, which
  you need to remove, to be basic, and all basic columns, which you need
  to remove, to be non-basic. For this purpose two additional api
  routines glp_pivot_in and glp_pivot_out are intended (the description
  is given in the file 'newapi.txt');

* instead "physically" deleting a row you may just make it free (i.e. of
  'F' type), that gives the same effect as deleting, but allows keeping
  the basis valid independently on the row status. Analogously, instead
  "physically" deleting a column you may just fix it at zero (make it of
  'S' type with zero bounds);

* in order to view the basis information at any point you can call the
  api routine glp_print_soln.

Here is some example:

   LPI *lp;
   struct spx2 parm;
   int i, j, ret;
   ...
   /* build an initial problem */
   lp = glp_create_prob(...);
   ...
   /* solve the initial problem */
   ret = glp_simplex2(lp, NULL);
   if (ret != 0) goto ...;
   /* now the basis information stored by the solver in the object,
      which lp points to, is valid */
   /* add a new row */
   glp_new_row(lp, NULL);
   i = glp_get_num_rows(lp); /* the new row reference number */
   glp_set_row_bnds(lp, i, 'G', ...);
   glp_new_aij(lp, i, ...);
   /* mark the new row as basic */
   glp_put_row_soln(lp, i, 'B', 0.0, 0.0);
   /* add a new column */
   glp_new_col(lp, NULL);
   j = glp_get_num_cols(lp); /* the new column reference number */
   glp_set_col_bnds(lp, j, 'D', ...);
   ...
   /* mark the new column as non-basic on upper bound */
   glp_put_col_soln(lp, j, 'U', 0.0, 0.0);
   /* solve the modified problem */
   glp_init_spx2(&parm);
   parm.initb = 2; /* tell the solver to use "warm" start */
   ret = glp_simplex2(lp, &parm);
   if (ret != 0) goto ...
   /* process the obtained basic solution */
   ...

I hope my comments will help you. If you will have any other questions
about glpk, please don't hesitate to ask me.