# A General Statistical Physics Framework for Assignment Problems
## 2 A General Formulation of the Assignment Problem
### Effective Free Energy for the General Assignment Problem  
Solving the multi-assignment problem entails determining the minimum of the function defined in Equation (2) across the potential mappings between the two discrete sets of points under consideration. Identifying this minimum is tantamount to identifying the most probable state of the system it characterizes. This \"system\" encompasses the various binary transportation plans, also referred to as assignment matrices, between \(S_{1}\) and \(S_{2}\) that adhere to the constraints Equation (3). Each state within this system corresponds to assignment matrix \(G\) with its associated energy \(U(G,C)\) as defined in Equation (2). The probability \(P(G)\) linked with an assignment matrix \(G\) is given by  
\[P(G)=\frac{1}{Z(\beta)}e^{-\beta U(G,C)}. \tag{4}\]  
In this equation, \(\beta\) is the inverse temperature, namely \(\beta=1/k_{B}T\), where \(k_{B}\) is the Boltzmann constant and \(T\) is the temperature, and \(Z(\beta)\) is the partition function computed over all states of the system. As this system is defined by the assignment matrices \(G\) and by the marginals of \(G\), \(n_{1}\), and \(n_{2}\), the partition function is equal to  
\[Z_{\beta} = e^{-\beta\mathcal{F}_{\beta}} \tag{5}\] \[= \sum\limits_{G(i,j)=0}^{1}\sum\limits_{n_{1}(i)=p_{min}(i)}^{p_{ max}(i)}\sum\limits_{n_{2}(j)=q_{min}(j)}^{q_{max}(j)}e^{-\beta U(G,C)},\]where \(\mathcal{F}(\beta)\) is the free energy of the system. The practicality of this free energy is limited due to the inability to compute it explicitly. We develop a method for approximating it through the saddle point approximation technique. Taking into account the constraints in Equation (3), the partition function can be written as  
\[Z_{\beta}=\sum_{G(i,j)=0}^{1}\sum_{n_{1}(i)=p_{min}(i)}^{p_{max}(i )}\sum_{n_{2}(j)=q_{min}(i)}^{q_{max}(j)}e^{-\beta\sum\limits_{i,j}C(i,j)G(i,j)}\] \[\prod_{i}\delta\left(\sum_{j}G(i,j)-n_{1}(i)\right)\prod_{j} \delta\left(\sum_{i}G(i,j)-n_{2}(j)\right)\] \[\delta\left(\sum_{i,j}G(i,j)-k\right). \tag{6}\]  
The three sums impose that \(G(i,j)\), \(n_{1}(i)\), and \(n_{2}(j)\) take integer values within some ranges defined by the constraints Equation (3). The additional constraints are imposed through the delta functions. We employ the Fourier representation of those delta functions, thereby introducing additional auxiliary variables \(x\), \(\lambda(i)\), and \(\mu(j)\), with \(i\in[1,N_{1}]\) and \(j\in[1,N_{2}]\). The partition function is then given, after reorganization, by (up to a multiplicative constant) by  
\[Z_{\beta}= \int_{-\infty}^{+\infty}\prod_{i}d\lambda(i)\int_{-\infty}^{+ \infty}\prod_{j}d\mu(j)\int_{-\infty}^{+\infty}dxe^{\beta\beta tx}\] \[\sum_{n_{1}(i)=p_{min}(i)}^{p_{max}(i)}\sum_{n_{2}(j)=q_{min}(i)} ^{q_{max}(j)}e^{\beta\left(\sum\limits_{i}\delta\lambda(i)n_{1}(i)+\sum \limits_{j}\delta\mu(j)n_{2}(j)\right)}\] \[\sum_{G(i,j)=0}^{1}e^{-\beta\sum\limits_{i,j}G(i,j)\left(C(i,j) +\delta\lambda(i)+\delta\mu(j)+\delta x\right)}, \tag{7}\]  
where \(\beta\) is the imaginary unit (\(\beta^{2}=-1\)). Note that we have rescaled the variables \(x\), \(\lambda\), and \(\mu\) by a factor \(\beta\) for consistency with the energy term.