[Coin-lpsolver] PreProcessing

[John J Forrest]

Justin,

Preprocessing can be applied to continuous LPs or ones with some integers. 
 Let's take the continuous case first.  The presolve for Clp was written 
first, but then it could be useful for other solvers so an 
OsiSolverInterface interface to the presolve was written.  To make this 
work the guts of the presolve code was moved to the Coin directory - files 
starting CoinPresolve.  The ClpPresolve and OsiPresolve code uses 
CoinPresolve.... code.

When you have integer variables then you can apply the continuous 
preprocessing techniques but you also want to do more.  The three 
techniques that come to mind.

1) For problems with unit coefficients and unit rhs CglDuplicateRow finds 
duplicate rows and more importantly rows which are subsets of others as 
then variables can be fixed.
2) If x -> 1 means y -> 0 AND x->0 means y->1 then we can substitute for x 
or y.  This may be detected by CglProbing
3) If x-> makes a constraint slack then a coefficient in that row can be 
strengthened.  This is also done by CglProbing.

Because Cgl functions are used the controlling function was put there as 
well - hence CglPreProcess.

Overall more work is needed on the CglPreProcess part than on the 
continuous presolve part but contributions to either would be very 
welcome.

John Forrest



jtyates at buffalo.edu 
Sent by: coin-lpsolver-bounces at list.coin-or.org
02/24/2006 06:06 PM

To
coin-lpsolver at list.coin-or.org
cc

Subject
[Coin-lpsolver] PreProcessing






I noticed that the Cgl project contains a source code for preprocessing
of optimization problems.  I also noticed that Clp had something called
presolve.  I was wondering if Clp had any preprocessing applications
within the project itself and whether this was contained in the presolve
file or called something else. 

Also, when using Clp as the LP solver, is there anywhere other than Cgl
that is called to perform any types of preprocessing steps. 

Basically, I am working with a group from the University of Buffalo that
is interested in possibly contributing to the preprocessing capabilities
of COIN-OR and am trying to find out any (and all) locations where any
preprocessing would be done or called in COIN-OR (and specifically, in 
CLP).

Thank you.

Justin

__________________________________________
Mr. Justin .T. Yates
Department of Industrial Engineering
State University of New York at Buffalo
415 Lawrence D. Bell Hall
Buffalo, NY 14260-2050
_______________________________________________
Coin-lpsolver mailing list
Coin-lpsolver at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-lpsolver

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