OTToolbox Documentation

Introduction About System Requirements Disclaimer & License Contact Installation Overview Compilation Import in Python Examples References

Introduction

About

OTToolbox is a toolbox for numerical optimal transport for Python 3 with numpy and scipy. The front end is written in Python 3 and several functions are provided by shared c++ libraries.
It provides various implementations for solving discrete optimal transport problems, via the linear programming formulation due to Kantorovich. It includes a naive dense solver for reference and convenience. However, currently the main functionality is the implementation of the sparse multi-scale solver described in [Schmitzer 2015].

In this early stage there is no extensive documentation available. It is recommended to try to complete the installation and then look at some of the example files.

Note that this is highly experimental software. It does virtually no safety checks on the users input data and will likely crash your Python session if invalid data is provided. See also Disclaimer & License.

System Requirements

Currently the toolbox is in a very early beta stage and no systematic testing for system compatibility has been performed.
So far it has been tested with:

Ubuntu 12.04 and 14.04, Python 3.4.2 and 3.4.3, numpy 1.9.2, scipy 0.15.1, g++ 4.6.3 and 4.8.4
OS X 10.9.5, Python 3.4.3, numpy 1.9.0, scipy 0.14.0

Due to the way communication between Python and C++ is handled, it is likely that the toolbox will only work on 64bit operating systems.
If you are new to Python we recommend the Anaconda distribution which provides a convenient way to set up a working Python environment. Moreover, while the toolbox can be operated from standard Python scripts, we highly recommend using jupyter for interactive testing and development.

In addition, the toolbox requires an external linear program solver. Currently, interfaces are provided for the following solvers:

ILOG CPLEX Optimization Studio (tested with versions 12.5 and 12.6.1). Online documentation. For academic researchers CPLEX is available under the IBM Academic Initiative.
LEMON Graph Library 1.3.1

These external libraries cannot be directly provided with the toolbox. The user is kindly asked to obtain either of the two by themselves.

Disclaimer & License

This toolbox is prototypical software, developed as part of ongoing research on efficient algorithms and should be considered experimental. It is distributed such that other researchers can test and reproduce published results as well as extend it.
It comes without any guarantees or warranty. Use at your own risk.

So far, no licence for distribution has been chosen. You are free to modify all components of the toolbox but are asked not to redistribute any part of it without written permission by the original toolbox author, see Contact.

Contact

The toolbox is developed by Bernhard Schmitzer, currently a post-doctoral reasearcher at CEREMADE, Université Paris-Dauphine (website). Feedback on how to make the toolbox more user-friendly, about bugs, successful installation on a new system configuration or requests for additional features is much appreciated.

Installation

Overview

Installation consists of two steps: compiling the c++ libraries and importing the front end modules into Python. Currently both steps require a little manual interaction by the user.

Compilation

Open the file Solvers/compile_constants.sh with a text editor. Find the sections for the CPLEX or Lemon specific settings and adjust the location to the libraries on your system. At least one must be provided to use the toolbox. Be sure to remove the comments in front of the lines that specify the include and linker information!
Build the core components of the toolbox by executing the script compile_shortcut.sh from a terminal. Check for possible compiler and linker errors.
Depending on which LP solver you want to use, run the corresponding compilation script: compile_cplex.sh for CPLEX and compile_lemon.sh for LEMON. Again, carefully check the output for compiler and linker errors.

Import in Python

After compilation it is important that Python knows where to look for the toolbox. This is achieved by the following commands (run within Python), where you must replace XXXX by the appropriate location of the toolbox on your system. The directory /XXXX/OTToolbox_v0.1.0/ should contain the file CClasses.py.

import sys
sys.path.append("/XXXX/OTToolbox_v0.1.0/")

Note: In the example files, this is already done via relative paths, see the file Examples/lib/header_rootdir.py for details.

After this, the various modules of the toolbox can be imported in Python for example via:

import Solvers.OT_CPLEX as OT_CPLEX
import Solvers.OT_Lemon as OT_Lemon

import OTTools
import OTTools.HierarchicalPartition as HierarchicalPartition

import Solvers.ShortCutSolver as ShortCutSolver
import Solvers.ShortCutSolver_CPLEX as ShortCutSolver_CPLEX
import Solvers.ShortCutSolver_Lemon as ShortCutSolver_Lemon
import Solvers.CostFunctionComputation as SolverCFC

We refer to the section on Examples to find out what the various modules do.

Examples

In the directory Examples/ some example files are provided. Most of them are IPython / jupyter notebooks (see Requirements), which allow for a more interactive demonstration with embedded plots. All examples contain some explaining comments with the code.

Filename	Description
Example-Dense-01-CPLEX.py	Very simple test file which solves a dense transport problem with CPLEX. Can be used to verify whether installation worked properly.
Example-Dense-01-Lemon.py	Very simple test file which solves a dense transport problem with LEMON. Can be used to verify whether installation worked properly. Note: The LEMON solver is a bit more elaborate to set up than the CPLEX solver, since marginals and cost function must be truncated to a discrete grid. Therefore most further examples use the CPLEX solver. Should CPLEX not be available to you, this script explains how to set up problems with LEMON and how to adapt other scripts if required. For the set-up of the ShortCut-Solver with Lemon see also Example-ShortCutSolver-01-Basic-Lemon.ipynb.
Example-ShortCutSolver-01-Basic-CPLEX.ipynb	Basic demonstration of the ShortCut-Solver on a small test problem, comparison with the naive dense solver, using dense data structures. Uses CPLEX as internal LP solver.
Example-ShortCutSolver-01-Basic-Lemon.ipynb	Basic demonstration of the ShortCut-Solver on a small test problem, comparison with the naive dense solver, using dense data structures. Uses Lemon as internal LP solver.
Example-ShortCutSolver-02-SparseDataStructures.ipynb	Solving a larger test problem with the ShortCut-Solver on sparse data structures. Comparison to the dense solver is no longer possible.
Example-ShortCutSolver-03-PaddingTest.ipynb	The construction of shielding neighourboods is compared with the padding method proposed in [Oberman & Ruan 2015]. It is shown on an extreme test problem that the padding method will not always provide a globally optimal result.

References

[Schmitzer 2015] B. Schmitzer: A Sparse Multi-Scale Algorithm for Dense Optimal Transport, http://arxiv.org/abs/1510.05466

[Oberman & Ruan 2015] A. Oberman and Y. Ruan: An efficient linear programming method for Optimal Transportation, http://arxiv.org/abs/1509.03668

OTToolbox_v0.0.1 : Documentation

Table of Contents