PAAL logo

PAAL

Practical Approximation Algorithms Library


View DocumentationExamples and Proofs

DownloadWindows/Linux sources

Primary Developer: Piotr Wygocki

Introduction

The PAAL is an open source, a header-only, generic library consisting of approximation algorithms, data structures and several complete solutions for the various optimization problems. The PAAL is implemented taking advantage of the new features of C++ introduced in the C++14 standard, which in many cases simplify greatly creation of generic code.

General Design

The algorithms are written as template functions in STL-style. The major change is, that we support ranges instead of iterators. Usually algorithms can be customized or extended, as they support many different arguments. Besides, the algorithms, the library contains many useful data-structures. Our data structures introduce useful and interesting higher level concepts, e.g., Metric or Cycle.

Besides standalone algorithms, the library contains frameworks which supports solving general optimization methods like local search or iterative rounding. The functional arguments of these frameworks are usually wrapped using Components class (see Components), which allows to specify named arguments. In such case the algorithm is called as follows:

algorithm(ProblemDescription, Components)

For each concept our library delivers the default implementations of components. Of course the user is allowed to replace each component. Consider for example the local search framework, where the user can can easily swap the implementation of the GetMoves procedure to provide his own way of searching the neighborhood. Also note that the same components, that are used by local search can be used in the simulated annealing algorithm. Similarly, if the user wants to swap the metric implementation to use specific properties of his topology, this is not a problem at all!

Download

git clone --recursive http://siekiera.mimuw.edu.pl:8082/paal

Build

PAAL is mainly a header only library. If you use linear programming you must link your executable against glpk.

Some algorithms have additional binary programs, to build them run:

mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make

In order to additionally build tests or examples add parameters -DWITH_TESTS=1 -DWITH_EXAMPLES=1 parameters to cmake call.

Platforms

Currently the library compiles on the gcc 4.8.4 and clang 3.5. On the Visual Studio 2015 preview only binaries are guarantied to compile.

License

The library is released under Boost Software License , which encourages both commercial and non-commercial use.

Contact

In case of any questions / suggestions / pull requests / contribution please contact Piotr Wygocki (wygos at mimuw.edu.pl).