Non exact/Heuristic solvers

[Saqib Ilyas]

Hi all

My problem is pretty big (integer, linear), and CPLEX takes 6.5 hours to find the optimal solution. I am wondering if there are any non exact/heuristic solvers such as those based on Genetic Algorithms or Ants Colony Optimization that I can evaluate as a student and generate results. I found that Tomlab includes solvers based on genetic algorithms. However, when I invoke Tomlab on my problem, it gave a "starting point need to be modified" error.

Thanks and best regards

--
Muhammad Saqib Ilyas
PhD Student, Computer Science and Engineering
Lahore University of Management Sciences

[Ali MohammadNezhad]

Hi muhammad
I have a novel solver for non convex nonlinear programming problems
that its efficiency has been proved. Do you want to purchase it?

> --
>
> You received this message because you are subscribed to the Google Groups
> "AMPL Modeling Language" group.
> To post to this group, send email to am...@googlegroups.com.
> To unsubscribe from this group, send email to
> ampl+uns...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/ampl?hl=en.
>
>
>

[Robert Fourer]

Genetic algorithms and other local search heuristic procedures are typically constructed for particular problem classes.  I am not aware of any really successful algorithms that have been implemented to interface with AMPL for the purpose of solving general integer linear programs, though I would be happy to hear of some.

 

The branch-and-bound implementation in CPLEX is itself an amalgam of heuristics, though in a framework that guarantees eventual determination of an optimal solution.  My first advice for trying to reduce solve times is to turn on search logging (directives mipdisplay and mipinterval) to get an idea why the procedure is taking so long.  It may be that the optimal solution is being found rather quickly and then a long time is being taken to prove optimality definitively, for example, in which case relaxing one of CPLEX's stopping criteria may suffice.  Other things that have worked for me include

 

   -- experimenting with CPLEX's many algorithmic options

   -- adding constraints ("cuts") to raise the computed bounds

   -- adding constraints to remove redundant solutions ("symmetries")

   -- breaking the problem into a series of simpler ones

 

Some study of integer programming and the branch-and-bound procedure is necessary to do these things effectively, though.  It is good to keep in mind that integer programming is a fundamentally hard problem class and that consequently, despite considerable progress in recent years, any optimizer is bound to solve some problems slowly without special effort on the part of the modeler.

 

Bob Fourer

4...@ampl.com

 

 

---

[Professor Alan Zinober]

Dear Robert

When using lpsolve and AMPL to solve an MIP or pure 0-1 probelm, is one
able to print out, at every p th iteration say, the objective function
value so that one can see what improvement is being made.

Also is one able to stop the iterations when one has achieved a good
improvement?


Is there any good program code available for algorithms like the Balas
impicit enumeration technique for 0-1 problems (or improved algorithms)?
Preferably in MATLAB, Scilab, C++ or similar language or ????

Alan Zinober (University of Sheffield, UK)

> 4...@ampl.com <mailto:4...@ampl.com>
>
>
>
>
>
> ------------------------------------------------------------------------
>
> *From:* Saqib Ilyas [mailto:msa...@gmail.com]
> *Sent:* Wednesday, December 02, 2009 9:09 AM
> *To:* am...@googlegroups.com
> *Subject:* [AMPL 3065] Non exact/Heuristic solvers

>
>
>
> Hi all
>
> My problem is pretty big (integer, linear), and CPLEX takes 6.5 hours
> to find the optimal solution. I am wondering if there are any non
> exact/heuristic solvers such as those based on Genetic Algorithms or
> Ants Colony Optimization that I can evaluate as a student and generate
> results. I found that Tomlab includes solvers based on genetic
> algorithms. However, when I invoke Tomlab on my problem, it gave a
> "starting point need to be modified" error.
>
> Thanks and best regards
>
> --
> Muhammad Saqib Ilyas
> PhD Student, Computer Science and Engineering
> Lahore University of Management Sciences
>
>
>

[cy]

Hi Muhammad,

I actually posted a similar question in this group regarding
metaheuristic solvers for AMPL:
http://groups.google.com.ph/group/ampl/browse_thread/thread/a5b3284b0ad2a36f?pli=1

I ended up using the open-source MILP solver CBC which can be
interfaced with AMPL. I still wanted to experiment with metaheuristics
but I didn't have enough time however.

[Saqib Ilyas]

Thanks very much. I guess I'll have to set up AMPL on Linux, then. I had ILOG licensed product for Windows in my University lab, so I was trying to stick to it. I hope to be able to find an unlimited open source ampl implementation (perhaps part of Coin-OR initiative) for Linux.

 

Thanks and best regards

--

You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To post to this group, send email to am...@googlegroups.com.
To unsubscribe from this group, send email to ampl+uns...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/ampl?hl=en.

[Paul]

Saqib Ilyas wrote:
> Thanks very much. I guess I'll have to set up AMPL on Linux, then. I had
> ILOG licensed product for Windows in my University lab, so I was trying to
> stick to it. I hope to be able to find an unlimited open source ampl
> implementation (perhaps part of Coin-OR initiative) for Linux.
>

I don't think COIN-OR has an AMPL clone. There is Zimpl (http://
zimpl.zib.de/), which is released under the GPL and implements a
subset of AMPL (but, AFAIK, not nearly all of AMPL).

/Paul

[ashutosh mahajan]

COIN-OR solvers can read AMPL files using the GLPK library. GLPK is
freely available and most linux distributions provide packages for
installing it. It works with most AMPL models but its functionality is
a strict subset of AMPL's.

ashutosh