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

[John J Forrest]

Jean-Sebastien,

I like your idea of hashing but I am thinking of putting more work into 
CoinBuild to make it more useful so I may want to iterate over nonzeros in 
row or column which is difficult with hashing.  I think I will spend a few 
hours coding up something which will be efficient with addRow or addColumn 
but slightly less efficient with random modifications - using binary 
search on linked lists or something like that.

I will post more when I have coded something more ambitious.  I suspect I 
will be re-inventing the wheel but it will a coin shaped wheel.

John Forrest



Jean-Sebastien Roy <js at jeannot.org> 
Sent by: coin-discuss-bounces at list.coin-or.org
02/04/2005 02:59 PM
Please respond to
Discussions about open source software for Operations Research 


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

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






As alternative, I've often used a hash-table ((int,int) -> double, with 
0 values not stored) to  store & modify the coefficient matrix, put all 
the elements in an array and sort them before using the Coin 
loadProblem() function to instantiate the problem.

It's quite easy to code (I did it in C, it should be much easier in 
C++), enables reasonnably fast input and update of the coefficient 
matrix, and fast instantiation (the sort usually doesn't take much time).

Regards,

js

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
_______________________________________________
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/20050205/ea678715/attachment.html>