|Version 29 (modified by mirko, 3 years ago) (diff)|
Welcome to the METSlib tabu search framework home page
Note that these project webpages are based on Wiki, which allows web users to modify the content to correct typos, add information, or share their experience and tips with other users. You are welcome to contribute to these project webpages. To edit these pages or submit a ticket you must first register and login.
METSlib is an OO (Object Oriented) metaheuristics modeling framework and optimization toolkit in C++.
Model and algorithms 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 and so on.
Once you have implemented your model in the problem framework, the library makes easy testing different Tabu Search strategies or even different algorithms (Simulated Annealing or other local search based algorithms) with a few lines of code.
METSlib hides the nuts and bolts of the algorithms from your code, you are only supposed to code the problem logic, not the search algorithm, this results in clearer code, which is also easier to read: your search strategy can be better understood and modified with less effort. The toolkit implements the basics of some metaheuristic algorithms:
- Simple local search
- Simulated Annealing (with linear, exponential and custom cooling schedule)
- Last but not least, Tabu Search.
It's really easy to code other metaheuristics based on the previous ones:
- Random Restart Local Search
- Variable Neighborhood Search
- Iterated Local Search
METSlib was tested with GCC 4.3.x and 4.4.x, but written with portability in mind, so, even if no build file for specific IDEs are provided, it should be simple to add one: the only requirement is a fairly recent C++ compiler with support for the TR1 extension. The correct way to build the library is to use 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 exploration strategy (move manager) and the actual moves.
If you choose Tabu Search metaheuristic you are free to use some of the already implemented termination criteria, 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.
This OO library was inspired by the OTS library released by the Coin-OR project. It was started by me in 2006 during the period of my master thesis with invaluable support from people of the Global Optimization Laboratory, and refined in the following years.
Please note that this is still alpha code, you are welcome to use it for your own project, but be aware that interfaces are still subject to changes and that some of the things you could want may not be there (you can surely code them yourself and send patches). On the other hand the object-oriented structure was carefully thought out to be reusable and the algorithm were reviewed by more than one person and more than one time.
METSlib is Open Source and is covered by the GNU GPL v3 license or, at you option, by the CPL. Other licenses can be considered by the author if needed. Feel free to join the mailing list, add tickets (you need to register first), send hints, and contribution.
Getting METSlib releases
Version 0.4.3 is the first public release of METSlib on COIN-OR.
- download sources with docs
- download Examples (note: examples are hugly and somewhat incorrect, please wait 0.4.4 version or see trunk)
- download documentation only
- online documentation
This version has been tested on Ubuntu 8.04 and 9.04, Debian Lenny, OpenSolaris 2009.06, and Windows/Cygwin 1.7beta. Also an experimental Visual C++ Express 2008 project file is provided.
Getting METSlib (via svn)
- You can get the latest METSlib sources and examples using the following subversion commands:
svn co https://projects.coin-or.org/svn/metslib/trunk/ metslib-trunk svn co https://projects.coin-or.org/svn/metslib/Examples/trunk/ Examples-trunk
- Are you using METSlib for your project? I'll be pleased to know what you are using METSlib for and to have your feedback. Write me at <mirko (dot) maischberger (at) gmail (dot) com>.
- An IntroductionToMetslib
- A short tabu search coding tutorial
- 0.4.3 API Reference Manual
- Compiling on OpenSolaris
- Compiling with VisualStudioExpress
- Solving QuadraticAssignmentProblem with a naive strategy.
- If you still need help, please join the mailing list.
- Mirko Maischberger <mirko.maischberger@…> (register and login to view)