[Ipopt] solving maxflow as LP

[sdirkse at gams.com]

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