<br><font size=2 face="sans-serif">My best guess would be that the factorization
is getting dense. If you allow more output and set the Clp log level
to 3 or greater you should see messages like</font>
<br>
<br><font size=2 face="sans-serif"> length of U nnnnn, length
of L nnnnn</font>
<br>
<br><font size=2 face="sans-serif">If these increase dramatically then
that is probably the problem. Theoretically with 20K variables you
could have a factorization taking 400 million doubles and even more in
associated lists. It probably is not that bad but .... If you
use Lapack then DENSE_CODE will be set in various CoinFactorization files
and then you would not get the associated data and it would be much faster.</font>
<br>
<br><font size=2 face="sans-serif">If that is not the case then feel free
to send me the artificial problem to see what the problem is.</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>acw@ascent.com</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">09/25/2006 12:04 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
<coin-discuss@list.coin-or.org></font></div></table>
<br>
<td width=59%>
<table width=100%>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">To</font></div>
<td><font size=1 face="sans-serif">coin-discuss@list.coin-or.org</font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">cc</font></div>
<td>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">Subject</font></div>
<td><font size=1 face="sans-serif">[Coin-discuss] Running out of memory
in large problems</font></table>
<br>
<table>
<tr valign=top>
<td>
<td></table>
<br></table>
<br>
<br>
<br><font size=2 face="sans-serif"><br>
We are happily using Cbc in a scheduling and planning application. We
run mostly in a Windows environment.</font><font size=3> <br>
</font><font size=2 face="sans-serif"><br>
Recently, as the size of our problems increased, we have started running
into what we take to be memory problems. It may turn out that these
problems are simply too big, in which case we'll look for simplifications.
But perhaps there is an easier answer, and we're hoping that the
collective wisdom of COIN-Discuss can come to our rescue.</font><font size=3>
<br>
</font><font size=2 face="sans-serif"><br>
The problems in question have on the order of 80 K variables, and something
like 300 K constraints. Cbc fails dramatically, throwing an exception
and exiting abnormally. (Because we are running Cbc via JNI inside
a thin Java interface layer, it's hard for us to see the details of the
exception, but we are working on that.)</font><font size=3> <br>
</font><font size=2 face="sans-serif"><br>
We've duplicated the failure with artificial test problems with as few
as 20 K variables and about 265 K constraints, with less than 8 M nonzero
coefficients.</font><font size=3> <br>
</font><font size=2 face="sans-serif"><br>
The failure occurs during the call to CbcModel::initialSolve that precedes
initial cut generation; that is, it happens very early, well before the
branch-and-cut phase properly begins. We narrowed it down to ClpSimplex::dual.
In the seconds prior to failure, we observe memory usage climbing
sharply.</font><font size=3> <br>
</font><font size=2 face="sans-serif"><br>
We hypothesize that Clp is unpacking the problem in some way; clearly not
to a full (non-sparse) matrix representation, but rather to some intermediate
form.</font><font size=3> <br>
</font><font size=2 face="sans-serif"><br>
It's possible that many of our constraints are redundant; we're investigating
that ourselves. But perhaps we don't need to make the effort: maybe
there is some way to get COIN to prune the redundant constraints cautiously,
without inflating the matrix? Thanks in advance for any advice that
you might have.</font><tt><font size=2>_______________________________________________<br>
Coin-discuss mailing list<br>
Coin-discuss@list.coin-or.org<br>
http://list.coin-or.org/mailman/listinfo/coin-discuss<br>
</font></tt>
<br>