News

  • 2009-05-03 - METSlib has a new home on  COIN-OR. No more development will take place on this site.
  • 2009-01-25 -  0.4.2 release fixes the mets::simple_tabu_list bug and adds a new  QAP solver in the  samples folder.
  • 2009-01-16 - I've found a nasty bug in the implementation of the mets::simple_tabu_list which required unusually long tabu lists to work. Now this is fixed in trunk (a new release is due soon). If you have code based on metslib you can wait for the new release or write me if you need a pre-release version and adjust the tenure of your list. A new sample on QAP is on svn.
  • 2008-12-23 - The first release of metslib has been downloaded 15 times in the first 5 days (not really exciting, but surely not bad for the first release of an Operations Research framework in C++).
  • 2008-12-17 - Version  0.4.1 with  sample code released. Please report any bug to the author. This release is intended to work on Linux, MacOS X or Cygwin.

METSlib Trac

METSlib is an OO (Object Oriented) metaheuristics optimization framework in C++.

Model and agorithms are modular: any search algorithm can be applied to the same model. On the other hand no assumption is made on the model, you can work on any problem type: timetabling, assignment problems, vehicle routing, bin-packing or any other.

Once you have implemented your model the framework allow you to test different TabuSearchStrategies or even different algorithms (Simulated Annealing or other local search based strategies) with a few lines of code.

METSlib hides the nuts and bolts of the algorithms from your code, this results in clearer code, easier to read: your search strategy can be better understood and modified with less effort. METSlib is  Open Source and is covered by the  GNU GPL v3 license. Other licenses can be considered by the author if needed.

METSlib implements the basics of some metaheuristics algorithm:

  • Random Restart Local Search
  • Variable Neighborhood Search
  • Iterated Local Search
  • Simulated Annealing (with linear, exponential and custom cooling schedule)
  • Last but not least, Tabu Search.

METSlib was tested with GCC 4.x, but written with portability in mind so, even if no build file for specific IDEs is provided, it should be simple to add one. The correct way to build the library is using the provided configure script (the script needs a Unix system or, on Windows, the  CygWin compatibility layer).

To use any algorithm you must implement an objective function, a neighborhood (move manager) and some moves.

If you choose Tabu Search metaheuristic you are free to use some of the already implemented termination criteria and tabu lists and aspiration criteria, or you can implement you own specialized versions.

If you opt for Simulated Annealing you can use one of the provided cooling schedules or implement your own.

The object oriented structure was carefully thought out to be highly reusable and the algorithm where reviewed by more than one person and more than one time.

This OO library was inspired by the  OTS library released by the Coin-OR project.

Class Diagram

http://code.100allora.it/metslib/attachment/wiki/WikiStart/mets-class-diagram.png?format=raw

Please note that there are still some little differences between the code and the class diagram (especially in the neightborhood/move_manager).

The classes coloured in yellow  1 2 3are the only one you need to subclass in a tipical implementation. You derive your own  solution class and than create one or more  move on that solution and one or more  move_manager to select the desired moves at each iteration of the algorithm.

Once you're done implementing your problem you can simply instantiate a solution, a move_manager, an  aspiration critera, a  tabu list and a  termination criteria to pass to the  tabu serach constructor. All the tabu search magic is done for you, but you can still customize it's behaviour implementing your own tabu_lists and aspiration or termination criteria.

If you want to react to some situations you can watch for the status of the algorithm after the termination criteria is met and decide what to do (you'll tipically end up with another, possibily different, tabu search iteration or the real termination of the algorithm).

You may now want to read QueensProblem page for quick introductory tutorial.

Complete API reference

API reference:

Sample programs

Success stories

METSlib is a slowly stabilizing and very young library. Few applications are known, if you use it and find it useful please report your success. This will be supporting for the author and useful to others to evaluate the library itself.

  • The author has written a fast timetabling application (can solve a problem with 50 hours a week, 34 resources meeting 376 times under 290 quality requirements in about 6 minutes on a Pentium IV processor). The delta feature of the METSlib moves allowed 1.394.000 evaluation/s and 88.906 moves/s.

Have you successfully used this framework? Please write me and I'll include your project in this section.

Contact Information

Report any bug to <mailto:mirko.maischberger@…>.

Download

The second public release of METSlib is  0.4.2. See  QAP sample to have a complete use case. You can also download the complete api reference as a  HTML archive or in  WinHelp CHM format.

If you use the library you should cite this page in your work:

Mirko Maischberger, "METSlib metaheuristic framework version 0.4.2". [online] Available  http://code.100allora.it/metslib, (the date you visited the site) 

% BibTeX entry. Remember to include \usepackage{hyperref} in yout .tex file
@misc{metslib2009,
  author={Mirko Maischberger},
  title={{METSlib} metaheuristic framework version 0.4.2},
  month={January},
  year={2009},
  howpublished = {\url{http://code.100allora.it/metslib}},
}

Also anonymous read access to svn is granted.

Need help? Willing to help?

Join the mailing list  http://lists.100allora.it/mailman/listinfo/metslib-dev and start asking!

Extra

http://code.100allora.it/pagerank/metslib.png

Attachments