[Coin-lpsolver] Problem creation performance

[Brady Hunsaker]

François Galea wrote:
> John,
> 
> My first experiments with a CoinBuild object for adding the columns to 
> the problem are more than satisfying ! :) Thanks for the good (and 
> quick) job !
> 
> François
> 
>

I'd like to second François's observation.  Using CoinBuild, I had 
row-by-row generation of an instance with about 200,000 rows reduce from 
something like 30-60 minutes (I never measured it exactly) to 3-4 
seconds.  That's about 3 orders of magnitude.  Curiously, this was true 
even though the Osi interface (OsiCpx) adds each row one at a time.  I 
guess it had been the single calls to CoinPackedMatrix::appendRow that 
were slow.

Thank you, John.

Why do we not make CoinPackedMatrix behave this way by default?  That 
is, store added rows or columns in a linked list until another method is 
called that requires the matrix.  This complicates the coding, since it 
is basically a caching framework, but would make things transparent for 
the user.  Is the complexity not worth the benefit?  Is there some other 
reason I don't see?

Brady


  John J Forrest a écrit :
> 
>>
>> 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-lpsolver mailing list
>> Coin-lpsolver at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/coin-lpsolver
> 
> 
> _______________________________________________
> Coin-lpsolver mailing list
> Coin-lpsolver at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-lpsolver


-- 
Brady Hunsaker
Assistant Professor
Industrial Engineering
University of Pittsburgh
http://www.engr.pitt.edu/hunsaker/