论文标题
一个用于确切barycenters定价支持点的整数计划
An Integer Program for Pricing Support Points of Exact Barycenters
论文作者
论文摘要
在需要稀疏解决方案的应用中，对一组离散措施的精确重中心的计算引起了人们的关注，并评估通过近似算法和启发式方法返回的解决方案的质量。已知该任务因增长维度而是NP-HARD，即使在低维度中，由于与搜索稀疏解决方案相关的线性编程配方的指数缩放，在实践中也极具挑战性。 一种促进实用计算的常见方法是基于选择的小型，固定集的支持点的$ S_0 $的近似值，或者固定集合$ s^*_ 0 $从测量中分配质量的支持点组合的组合。通过线性和整数编程技术的组合，我们对整数程序进行建模，以计算其他组合，然后又添加到$ S^*_ 0 $或$ S_0 $时，可以更好地近似基础的确切的BaryCenter问题。该方法改善了经典列生成方法的可伸缩性：我们解决了一个二次尺寸的混合智能程序，而不是必须评估许多成本降低成本值的定价问题。该模型的属性以及实用的计算揭示了量身定制的分支和结合程序作为良好的解决方案策略。
The computation of exact barycenters for a set of discrete measures is of interest in applications where sparse solutions are desired, and to assess the quality of solutions returned by approximate algorithms and heuristics. The task is known to be NP-hard for growing dimension and, even in low dimensions, extremely challenging in practice due to an exponential scaling of the linear programming formulations associated with the search for sparse solutions. A common approach to facilitate practical computations is an approximation based on the choice of a small, fixed set $S_0$ of support points, or a fixed set $S^*_0$ of combinations of support points from the measures, that may be assigned mass. Through a combination of linear and integer programming techniques, we model an integer program to compute additional combinations, and in turn support points, that, when added to $S^*_0$ or $S_0$, allow for a better approximation of the underlying exact barycenter problem. The approach improves on the scalability of a classical column generation approach: instead of a pricing problem that has to evaluate exponentially many reduced cost values, we solve a mixed-integer program of quadratic size. The properties of the model, and practical computations, reveal a tailored branch-and-bound routine as a good solution strategy.
