Branched Optimal Transport (BOT)

This repository contains the code supplementary to the accepted NeurIPS 2022 paper Theory and Approximate Solvers for Branched Optimal Transport with Multiple Sources.

Here, we provide code for the following algorithms and experiments:

1. the numerical scheme to systematically check inequality Γ₂ (Sect. E.1.4),
2. the geometric construction algorithm for solutions with optimal geometry (Sect. 3.2),
3. the numerical BP optimization routine (Sect. 6.1),
4. the Brute-force solver for topology optimization (Sect. 6.2),
5. the heuristic for the topology optimization (Sect. 6.2).

For instructions on setting up an anaconda environment see environment.txt.
To get started check out the tutorials for a step by step introduction to the repo.

Introduction to BOT

BOT is an NP-hard optimization problem. Given a set of sources (below in red) and sinks (below in blue), the objective is to optimize a transportation network with respect to the following cost function:

where α is a parameter between 0 and 1. It determines how much more efficient it is to transport mass with nearby destinations along the same route. The mathematical reason is the subadditivity of (m₂ + m₂)^α < m₁^α + m₂^α. The smaller α the more branching is observed in optimal solutions. The case of α=0 corresponds to the Euclidean Steiner Tree Problem. For α=1, BOT relaxes to the efficiently solvable problem of Optimal Transport (no more branching). The BOT optimization can be split into a convex geometric optimization of the branching point positions and a combinatorial optimization of the topology.

1) Inequality check

By proving the inequality Γ₂, one can show that degree-4 branchings in a BOT solution are never globally optimal.
The white region is the only region which could not be ruled out analytically and which is therefore handled numerically.
The code can be found here.

2) Geometric construction of solutions with optimal geometry for a given topology

The presented geometric construction with so-called pivot points and pivot circles was generalized in the paper to be applicable to BOT problems with multiple sources. The construction is very efficient, but works only if the optimal solution does not contain any edges contractions. The algorithm is only applicable to BOT problems in the Euclidean plane.
More examples can be found here.

3) Numerical optimization of the BP configuration for a given topology

This numerical optimization routine is an effective algorithm to optimize the BP configuration for a given tree topology. It is applicable in two- and higher-dimensional Euclidean spaces for all tree topologies. It is the basis of the heuristic which addresses the combinatorics of the BOT topology (see below).
The respective code can be found here. In notebooks please find the runtime analysis, and the scaling analysis.

4) Brute-force topology optimization

The number of possible tree topologies for BOT grows super-exponentially with the problem size. For 9 terminals, there exist already 135135 distinct topologies. Trying them all out is computationally very costly. A ground truth example and the histogram of all costs of the different topologies is shown above. For larger problems all brute-force approaches become infeasible.
More ground truth examples from brute-force search can be found here.

5) Heuristic for topology optimization

In notebooks please find the comparison of the greedy heuristic to brute-force solutions, number of iterations analysis, influence of the kernel width and a topology optimization step by step.