Practical Approximation Algorithms Library
View DocumentationExamples and Proofs
Primary Developer: Piotr Wygocki
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.
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!
git clone --recursive http://siekiera.mimuw.edu.pl:8082/paal
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.
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.
The library is released under Boost Software License , which encourages both commercial and non-commercial use.
In case of any questions / suggestions / pull requests / contribution please contact Piotr Wygocki (wygos at mimuw.edu.pl).