Fast computation of exact solutions of generic and degenerate assignment problems
Fast computation of exact solutions of generic and degenerate assignment problems
复制标题
快速计算一般和退化分配问题的精确解
DOI：
10.1103/physreve.103.042101
复制
发表时间：
2021
影响因子：
2.4
通讯作者：
Orland, Henri
中科院分区：
文献类型：
--
作者：
Koehl, Patrice;Orland, Henri
线性分配问题是组合优化中的一个基本问题，具有广泛的应用，从运筹学到数据科学。它包括在一对一的基础上将“代理”分配给“任务”，同时最小化与分配相关的总成本。虽然已经开发了许多精确的算法来确定这样的最佳分配，但这些方法中的大多数对于大规模问题来说在计算上都是禁止的。在本文中，我们提出了另一种方法来解决分配问题，采用统计物理学的技术。我们的第一个贡献是充分描述这种形式主义，包括其主要主张的所有证据。特别是，我们推导出一个强凹有效的自由能函数，捕捉在有限温度下的分配问题的约束。我们证明，这种自由能单调下降的函数，温度的倒数，最佳分配成本，温度退火提供了一个强大的框架。我们还证明了，对于足够大的值的精确解的一般分配问题可以推导出使用简单的舍入到最近的整数元素的计算分配矩阵。我们的第二个贡献是得到一个可证明收敛的方法来处理退化的分配问题，这些问题的特征。我们描述了我们的框架，优化并行架构，一个基于CPU，其他基于GPU的计算机实现。我们表明，后者能够解决大的分配问题（几个10 000的订单）在计算时钟时间的订单分钟。
The linear assignment problem is a fundamental problem in combinatorial optimization with a wide range of applications, from operational research to data science. 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 paper, we propose an alternative approach to solving the assignment problem using techniques adapted from statistical physics. Our first contribution is to fully describe this formalism, including all the proofs of its main claims. In particular we derive a strongly concave effective free-energy function that captures the constraints of the assignment problem at a finite temperature. We prove that 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. We prove also that for large enoughvalues the exact solution to the generic assignment problem can be derived using simple roundoff to the nearest integer of the elements of the computed assignment matrix. Our second contribution is to derive a provably convergent method to handle degenerate assignment problems, with a characterization of those problems. We describe computer implementations of our framework that are optimized for parallel architectures, one based on CPU, the other based on GPU. We show that the latter enables solving large assignment problems (of the orders of a few 10 000s) in computing clock times of the orders of minutes.