This repository contains code for optimizing combinatorial optimization problems by message passing techniques. The solvers work on the Lagrange decomposition of the specific optimization problem and monotonously improve the bound of the Lagrange dual function. A solution of the original primal problem is computed by rounding strategies.
Supported combinatorial optimization problems:
- Graphical Models (by reimplementing the TRW-S technique, see references)
- Cell Tracking Problems
- Quadratic Assignment Problems
L. Hutschenreiter, S. Haller, L. Feineis, C. Rother, D. Kainmüller, B. Savchynskyy.
“Fusion Moves for Graph Matching”.
arXiv preprint arXiv:2101.12085. [pdf]
S. Haller, M. Prakash, L. Hutschenreiter, T. Pietzsch, C. Rother, F. Jug, P. Swoboda, B. Savchynskyy.
“A Primal-Dual Solver for Large-Scale Tracking-by-Assignment”.
AISTATS 2020. [pdf]
V. Kolmogorov.
“Convergent tree-reweighted message passing for energy minimization”.
PAMI 2006. [pdf]
The easiest way to get started is by using Docker or podman. Usage of podman is recommended as it allows to create root-less containers. The advantage is that with podman the local user is able to create a container that contains the full development environment without requiring root access.
On Ubuntu 20.10 and later you can install podman via:
sudo apt update && sudo apt install podmanTo spawn a container containing the development environment you can simply run the following command in the root of the repository:
# for a debug build:
./scripts/setup-local-dev-env debug
# or alternatively for a release build:
./scripts/setup-local-dev-env releaseAfter building the container image and spawning a new container instance you
will be greeted by a shell inside the container. The software is already built
and installed. You can use it by executing gm_uai, ct_jug, qap_dd, etc.
If you want to set up the development environment on your host system you should first install the necessary dependencies. On Ubuntu you can install them by issuing:
sudo apt install build-essential curl meson ninja-build pkg-config python3 python3-dev python3-numpy swigThere is a helper script to automate the process of creating a development environment. You can can execute the following command from the root of the repository:
# for debug build:
./scripts/setup-local-dev-env debug
# alternatively for release build:
./scripts/setup-local-dev-env releaseThe script will create a temporary directory, build and install some
dependencies to the temporary install root and build the project in the
temporary directory. Note that the script aims to not change or install
software on your host system. Everything is done in temporary directories that
are automatically deleted when you leave the development environment. If the
scripts finishes successfully, you will be greeted by a shell in the build
directory of libmpopt. Everything is installed to a temporary install prefix
which is automatically added to your $PATH environment variable. You can run
the software by executing gm_uai, ct_jug, qap_dd, etc.
After making changes to the source code run ninja install in the shell of the
development environment.
If you want to switch between debug or release mode you can execute meson configure -Dbuildtype=debug or meson configure -Dbuildtype=release followed
by ninja install.
You will need build tools like meson, ninja, a C++17 compatible compiler, Python and the SWIG binding generator.
The following command should install all necessary dependencies on an Ubuntu machine:
sudo apt install build-essential curl meson ninja-build pkg-config python3 python3-dev python3-numpy swigBuilding is done by:
mkdir /path/to/build/directory
meson setup /path/to/build/directory
ninja -C /path/to/build/directoryInstallation is done by:
ninja -C /path/to/build/directory install