[Ipopt] solving maxflow as LP

[Kelly, Jeff (ON0F)]

All;

I would like to add a couple of more points regarding solving an LP with
a QP code such as IPOPT.

1. If you have a large LP problem as in this case then solve it with an
LP code designed for large-scale problems (at least sparse) because
there is a lot of extra over-head in managing the Hessian, etc. in the
algorithm when it is not required.  I have done this is the past with an
internal simplex-based SQP having it solve a large LP and it is not
appropriate do to this - it makes both parties look bad.

2. My experience with LP_SOLVE is that it is *very* slow to transfer the
sparse Jacobian or LP matrix to its internal data structures and it is
also not that efficient for solving problems with > 100,000 rows/columns
(medium-sized).  I have also used GNU LP Kit and it is faster to
transfer the model to the solver but both suffer from the fact that they
are only appropriate for medium sized problems.  I am also a very big
user of FICO Xpress solving LP, QP, MILP and SLP problems in the
1,000,000 row/column range (before presolve) and I would expected your
problem to take < 1-hour after its presolve would run in < 5-minutes.

3. If you are comparing a Ford-Fulkerson approach then actually what you
need to use is a dual-simplex method because it is more like a
network-LP.  Before a presolve with dual reductions (AMPL only does
primal reductions) I would expect an interior-point to work better for
such a large-scale max-flow problem.  However, after presolve with dual
reductions, I would expect the dual-simplex to be better.

I hope this helps - 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: Wednesday, October 20, 2010 4:18 AM
To: ipopt at list.coin-or.org
Subject: Re: [Ipopt] solving maxflow as LP

Thanks for the replies.

I do not think that AMPL spends long time on the processing and
passing the problem to ipopt; after starting the optimisation, I
checked the processes (unix) and saw that AMPL did take some 10
minutes and then ipopt got started to run (for 24 hours or so). After
reading your replies, my guess is that mumps takes that long time at
the beginning.

I made the change suggested by Jeff (see his 3rd point) in the AMPL
model, it helps, but only on the AMPL side, now it takes only 2
minutes to get ipopt started... However, it seems that this trick does
not help to ipopt, it is still running for long time.

I guess changing the mumps to pardiso and using an optimised blas
would help, these will be the next steps.

As a matter of fact, I would still like to use AMPL+ipopt, because
(among other things) I wanted to see if I can compare the running time
of it vs. a Ford-Fulkerson implementation in java. This is why I am
not using ipopt with c++ code.

Thanks again,
Tamas

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