Differentiable Extensions with Rounding Guarantees for Combinatorial Optimization over Permutations and Trees

Continuously extending combinatorial optimization objectives is a powerful technique commonly applied to the optimization of set functions. However, few such methods exist for extending functions on permutations, despite the fact that many combinatorial optimization problems, such as the traveling salesperson problem (TSP), are inherently optimization over permutations.

In ongoing work, PI Wang and her students develop Birkhoff extension, a differentiable continuous polytime-computable extension of any real-valued function on permutations to doubly stochastic matrices. Their approach is based on Birkhoff decomposition, which allows construction of an extension with values that are convex combinations of the objective's values at permutations. Most interestingly, they show that any solution to the extension can be rounded, in polynomial time, to a permutation without increasing the function value. This implies that an optimal of the continuous extension will lead to an optimal in the discrete case. Furthermore, Birkhoff extension can be biased towards an approximate solution so that it always yields a solution no worse than the approximate solution. Consequently, this extension can be readily combined with existing optimization approaches to offer improvements. An interesting next step is to combine this extension with neural networks so as to solve a family of combinatorial optimization problems (e.g., TSP, Minimum Steiner tree) in a data-driven manner.