An Interior Point–Inspired Algorithm for Linear Programs Arising in Discrete Optimal Transport

Filippo Zanetti () and Jacek Gondzio ()
Additional contact information
Filippo Zanetti: School of Mathematics and Maxwell Institute for Mathematical Sciences, The University of Edinburgh, Edinburgh EH9 3JZ, United Kingdom
Jacek Gondzio: School of Mathematics and Maxwell Institute for Mathematical Sciences, The University of Edinburgh, Edinburgh EH9 3JZ, United Kingdom

INFORMS Journal on Computing, 2023, vol. 35, issue 5, 1061-1078

Abstract: Discrete optimal transport problems give rise to very large linear programs (LPs) with a particular structure of the constraint matrix. In this paper, we present a hybrid algorithm that mixes an interior point method (IPM) and column generation, specialized for the LP originating from the Kantorovich optimal transport problem. Knowing that optimal solutions of such problems display a high degree of sparsity, we propose a column generation–like technique to force all intermediate iterates to be as sparse as possible. The algorithm is implemented nearly matrix-free. Indeed, most of the computations avoid forming the huge matrices involved and solve the Newton system using only a much smaller Schur complement of the normal equations. We prove theoretical results about the sparsity pattern of the optimal solution, exploiting the graph structure of the underlying problem. We use these results to mix iterative and direct linear solvers efficiently in a way that avoids producing preconditioners or factorizations with excessive fill-in and at the same time guaranteeing a low number of conjugate gradient iterations. We compare the proposed method with two state-of-the-art solvers and show that it can compete with the best network optimization tools in terms of computational time and memory use. We perform experiments with problems reaching more than four billion variables and demonstrate the robustness of the proposed method.

Keywords: optimal transport; interior point method; column generation; sparse approximation; chordal graphs (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0184 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:5:p:1061-1078

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().