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

[Brady Hunsaker]

John asked whether other people had noticed this performance issue with 
addRow/addColumn.  I had noticed this in the last week using Osi to 
create instances with many rows (in this case for a column generation 
routine within BCP).  We are experiencing a similar situation to 
Francois in which the time to generate the instance is often much longer 
than the solving time when we add rows one at a time.

We had not started looking at a correction, but I am enthusiastic about 
making use of John's suggestion.  How hard would it be to insulate the 
user from these issues?  Could addRow and addColumn be implemented in 
this way by default, so that the actual CoinPackedMatrix or 
OsiSolverInterface is only changed when certain other methods are 
called?  Or is it better to require that the user make this distinction?

Brady

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


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