Light speed computation of exact solutions to generic and to degenerate assignment problems

Speaker: Patrice Koehl, UC Davis

The linear assignment problem is a fundamental problem in combinatorial optimization with a wide range of applications, from operational research to data sciences. It consists of assigning agents" to tasks" on a one-to-one basis, while minimizing the total cost associated with the assignment. While many exact algorithms have been developed to identify such an optimal assignment, most of these methods are computationally prohibitive for large size problems. In this talk, I will describe a novel approach to solving the assignment problem using techniques adapted from statistical physics. In particular I will derive a strongly concave effective free energy function that captures the constraints of the assignment problem at a finite temperature. This free energy decreases monotonically as a function of ββ, the inverse of temperature, to the optimal assignment cost, providing a robust framework for temperature annealing. For large enough ββ values the exact solution to the generic assignment problem can be derived using a simple round-off to the nearest integer of the elements of the computed assignment matrix. I will also describe a provably convergent method to handle degenerate assignment problems. Finally, I will describe computer implementations of this framework that are optimized for parallel architectures, one based on CPU, the other based on GPU.

Zoom info available at https://sites.google.com/view/maddd

After the talk, we will do virtual tea/coffee get-together at https://gather.town/KOoFj0aKT5GkEj40/Alder-Room