An Integer Program for Pricing Support Points of Exact Barycenters

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 of combinations of support points from the measures that may be assigned mass. Through classic integer programming techniques, we model an integer program to compute additional combinations of support points that, when added to the fixed set, allow for a better approximation of the underlying exact barycenter problem. The approach improves on the scalability of previous column generation approaches: 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.

Funding: S. Borgwardt was supported by the Air Force Office of Scientific Research [Grant FA9550-21-1-0233], the National Science Foundation [Grant 2006183], Algorithmic Foundations, Division of Computing and Communication Foundations, and the Simons Foundation [Grant 524210].