Awesome
libmpopt – Library for Messaging Passing Optimization Techniques
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
- Maximum Weight Independent Set Problems
References
-
S. Haller, B. Savchynskyy.<br> “A Bregman-Sinkhorn Algorithm for the Maximum Weight Independent Set Problem”.<br> arXiv Pre-Print 2024. [PDF] [Website & Paper Specific Code]
-
S. Haller, L. Feineis, L. Hutschenreiter, F. Bernard, C. Rother, D. Kainmüller, P. Swoboda, B. Savchynskyy.<br> “A Comparative Study of Graph Matching Algorithms in Computer Vision”.<br> ECCV 2022 [PDF] [Website]
-
L. Hutschenreiter, S. Haller, L. Feineis, C. Rother, D. Kainmüller, B. Savchynskyy.<br> “Fusion Moves for Graph Matching”.<br> ICCV 2021. [PDF]
-
S. Haller, M. Prakash, L. Hutschenreiter, T. Pietzsch, C. Rother, F. Jug, P. Swoboda, B. Savchynskyy.<br> “A Primal-Dual Solver for Large-Scale Tracking-by-Assignment”.<br> AISTATS 2020. [pdf]
-
V. Kolmogorov.<br> “Convergent tree-reweighted message passing for energy minimization”.<br> PAMI 2006. [pdf]
Setting up a Development Environment
Using a Development Container via Docker/Podman
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 podman
To 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-dev-env debug
# or alternatively for a release build:
./scripts/setup-dev-env release
After 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.
Using Your Host System
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 swig
There 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 release
The 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
.
Installing into an existing Python virtual environment (venv)
When developing Python projects that use libmpopt as a dependency it is
convenient to directly install the project into an virtual environment.
Here we will use /tmp/venv
as the base path of the virtual environment, but
every occurrence can obviously be replaced by the real path.
The assumption is that a virtual environment was created with the following command:
python3 -m venv /tmp/venv
To activate the virtual environment in the bash shell we can use:
source /tmp/venv/bin/activate
After this command the virtual environment is active and the shell prompt
should have updated to indicate this fact. Inside the environment we can use
pip
to install necessary dependencies, e.g. pip install numpy
. Everything
will be installed locally into the /tmp/venv
directory.
To install libmpopt, enter the source directory, ensure that the virtual environment is active and then run:
./scripts/install-into-venv
The script will automatically determine the location of the active virtual
environment and install all files at the correct location. With the virtual
environment being active commands like qap_dd
etc. should work. Additional
Python should be able to execute import mpopt
correctly. Therefore, any
Python script is able to use the mpopt libary as long as the virtual
environment is active.
Building and Installing the Software Manually
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 swig
Building is done by:
mkdir /path/to/build/directory
meson setup /path/to/build/directory
ninja -C /path/to/build/directory
Installation is done by:
ninja -C /path/to/build/directory install