Along the same line, I think lp_solve should also be a good candidate to try.<br><br>
<div class="gmail_quote">On Tue, Oct 19, 2010 at 7:33 PM, Horand Gassmann <span dir="ltr"><<a href="mailto:Horand.Gassmann@dal.ca">Horand.Gassmann@dal.ca</a>></span> wrote:<br>
<blockquote style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote">Aside from understandable pride in one's product, is there any reason<br>why nobody has suggested to use a linear solver such as clp for this<br>
problem?<br><br>gus gassmann<br>
<div>
<div></div>
<div class="h5"><br><br><br><a href="mailto:sdirkse@gams.com">sdirkse@gams.com</a> wrote:<br><br>> Andreas,<br>> I won't try to make a model with 10.7 million NZ seem trivial but it<br>> shouldn't be that tough either. In general we expect the solver to<br>
> take up most of the time, not GAMS. So the reported times are not<br>> what I expect.<br>><br>> Tamas, I would be interested to see the AMPL code for this and the<br>> original data to see what the times look like in GAMS.<br>
><br>> -steve<br>> Sent on the Sprint® Now Network from my BlackBerry®<br>><br>> -----Original Message-----<br>> From: Andreas Waechter <<a href="mailto:andreasw@watson.ibm.com">andreasw@watson.ibm.com</a>><br>
> Sender: <a href="mailto:ipopt-bounces@list.coin-or.org">ipopt-bounces@list.coin-or.org</a><br>> Date: Tue, 19 Oct 2010 17:21:05<br>> To: Kelly, Jeff (ON0F)<<a href="mailto:jeff.kelly@honeywell.com">jeff.kelly@honeywell.com</a>><br>
> Cc: ipopt mailing list<<a href="mailto:ipopt@list.coin-or.org">ipopt@list.coin-or.org</a>><br>> Subject: Re: [Ipopt] solving maxflow as LP<br>><br>> Hi Tamas,<br>><br>> A few additional comments:<br>
><br>> - AMPL communicates the problem to Ipopt via a file, with the extension<br>> ".nl" . AMPL is not really well suited for large problems, and it can<br>> take the AMPL Solver Library (with which the AMPL Ipopt executable is<br>
> linked) a very very long time just to read in this data file and to set up<br>> the internal data structures.<br>><br>> So, if it takes 20 hours before you see the printout of the size<br>> statistics that you included, it means that all this time is just to set<br>
> up AMPL data structures before Ipopt is doing anything. To speed this up,<br>> you need to use programming code (e.g., C++) to code your problem.<br>><br>> It could also be that MUMPS takes a lot of time in the symbolic<br>
> factorization. In general, I would suggest to use a different linear<br>> solver (Pardiso, WSMP) for such large problems. Here, make sure you are<br>> using some optimized BLAS as well. This is probably the easiest thing to<br>
> try first.<br>><br>> (If you use Ipopt via AMPL, the Jacobian, as well as the Hessian, are<br>> giving analytically, so there is no finite difference approximation)<br>><br>> Hope this helps,<br>><br>
> Andreas<br>><br>> On Tue, 19 Oct 2010, Kelly, Jeff (ON0F) wrote:<br>><br>>> Tama;<br>>><br>>> Is the AMPL primal presolve turned on? It is important to turn on for<br>>> IPOPT because IPOPT does not recognize linear singleton constraints to<br>
>> perform primal reductions. It assumes all constraints are non-linear<br>>> i.e., every non-zero in the Jacobian is a function of one or more of the<br>>> variables which for your problem is not the case.<br>
>><br>>> In the startup phase, does IPOPT create the Jacobian matrix using<br>>> finite-difference? If so then this is extremely inefficient because<br>>> IPOPT does not partition the variables into "groups" using a<br>
>> graph-coloring algorithm such as TOMS 618 by Coleman et. al. (1984).<br>>> This will more than substantially speedup of the generation of constant<br>>> Jacobian because it will reduce the number of function evaluations.<br>
>><br>>> Also, for max-flow problems where there can be many doubleton "x(i) -<br>>> x(j) = 0 for j<>i" constraints you may look at adding your own presolve<br>>> to remove x(j) and the transfer/connection equality from the solver -<br>
>> you will however still need to include x(j) in your modeling of course<br>>> i.e., x(j) = x(i) where x(i) is from the solver and x(j) is now an<br>>> "internal" modeling variable.<br>>><br>
>> All the best - Jeff<br>>><br>>> -----Original Message-----<br>>> From: <a href="mailto:ipopt-bounces@list.coin-or.org">ipopt-bounces@list.coin-or.org</a><br>>> [mailto:<a href="mailto:ipopt-bounces@list.coin-or.org">ipopt-bounces@list.coin-or.org</a>] On Behalf Of Tamas Vinko<br>
>> Sent: Tuesday, October 19, 2010 2:00 PM<br>>> To: <a href="mailto:ipopt@list.coin-or.org">ipopt@list.coin-or.org</a><br>>> Subject: [Ipopt] solving maxflow as LP<br>>><br>>> Hello,<br>>><br>
>> I am trying to solve a huge max-flow problem, formulated as an LP with<br>>> ipopt+ampl (using mumps).<br>>> The size of the problem is:<br>>><br>>> Number of nonzeros in equality constraint Jacobian...: 10748378<br>
>> Total number of variables............................:<br>>> 5374189<br>>> variables with lower and upper bounds: 5374188<br>>> Total number of equality constraints.................:<br>
>> 37546<br>>><br>>> Now, ampl takes about 10 minutes before it passes the problem to<br>>> ipopt. Then, ipopt takes about 20 hours to start with the first<br>>> iteration and finally converges to the solution in 3-4 hours.<br>
>><br>>> Do you have any advice how can I speed up the solving time, especially in<br>>> the startup phase?<br>>><br>>> Thanks,<br>>> Tamas.<br>>><br>>> _______________________________________________<br>
>> Ipopt mailing list<br>>> <a href="mailto:Ipopt@list.coin-or.org">Ipopt@list.coin-or.org</a><br>>> <a href="http://list.coin-or.org/mailman/listinfo/ipopt" target="_blank">http://list.coin-or.org/mailman/listinfo/ipopt</a><br>
>><br>>><br>>> _______________________________________________<br>>> Ipopt mailing list<br>>> <a href="mailto:Ipopt@list.coin-or.org">Ipopt@list.coin-or.org</a><br>>> <a href="http://list.coin-or.org/mailman/listinfo/ipopt" target="_blank">http://list.coin-or.org/mailman/listinfo/ipopt</a><br>
>><br>>><br>><br>> _______________________________________________<br>> Ipopt mailing list<br>> <a href="mailto:Ipopt@list.coin-or.org">Ipopt@list.coin-or.org</a><br>> <a href="http://list.coin-or.org/mailman/listinfo/ipopt" target="_blank">http://list.coin-or.org/mailman/listinfo/ipopt</a><br>
><br>> _______________________________________________<br>> Ipopt mailing list<br>> <a href="mailto:Ipopt@list.coin-or.org">Ipopt@list.coin-or.org</a><br>> <a href="http://list.coin-or.org/mailman/listinfo/ipopt" target="_blank">http://list.coin-or.org/mailman/listinfo/ipopt</a><br>
><br>><br><br><br><br>_______________________________________________<br>Ipopt mailing list<br><a href="mailto:Ipopt@list.coin-or.org">Ipopt@list.coin-or.org</a><br><a href="http://list.coin-or.org/mailman/listinfo/ipopt" target="_blank">http://list.coin-or.org/mailman/listinfo/ipopt</a><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>--------------------------------------------------<br>Binh Nguyen<br>Computer Science Department<br>Rensselaer Polytechnic Institute<br>Troy, NY, 12180<br>--------------------------------------------------<br>