Re: [Help-glpk] solve, add rows, resolve

[Andrew Makhorin]

> My apologies.  It is not add_rows, but del_cols that is an issue.  I
> wrote the previous email from memory, which was incorrect.
> 
> I am attaching a test case.  If we remove the first column of p0033, 
> then re-solving fails.  However, if you remove the second column, it 
> succeeds.  You can check this by changing the index to be removed.
> 
> Presumably the first column is basic in the original solution and the 
> second column is non-basic.

Yes, it is expected behavior.

> 
> My question is this:
> - If a basic column is removed, what behavior do you expect from GLPK? 
> Should it adjust the basis and resolve?  Resolve starting from the 
> beginning (a new basis)?  Fail?

In principle, it would be possible to implement a "smart" mode,
i.e. if before modifying the problem instance its basis is valid, do
something in order to keep it valid after modifications have done.
However, such a mode would be: (a) very time-consuming, and
(b) useless if the model is not intended to be reoptimized later.

So, I decided to keep only statuses of rows and columns stored in
LPX object. The statuses are initially assigned on creating rows and
columns (by default the row is basic and the column is non-basic),
and then they are not changed until either the solver routine change
them or the application program explicitly does that through the
routines lpx_set_row_stat/lpx_set_col_stat. No checks are made until
the basis factorization actually needs to be computed, i.e. the
statuses can be changed arbitrarily at any time.

If, on creating the lp instance, the application did not change the
statuses, then the basis is valid, because all rows (i.e. slacks, or
more precisely, artificial variables) are basic and all columns
(structural variables) are non-basic. The routines lpx_adv_basis and
lpx_cpx_basis produce advanced basis changing the statuses and
guarantee that the new basis is valid. If lpx_simplex terminates
successfully, it is also guarantees that the final basis is valid
independently on the primal/dual solution status. Thus the basis can
become invalid only in the two cases: a) basic row/column is made
non-basic or vice versa by excplicitly changing its status; and
b) non-basic rows (active constraint) and/or basic columns have been
removed from the instance.

Note that the case (b) should happen in re-optimization. Indeed, if
you are using cutting planes or "lazy" constraints, you either add
new rows which becoming basic retain the basis valid, or remove
non-active constraints, i.e. basic rows, in which case the basis also
remains valid. If you are using column generation, you either add new
and therefore non-basic columns or remove non-basic columns to
temporarily or permanently fix them at zero, and again the basis
remains valid.

I think an intelligent way to remove a basic column is to fix it
at zero instead to remove it immediately and keep it so until it has
became non-basic, in which case it can be safely removed. The same
way can be used to remove a non-basic row: we make it free and wait
until it has entered the basis.

Another (less intelligent) way is to compute the row of the simplex
tableau corresponding to the basic column to be removed
(lpx_eval_tab_row), find an appropriate non-basic row or column
having non-zero influence coefficient, and change to the adjacent
basis, where the basic column becomes non-basic while the non-basic
row/column becomes basic. Note, however, that on api level currently
there is no routine to perform this pivot operation efficiently, so
using lpx_set_row_stat and lpx_set_col_stat to change the basis will
destroy lu-factorization for the current basis (which is also kept
in LPX object from the last call to lpx_warm_up or lpx_simplex).


Andrew Makhorin