# A General Statistical Physics Framework for Assignment Problems
###### Abstract  
Linear assignment problems hold a pivotal role in combinatorial optimization, offering a broad spectrum of applications within the field of data sciences. They consist of assigning \"agents\" to \"tasks\" in a way that leads to a minimum total cost associated with the assignment. The assignment is balanced when the number of agents equals the number of tasks, with a one-to-one correspondence between agents and tasks, and it is and unbalanced otherwise. Additional options and constraints may be imposed, such as allowing agents to perform multiple tasks or allowing tasks to be performed by multiple agents. In this paper, we propose a novel framework that can solve all these assignment problems employing methodologies derived from the field of statistical physics. We describe this formalism in detail and validate all its assertions. A major part of this framework is the definition of a concave effective free energy function that encapsulates the constraints of the assignment problem within a finite temperature context. We demonstrate that this free energy monotonically decreases as a function of a parameter \(\beta\) representing the inverse of temperature. As \(\beta\) increases, the free energy converges to the optimal assignment cost. Furthermore, we demonstrate that when \(\beta\) values are sufficiently large, the exact solution to the assignment problem can be derived by rounding off the elements of the computed assignment matrix to the nearest integer. We describe a computer implementation of our framework and illustrate its application to multi-task assignment problems for which the Hungarian algorithm is not applicable. s +  
Let us first define the assignment problem. Let \(T\) be the set of tasks and \(A\) the set of agents, with possibly different cardinalities \(|T|=N_{2}\) and \(|A|=N_{1}\). If we define \(C(i,j)\) as the cost of assigning task \(i\) to the agent \(j\), the balanced assignment problem can be stated as finding a transportation matrix \(G\) between \(T\) and \(A\) whose elements are non-negative integer numbers and that minimizes  
\[U=\sum_{i\in T}\sum_{j\in A}C(i,j)G(i,j). \tag{1}\]  
In the special case of \(N_{1}=N_{2}\), with a one-to-one assignment of tasks to agents (the _balanced assignment problem_), \(G\) corresponds to a permutation of \(\{1,\ldots,N\}\). In the more general case, \(N_{1}\) and \(N_{2}\) can be different (unbalanced assignment), the number of pairings \(k\) may be imposed with \(0<k\leq\min(N_{1},N_{2})\) (\(k\)-cardinality assignment problem), and/or tasks and agents may be assigned to more than one agents and tasks, respectively. In those general cases, \(G\) remains binary but may not be a permutation matrix (in the specific case of the \(k\)-cardinality problem, for example, \(G\) is a partial permutation matrix of rank \(k\)). As mentioned above, assignment problems are basically combinatorial optimization problems that can be solved numerically using a linear programming model or, more specifically, a linear integer programming method. Those methods, however, are theoretically \(NP\)-complete. There are fast heuristics that can solve such problems, such as [PERSON]'s simplex method [4]. The assignment problem, however, is a specialized case of integer linear programming that can be recast and solved by an exact polynomial algorithm. For example, the most common algorithm for solving the balanced assignment problem has its origin in the work of [PERSON] [5]. It was \"rediscovered\" 60 years later by [6] and is now dubbed the Hungarian algorithm. It is a global algorithm that iteratively identifies assignments between agents and tasks. It is polynomial in running time (\(O(N^{4})\) or \(O(N^{3})\) depending on the implementation). While it is serial by nature, there are many recent efforts to parallelize this algorithm (see, for example [7; 8; 9], and references therein). The Hungarian algorithm can be adapted to many unbalanced assignment problems.