[Ipopt] solving maxflow as LP

[Horand Gassmann]

Aside from understandable pride in one's product, is there any reason  
why nobody has suggested to use a linear solver such as clp for this  
problem?

gus gassmann



sdirkse at gams.com wrote:

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