[Clp] Basis maintenance in presolve

[Julian Hall]

Dear Rune,

> We are currently implementing some specialized presolve actions. We want 
> these to maintain a basis of the original model as is already done by 
> the current
> 
> presolve actions.  However, it is not clear to us how this actually 
> happens. For instance, for a forcing constraint like
> 
>  
> 
> 2x + 4y <= 0  ,   0 <= x,  0 <= y
> 
>  
> 
> it seems that Clp presolve first fixes x and y at zero and removes them 
> from the matrix and after that removes the row since it has become 
> empty. But what if x or y are basis variables?

Before presolve, perform a fresh inversion of the basis matrix---if 
using the Clp INVERT, you'll have to know the relationship between basic 
columns and pivotal rows.

There will be pivots corresponding to x and y. Introduce into the basis 
the slack variables corresponding to these rows. [They can't already be 
basic since they would be the pivots in their "home" row.]

> Also every time, we remove a row, we cause the basis columns to become linearly dependent, 
> so which column should we remove from the basis?

Remove the column corresponding to the pivot in that row.

> Basis maintenance in presolve seems non-trivial, but we have not been 
> able to find any literature discussing the issue.
> 
> Is there a simple answer to how this is done or do you know a good ref 
> describing how to do it? (The presolve source code refers to some 
> article here and there. Would that be Andersen & Andersen?).

If you are fully conversant with the basis factorization, then it's not 
so difficult.

I assume that you're not trying to perform your specialized presolve 
actions after calling the Clp presolve. Doing this it sounds hazardous.

Julian
--
Dr. J. A. Julian Hall, Senior Lecturer, School of Mathematics,
University of Edinburgh, JCMB, King's Buildings, EDINBURGH, EH9 3JZ, UK.
Room: 6221   Phone: [+44](131) 650 5075   Email: J.A.J.Hall at ed.ac.uk
Fax: [+44](131) 650 6553   Web: http://www.maths.ed.ac.uk/hall

-- 
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.