A column generation approach to the discrete barycenter problem
A column generation approach to the discrete barycenter problem
复制标题
离散重心问题的列生成方法
DOI：
10.1016/j.disopt.2021.100674
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Patterson, Stephan
中科院分区：
文献类型：
--
作者：
Borgwardt, Steffen;Patterson, Stephan
离散Wasserstein重心问题是一组离散概率测度的最小代价质量传递问题。虽然通过线性规划可以计算出精确的重心，但潜在的线性规划可能非常大。对于最坏情况输入，最著名的线性规划公式是变量数量呈指数增长，但约束数量很少，这使其成为列生成的有趣候选。在本文中，我们设计并研究了两种列生成策略：一种是基于简化成本计算的自然列生成策略，另一种是基于dantzigg - wolfe分解的列生成策略。对于后者，我们产生了有效可解的子问题，即经典运输问题形式的定价问题。这两种策略从初始可行解的有效计算开始。虽然约束的结构导致计算所有剩余变量的成本降低，但这两种方法在速度上都可能优于使用完整程序的计算，并且在内存需求方面明显优于使用完整程序的计算。在我们的计算实验中，我们证明，根据输入，任何一种策略都可以成为最佳选择。
The discrete Wasserstein barycenter problem is a minimum-cost mass transport problem for a set of discrete probability measures. Although an exact barycenter is computable through linear programming, the underlying linear program can be extremely large. For worst-case input, a best known linear programming formulation is exponential in the number of variables, but has a low number of constraints, making it an interesting candidate for column generation.In this paper, we devise and study two column generation strategies: a natural one based on a simplified computation of reduced costs, and one through a Dantzig–Wolfe decomposition. For the latter, we produce efficiently solvable subproblems, namely, a pricing problem in the form of a classical transportation problem. The two strategies begin with an efficient computation of an initial feasible solution. While the structure of the constraints leads to the computation of the reduced costs of all remaining variables for setup, both approaches may outperform a computation using the full program in speed, and dramatically so in memory requirement. In our computational experiments, we exhibit that, depending on the input, either strategy can become a best choice.
登录
查看更多内容
DOI：
--
发表时间：
2019-09
期刊：
J. Mach. Learn. Res.
影响因子：
--
作者：
Tianyi Lin;Nhat Ho;Marco Cuturi;Michael I. Jordan
通讯作者：
Tianyi Lin;Nhat Ho;Marco Cuturi;Michael I. Jordan
DOI：
10.1051/m2an/2015033
发表时间：
2015-11-01
期刊：
ESAIM-MATHEMATICAL MODELLING AND NUMERICAL ANALYSIS-MODELISATION MATHEMATIQUE ET ANALYSE NUMERIQUE
影响因子：
--
作者：
Carlier, Guillaume;Oberman, Adam;Oudet, Edouard
通讯作者：
Oudet, Edouard
Wasserstein 重心是 NP 难计算的
DOI：
10.1137/21m1390062
发表时间：
2021
期刊：
ArXiv
影响因子：
--
作者：
Jason M. Altschuler;Enric Boix
通讯作者：
Enric Boix
自然图像的重心 - 用于图像变形的约束 Wasserstein 重心
DOI：
10.1109/cvpr42600.2020.00793
发表时间：
2019
期刊：
2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)
影响因子：
--
作者：
Dror Simon;Aviad Aberdam
通讯作者：
Aviad Aberdam
DOI：
10.1287/ijoo.2019.0020
发表时间：
2018
期刊：
INFORMS J. Optim.
影响因子：
--
作者：
S. Borgwardt;Stephan Patterson
通讯作者：
Stephan Patterson