Improved Linear Programs for Discrete Barycenters
Improved Linear Programs for Discrete Barycenters
复制标题
离散重心的改进线性程序
DOI：
10.1287/ijoo.2019.0020
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Stephan Patterson
中科院分区：
文献类型：
--
作者：
S. Borgwardt;Stephan Patterson
离散重心是一组离散测量的质量运输问题的最佳解决方案。它们出现在运筹学和统计学的应用中。最著名的算法基于线性规划，但这些程序的测量数量呈指数级增长，这使得它们在实际用途中难以实现。
在本文中，我们改进了这些算法。首先，通过使用最优条件来限制搜索空间，我们提供了一个更好的线性程序，可以显着减少变量的数量。其次，我们回顾文献中的一种证明方法，该方法适用于尚未考虑用于计算的线性程序。我们证明，对于一般位置的数据来说，第二种公式是可行的，并且可以说是首选方法。第三，然后我们将这两个程序组合成一个混合模型，该模型保留了部分结构化数据的两种公式的最佳属性。
然后，我们通过理论分析和计算实验来研究模型。我们既考虑构建模型的难度又考虑其实际解决方案。在此过程中，我们证明每个改进的线性程序都成为不同底层结构数据的最佳首选方法。
Discrete barycenters are the optimal solutions to mass transport problems for a set of discrete measures. They arise in applications of operations research and statistics. The best known algorithms are based on linear programming, but these programs scale exponentially in the number of measures, making them prohibitive for practical purposes.
In this paper, we improve on these algorithms. First, by using the optimality conditions to restrict the search space, we provide a better linear program that reduces the number of variables dramatically. Second, we recall a proof method from the literature, which lends itself to a linear program that has not been considered for computations. We exhibit that this second formulation is a viable, and arguably the go-to approach, for data in general position. Third, we then combine the two programs into a single hybrid model that retains the best properties of both formulations for partially structured data.
We then study the models through both a theoretical analysis and computational experiments. We consider both the hardness of constructing the models and their actual solution. In doing so, we exhibit that each of the improved linear programs becomes the best, go-to approach for data of different underlying structure.