<br><font size=2 face="sans-serif">Jean-Sebastien,</font>
<br>
<br><font size=2 face="sans-serif">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.</font>
<br>
<br><font size=2 face="sans-serif">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.</font>
<br>
<br><font size=2 face="sans-serif">John Forrest</font>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td width=40%><font size=1 face="sans-serif"><b>Jean-Sebastien Roy <js@jeannot.org></b>
</font>
<br><font size=1 face="sans-serif">Sent by: coin-discuss-bounces@list.coin-or.org</font>
<p><font size=1 face="sans-serif">02/04/2005 02:59 PM</font>
<table border>
<tr valign=top>
<td bgcolor=white>
<div align=center><font size=1 face="sans-serif">Please respond to<br>
Discussions about open source software for Operations Research
</font></div></table>
<br>
<td width=59%>
<table width=100%>
<tr>
<td>
<div align=right><font size=1 face="sans-serif">To</font></div>
<td valign=top><font size=1 face="sans-serif">coin-discuss@list.coin-or.org</font>
<tr>
<td>
<div align=right><font size=1 face="sans-serif">cc</font></div>
<td valign=top>
<tr>
<td>
<div align=right><font size=1 face="sans-serif">Subject</font></div>
<td valign=top><font size=1 face="sans-serif">[Coin-discuss] Re: [Coin-lpsolver]
Problem creation performance</font></table>
<br>
<table>
<tr valign=top>
<td>
<td></table>
<br></table>
<br>
<br>
<br><font size=2><tt>As alternative, I've often used a hash-table ((int,int)
-> double, with <br>
0 values not stored) to store & modify the coefficient matrix,
put all <br>
the elements in an array and sort them before using the Coin <br>
loadProblem() function to instantiate the problem.<br>
<br>
It's quite easy to code (I did it in C, it should be much easier in <br>
C++), enables reasonnably fast input and update of the coefficient <br>
matrix, and fast instantiation (the sort usually doesn't take much time).<br>
<br>
Regards,<br>
<br>
js<br>
<br>
John J Forrest wrote:<br>
> <br>
> Apologies for double posting but it is more general than Clp.<br>
> <br>
> Francois mentioned that there was a large overhead to using addColumn
<br>
> (i.e. adding one at a time) in Clp. As Clp is using CoinPackedMatrix
<br>
> this probably also applies to other codes using CoinPackedMatrix,
<br>
> including some implementations of Osi. I had realized there
was an <br>
> overhead to addRow but had not realized it is worse for addColumn.<br>
> <br>
> My solution is to add a new class to Coin - CoinBuild. The user
<br>
> instantiates an empty CoinBuild object and then performs addRow (or
<br>
> addColumn but not a mixture) in the same was as addRow (or addColumn)
<br>
> for an OsiSolverInterface model. This stores the information
in a <br>
> linked list. Then the user uses model.addRows(object) to get
the <br>
> information to its final destination. There is addRows/addColumns
in <br>
> Clp and addRows/addCols in OsiSolverInterface.<br>
> <br>
> Doing this reduced the time for adding 10,000 rows from 0.53 seconds
to <br>
> 0.04 and for adding 10,000 columns from 5.71 seconds to 0.03.<br>
> <br>
> (Francois - see Clp/Samples/addColumns.cpp for sample code).<br>
> <br>
> The reason for posting this to Coin-discuss was to tell people it
was <br>
> available and to ask if other people had noticed the performance hit.
<br>
> Also to see if my solution is adequate.<br>
> <br>
> John Forrest<br>
_______________________________________________<br>
Coin-discuss mailing list<br>
Coin-discuss@list.coin-or.org<br>
http://list.coin-or.org/mailman/listinfo/coin-discuss<br>
</tt></font>
<br>