[Ipopt] solving maxflow as LP

Wed Oct 20 02:08:13 EDT 2010

Along the same line, I think lp_solve should also be a good candidate to
try.

On Tue, Oct 19, 2010 at 7:33 PM, Horand Gassmann <Horand.Gassmann at dal.ca>wrote:

> 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
> >
> >
>
>
>
> _______________________________________________
> Ipopt mailing list
> Ipopt at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/ipopt
>

-- 
--------------------------------------------------
Binh Nguyen
Computer Science Department
Rensselaer Polytechnic Institute
Troy, NY, 12180
--------------------------------------------------
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/ipopt/attachments/20101020/741a4fac/attachment-0001.html 