[Coin-discuss] Re: [Coin-lpsolver] Problem creation performance

[John J Forrest]

Apologies for double posting but it is more general than Clp.

Francois mentioned that there was a large overhead to using addColumn 
(i.e. adding one at a time) in Clp.  As Clp is using CoinPackedMatrix this 
probably also applies to other codes using CoinPackedMatrix, including 
some implementations of Osi.  I had realized there was an overhead to 
addRow but had not realized it is worse for addColumn.

My solution is to add a new class to Coin - CoinBuild.  The user 
instantiates an empty CoinBuild object and then performs addRow (or 
addColumn but not a mixture) in the same was as addRow (or addColumn) for 
an OsiSolverInterface model.  This stores the information in a linked 
list.  Then the user uses model.addRows(object) to get the information to 
its final destination.  There is addRows/addColumns in Clp and 
addRows/addCols in OsiSolverInterface.

Doing this reduced the time for adding 10,000 rows from 0.53 seconds to 
0.04 and for adding 10,000 columns from 5.71 seconds to 0.03.

(Francois - see Clp/Samples/addColumns.cpp for sample code).

The reason for posting this to Coin-discuss was to tell people it was 
available and to ask if other people had noticed the performance hit. Also 
to see if my solution is adequate.

John Forrest




François Galea <Francois.Galea at prism.uvsq.fr> 
Sent by: coin-lpsolver-bounces at list.coin-or.org
02/04/2005 03:15 AM

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

Subject
[Coin-lpsolver] Problem creation performance






Hi !

I have a question concerning the Clp library API.

I need to generate different LPs (my previous question about QPs has no 
relation with this problem), whose size is about 2500 rows, 2500 columns 
and 250000 non-zeros. The model is such that it's easier for me to 
create an empty problem object using the ClpSimplex() constructor :

ClpSimplex * simplex = new ClpSimplex();

then I populate it column-wise, by first performing a series of calls 
like this:

simplex->addRows( rcnt, lb, ub, rowstarts, NULL, NULL );

then I add the columns by a series of this kind of calls :

simplex->addColumns( 1, &lb, &ub, &objcoef, colstarts, ind, val );

This leads to a major problem, that the creation of the problem is much 
slower than its resolution. Maybe Clp is more performant when creating 
simplex objects row-wise than column-wise, but I really need to create 
my problem objects this way.

Most of the examples I found in the Clp documentation create ClpSimplex 
objects by reading MPS files, and the only one I found that creates an 
object from scratch provides the whole simplex matrix at once, which is 
okay when you can easily find the size of the problem before creating 
the object, but it not okay for me.

Could I get a link to a more complete documentation than the one I found 
in the Clp website, which only mentions the addRows and addColumns 
methods once ? Or can anybody tell me why I get such a low model 
creation speed, and how to make things faster ?

Thanks for the help,

François Galea

_______________________________________________
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/coin-discuss/attachments/20050204/d778bde2/attachment.html>