Re: [Help-glpk] basis invalid after lpx_del_cols

[Andrew Makhorin]

> Some unexpected behavior came up when using the COIN-OR OSI interface to
> GLPK.
> 
> After a call to lpx_del_cols that removes one column (evidently a basic
> one), the code calls lpx_simplex to optimize the changed problem.
> However, this call fails with a "basis is invalid" error.
> 
> I have traced through the code, so I think I have a sense of what's
> happening, which I've listed below.  I'm not sure how this should be
> handled.  Andrew (or anyone), what is your advice?  How can we call
> lpx_simplex after a call to lpx_del_cols?
> 
> Brady
> 
> 
> How I think the code works:
> - when columns are added, they are by default made nonbasic
> - when rows are added, they are by default made basic
> - the basis can be changed with a call to lpx_adv_basis or a prior call
> to lpx_simplex
> - when lpx_simplex is called, it calls spx_simplex, which eventually
> calls spx_warm_up
> - spx_warm_up will cause the program to fail if the basis is the wrong
> size or not invertible
> - although I haven't tested them, there seem to be a number of ways the
> basis could become invalid:
>   + lpx_del_cols removes a basic column
>   + lpx_del_rows removes a nonbasic row
>   + lpx_add_rows adds a row that is linearly dependent on the current basis

The code works exactly as you think.

Removing a basic column make the current basis invalid and leads to
the error on a subsequent call lpx_simplex.

There are three principal ways to provide validity of the basis:

1. Make the column non-basic before removing it from the problem.
   This can be attained by replacing it by any appropriate non-basic
   row/column which enters the basis instead.

2. Fix the column at zero rather than remove it. Mathematically this
   is the same as the column would be removed. Physically the column
   may be removed any time later once it will have left the basis.

3. Construct a valid basis using lpx_adv_basis or a similar routine.
   (This is a bad idea in case of re-optimization.)


Andrew Makhorin