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

[John J Forrest]

Laci,

I agree that OsiSolverInterface::addRows is the fastest way but that does 
mean knowing in advance how many rows will be added and guessing number of 
elements or using a complicated structure holding CoinPackedVectors and 
bounds.  I put in CoinBuild as it means user has to change one line of 
code and add two more trivial lines and you get same speed as addRows 
minus probably 1 %.

John



ladanyi at watson.ibm.com 
Sent by: coin-discuss-bounces at list.coin-or.org
02/04/2005 01:50 PM
Please respond to
Discussions about open source software for Operations Research 


To
Discussions about open source software for Operations Research 
<coin-discuss at list.coin-or.org>
cc
coin-lpsolver at list.coin-or.org
Subject
Re: [Coin-discuss] Re: [Coin-lpsolver] Problem creation performance






This is is a reasonable solution, but I'm not sure it's necessary. Maybe 
just
the documentation should be clearer that adding rows/cols one-by-one is 
not
the brightest thing to do; one should use the addRows/addCols methods
instead. This CoinBuild class is just a vehicle to make this clear to the
user, right? (Which might be a good enough reason for its existence...)

--Laci

On Fri, 4 Feb 2005, John J Forrest wrote:

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


_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20050204/42531f66/attachment.html>