[Clp] Basis maintenance in presolve

[Rune Møller Jensen]

Hi,

 

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? 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?

 

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?).

 

Any help on this is greatly appreciated!

 

Best regards

Rune  

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20100406/018a8284/attachment.html>