looking for metaheuristic solvers for AMPL

[cy]

hi all,

i'd just like to ask if there are available metaheuristic (e.g.
genetic algorithms, simulated annealing) solvers for AMPL. i'm
interested in comparing the performance of exact methods (e.g. branch
and bound) vs. metaheuristics for some test problems (e.g. MIPLIB).

thanks,
cy

[mitte...@asu.edu]

AMPL is a modeling language not a programming language

[cy]

yes, what i mean is if there are solvers for AMPL which implement
metaheuristic algorithms.
for example, we can have the following set of command for AMPL:

********
model model1.mod;
data data1.dat;
option solver cplex;
option cplex_options... #experiment with cplex options here
solve;

...
option solver metaheuristic_solver;
option meta_options... #experiment with metaheuristic options here
solve;
********

what i'd like to do is compare the performance (e.g. objective
function values after a certain time limit) of branch and bound vs.
metaheuristics under the AMPL modeling language.

thanks,
cyrus

[Ali Baharev]

Hi Cyrus,

I have a limited experience with metaheuristics. Genetic algorithms
almost always have to be tailored to the the problem. In other words
you have to create a problem specific representation usually using a
class library (e.g. in C++), based on the physical background of the
problem at hand. The MPS files in the MIPLIB library are not suitable
for preparing a problem specific representation, you have no
information about the physical background of the problems.

AMPL is a general purpose tool and requires no problem specific adjustments.

That's what he meant by saying "AMPL is a modeling language not a
programming language".

If you have any questions feel free to contact me.

Good luck,

Ali

[Robert Fourer]

At the NEOS Server site you will find references to AMPL interfaces for some
heuristic solvers; see the entries for ACRS, ASA, PGAPack, and Pswarm under
Global Optimization at neos.mcs.anl.gov/neos/solvers. Except for ACRS they only
handle problems with simple bound constraints, however.

As Ali Baharev has suggested, metaheuristics have seen their greatest success in
situations where they are tailored to very specific problem types. For
arbitrary MIP problems, general-purpose branch-and-bound software has been the
approach that has mainly been pursued. Note however that heuristics for
deducing integer solutions from fractional ones are an important component of
any good branch-and-bound code, and many of the criteria for node and branch
selection are essentially heuristics, too.

Bob Fourer
4...@ampl.com

[A. Ismael F. Vaz]

Just to make an additional note. PSwarm is able to handle linear constraints
(see www.norg.uminho.pt/aivaz/pswarm). ASA is able to handle nonlinear
constraints by using an infinity barrier penalty function (the penalty
function will be +infty for unfeasible point). Note that ASA approach is a
very rude approach to nonlinear constraints and the results may not be
satisfactory.

One thing is for sure, none of the mentioned solver are able to handle
integer variables and therefore they cannot be used for MIP problems.

Ismael Vaz
www.norg.uminho.pt/aivaz

[cy]

Hi all,

Thanks for all the input. I guess I would stick with branch and bound
rather than experiment with metaheuristics. I don't have much
experience in programming, and the AMPL modeling language appears more
intuitive for me. It seems that there are no standard modeling
language for metaheuristics.

By the way, while searching for metaheuristic solvers for AMPL, I came
across the following articles:
http://jonah.cs.elon.edu/dpowell2/Courses/GMMaterials/GECCO-2007/GECCO-2007.ppt
http://portal.acm.org/citation.cfm?id=1277372

These articles detail coupling of the AMPL modeling language and the
NSGA-II algorithm. I don't know if this solver is publicly available
though.

Thanks,
Cyrus