[Ipopt] solving maxflow as LP

[Kelly, Jeff (ON0F)]

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
the startup phase?

Thanks,
Tamas.

_______________________________________________
Ipopt mailing list
Ipopt at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/ipopt