# A General Statistical Physics Framework for Assignment Problems
## 5 Matching: A Program for Solving Assignment Problems  
We have implemented the multi-assignment framework described here in a C++ program, Matching, that is succinctly described in Algorithm 1. Matching relies on an iterative process in which the parameter \(\beta\) is gradually increased. At each value of \(\beta\), the nonlinear system of equations defined by Equation (10) is solved. We write this system as  
\[ \begin{cases}\mathbf{A}_{\lambda}=0,\\ \mathbf{A}_{\mu}=0,\\ A_{x}=0,\end{cases} \]  
where \(\mathbf{A}=(\mathbf{A}_{\lambda},\mathbf{A}_{\mu},A_{x})\) is a vector of predicates defined as  
\[A_{\lambda}(i)= \sum_{j}h(\beta(C(i,j)+\lambda(i)+\mu(j)+x))\] \[-g(\beta\lambda(i),p_{min}(i),p_{max}(i)),\] \[A_{\mu}(j)= \sum_{i}h(\beta(C(i,j)+\lambda(i)+\mu(j)+x))\] \[A_{x}= \sum_{i,j}h(\beta(C(i,j)+\lambda(i)+\mu(j)+x))-k.\]  
This system has \(N_{1}+N_{2}+1\) equations, with the same number of variables. It is solved using an iterative Newton-Raphson method (for details, see, for example [16; 25]). Once the SPA system of equations is solved, the assignment matrix \(\overline{G}_{\beta}\), the functions \(\overline{n}_{1\beta}\), \(\overline{n}_{2\beta}\), and the corresponding transportation energy \(U^{MF}(\beta)\) are computed. The iterations over \(\beta\) are stopped if the mean field energy \(U^{MF}_{\beta}\) does not change anymore (within a tolerance TOL usually set to \(10^{-6}\)). Otherwise, \(\beta\) is increased, and the current values of \(\lambda\), \(\mathbf{\mu}\) and \(x\) are used as input for the following iteration. At convergence, the values of the assignment matrix are rounded to the nearest integer (indicated as \([\,]\) in the output of Algorithm 1). The minimal energy is then computed using the corresponding integer matrix. The primary computational expense of this algorithm arises from solving the nonlinear set of equations corresponding to the SPA at every \(\beta\) value. We use for this purpose an iterative Newton-Raphson method (see [15]). ```
Input:\(N_{1}\) and \(N_{2}\), the number of agents and tasks; \(p_{min}(i)\) and \(p_{max}(i)\), the minimum and maximum number of agents needed to perform task \(i\), and \(q_{min}(j)\) and \(q_{max}(j)\), the minimum and maximum number of tasks that can be performed by an agent \(j\); \(k\), the expected number of assignments; the cost matrix \(C\). Initial value \(\beta_{0}\) for \(\beta\), the inverse of the temperature Initialize: Initialize arrays \(\lambda\) and \(\mu\) to \(0\) and initialize \(x=0\). Set \(STEP=\sqrt{10}\). for\(i=1,\ldots\) until convergence do (1) Initialize \(\beta^{i}=STEP*\beta^{i-1}\). (2) Solve non linear Equation (10) for \(\lambda\), \(\mu\) and \(x\) at saddle point (3) Compute corresponding \(\overline{G}_{\beta}^{i}\), \(\overline{n}_{1\beta}^{i}\), \(\overline{n}_{2\beta}^{i}\), and \(U_{\beta}^{i,MF}\) (4) Check for convergence: if \(|U_{\beta}^{i,MF}-U_{\beta}^{i-1,MF}|<TOL\), stop endfor Output: The converged assignment matrix \(\left\lfloor\overline{G}_{\beta}\right\rfloor\), the functions \(\left\lfloor\overline{n}_{1\beta}\right\rfloor\), \(\left\lfloor\overline{n}_{2\beta}\right\rfloor\) over the agents and tasks, and the minimal associated cost \(U_{\beta}\). ```  
**Algorithm 1** Matching: a temperature-dependent framework for solving the multi-assignment problem  
As for any annealing scheme, the initial temperature, or, in our case, the initial value \(\beta_{0}\), is a parameter that significantly impacts the efficiency of the algorithm. Setting \(\beta_{0}\) to be too small (i.e., a high initial temperature) will lead to inefficiency as the system will spend a significant amount of time at high temperatures, while setting \(\beta_{0}\) too high will require many steps to converge at the corresponding low temperature, thereby decreasing the efficiency brought about by annealing. The value of \(\beta\) scales the cost matrix \(C\) and as such is related to the range of this matrix, more specifically to its largest value, \(C_{max}\).