# Genetic column generation: Fast computation of high-dimensional multi-marginal optimal transport problems

arXiv: https://arxiv.org/abs/2103.12624 · HTML: https://mlsanity.com/paper/2103.12624/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 23 Mar 2021.

## Builds on (most cited first, 11 of 11)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Wasserstein GAN](https://mlsanity.com/paper/1701.07875/) (2017)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [A Sparse Multi-Scale Algorithm for Dense Optimal Transport](https://mlsanity.com/paper/1510.05466/) (2015)
- [A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation](https://mlsanity.com/paper/2101.05380/) (2021)
- [Hardness results for Multimarginal Optimal Transport problems](https://mlsanity.com/paper/2012.05398/) (2020)
- [Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm](https://mlsanity.com/paper/1710.08234/) (2017)
- [Domain decomposition for entropy regularized optimal transport](https://mlsanity.com/paper/2001.10986/) (2020)
- [A simple counterexample to the Monge ansatz in multi-marginal optimal transport, convex geometry of the set of Kantorovich plans, and the Frenkel-Kontorova model](https://mlsanity.com/paper/1808.04318/) (2018)
- [Convex relaxation approaches for strictly correlated density functional theory](https://mlsanity.com/paper/1808.04496/) (2018)

## Built on by (most cited first, 3 of 3)

- [The GenCol algorithm for high-dimensional optimal transport: general formulation and application to barycenters and Wasserstein splines](https://mlsanity.com/paper/2209.09081/) (2022)
- [Genetic Column Generation for Computing Lower Bounds for Adversarial Classification](https://mlsanity.com/paper/2406.08331/) (2024)
- [Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions](https://mlsanity.com/paper/2609.13010/) (2026)

## Abstract (arXiv)

We introduce a simple, accurate, and extremely efficient method for numerically solving the multi-marginal optimal transport (MMOT) problems arising in density functional theory. The method relies on (i) the sparsity of optimal plans [for N marginals discretized by ℓ gridpoints each, general Kantorovich plans require ℓN gridpoints but the support of optimizers is of size O(ℓ· N) [FV18]], (ii) the method of column generation (CG) from discrete optimization which to our knowledge has not hitherto been used in MMOT, and (iii) ideas from machine learning. The well-known bottleneck in CG consists in generating new candidate columns efficiently; we prove that in our context, finding the best new column is an NP-complete problem. To overcome this bottleneck we use a genetic learning method tailormade for MMOT in which the dual state within CG plays the role of an "adversary", in loose similarity to Wasserstein GANs. On a sequence of benchmark problems with up to 120 gridpoints and up to 30 marginals, our method always found the exact optimizers. Moreover, empirically the number of computational steps needed to find them appears to scale only polynomially when both N and ℓ are simultaneously increased (while keeping their ratio fixed to mimic a thermodynamic limit of the particle system).