Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by ...
详细信息
Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by a lack of efficient algorithms. Indeed, MOT in general requires exponential time in the number of marginals k and their support sizes n. This paper develops a general theory about what "structure" makes MOT solvable in poly(n, k) time. We develop a unified algorithmic framework for solving MOT in poly(n, k) time by characterizing the structure that different algorithms require in terms of simple variants of the dual feasibility oracle. This framework has several benefits. First, it enables us to show that the Sinkhorn algorithm, which is currently the most popular MOT algorithm, requires strictly more structure than other algorithms do to solve MOT in poly(n, k) time. Second, our framework makes it much simpler to develop poly(n, k) time algorithms for a given MOT problem. In particular, it is necessary and sufficient to (approximately) solve the dual feasibility oracle-which is much more amenable to standard algorithmic techniques. We illustrate this ease-ofuse by developing poly(n, k)-time algorithms for three general classes of MOT cost structures: (1) graphical structure;(2) set-optimization structure;and (3) low-rank plus sparse structure. For structure (1), we recover the known result that Sinkhorn has poly(n, k) runtime;moreover, we provide the first poly(n, k) time algorithms for computing solutions that are exact and sparse. For structures (2)-(3), we give the first poly(n, k) time algorithms, even for approximate computation. Together, these three structures encompass many-if not most-current applications of MOT.
This paper presents an interior point method for solving a bordered block-diagonal linear program which consists of a number of disjoint blocks coupled by a total of p variables and constraints. This structure include...
详细信息
This paper presents an interior point method for solving a bordered block-diagonal linear program which consists of a number of disjoint blocks coupled by a total of p variables and constraints. This structure includes the well-known block-angular and dual block-angular structures, as well as their special cases, such as staircase problems, generalized bounds, and multicommodity flows. When p is small relative to the total dimension of the problem, the method achieves a substantial speedup relative to other general-purpose methods.
A primal-dual path-following algorithm that applies directly to a linear program of the form, min{c(t)x\Ax = b, Hx less-than-or-equal-to u, x greater-than-or-equal-to 0, X is-an-element-of R(n)}, is presented. This al...
详细信息
A primal-dual path-following algorithm that applies directly to a linear program of the form, min{c(t)x\Ax = b, Hx less-than-or-equal-to u, x greater-than-or-equal-to 0, X is-an-element-of R(n)}, is presented. This algorithm explicitly handles upper bounds, generalized upper bounds, variable upper bounds, and block diagonal structure. We also show how the structure of time-staged problems and network flow problems can be exploited, especially on a parallel computer. Finally, using our algorithm, we obtain a complexity bound of 0(square-root n ds2 log(nkappa)) for transportation problems with s origins, d destinations (s < d), and n arcs, where kappa is the maximum absolute value of the input data.
This paper reports computational experience with the codesDecompsx andLift which are built on IBM's MPSX/370 LP software for large-scale structured *** is an implementation of the Dantzig-Wolfe decomposition algor...
详细信息
This paper reports computational experience with the codesDecompsx andLift which are built on IBM's MPSX/370 LP software for large-scale structured *** is an implementation of the Dantzig-Wolfe decomposition algorithm for block-angular LP'*** is an implementation of a nested decomposition algorithm for staircase and block-triangular LP's. A diverse collection of test problems drawn from real applications is used to test these codes, including multinational energy models and global economic models.
Since the original work of Dantzig and Wolfe in 1960, the idea of decomposition has persisted as an attractive approach to large-scale linear programming. However, empirical experience reported in the literature over ...
详细信息
Since the original work of Dantzig and Wolfe in 1960, the idea of decomposition has persisted as an attractive approach to large-scale linear programming. However, empirical experience reported in the literature over the years has not been encouraging enough to stimulate practical application. Recent experiments indicate that much improvement is possible through advanced implementations and careful selection of computational strategies. This paper describes such an effort based on state-of-the-art, modular linear programming software (IBM's MPSX/370).
暂无评论