# A General Statistical Physics Framework for Assignment Problems
## 2 A General Formulation of the Assignment Problem  
We consider two sets of points, \(S_{1}\) and \(S_{2}\), with cardinalities \(N_{1}\) and \(N_{2}\), respectively. We represent the cost of transportation between \(S_{1}\) and \(S_{2}\) as a matrix \(C\) whose elements \(C(i,j)\) are positive, for all \((i,j)\in[1,N_{1}]\times[1,N_{2}]\). We set the number of assignments between points in \(S_{1}\) and \(S_{2}\) to be a strictly positive integer number \(k\), a constant given as input to the problem. A point \(i\) is assigned to \(n_{1}(i)\) points in \(S_{2}\), with \(n_{1}(i)\) belonging to \([p_{min}(i),\ldots,p_{max}(i)]\), where \(p_{min}(i)\) and \(p_{max}(i)\) are non-negative integers satisfying \(0\leq p_{min}(i)\leq p_{max}(i)\leq N_{2}\). Similarly, a point \(j\) is assigned to \(n_{2}(j)\) points in \(S_{1}\), with \(n_{2}(j)\) belonging to \([q_{min}(j),\ldots,q_{max}(j)]\), where \(q_{min}(j)\) and \(q_{max}(j)\) are non-negative integers satisfying \(0\leq q_{min}(j)\leq q_{max}(j)\leq N_{1}\). Using the traditional \"task-agent\" for the formulation of an assignment problem, \(S_{1}\) represents the tasks, and \(S_{2}\) the agents. \(n_{1}(i)\) is the number of agents needed to perform task \(i\), while \(n_{2}(j)\) is the number of tasks that can be performed by agent \(j\). \(p_{min}(i)\) and \(p_{max}(i)\) represent the minimum and maximum number of agents that are assigned to a task \(i\), respectively, while \(q_{min}(j)\) and \(q_{max}(j)\) represent the minimum and maximum number of tasks that can be assigned to an agent \(j\), respectively. We use a general definition of these boundaries, in that we allow each task and each agent to have their own limits. The multi-assignment problem is then framed as the search for an assignment matrix \(G\) that defines the correspondence between points in \(S_{1}\) and points in \(S_{2}\). This matrix is found by minimizing the assignment cost \(U\), defined as  
\[U(G,C)=\sum_{i,j}G(i,j)C(i,j). \tag{2}\]  
The summations encompass all \(i\) in \(S_{1}\) and \(j\) in \(S_{2}\). The objective is to locate the minimum of \(U\) given the values of \(G(i,j)\) that adhere to the following constraints:\[\forall i,\quad\sum\limits_{j}G(i,j)=n_{1}(i)\] \[\forall j,\quad\sum\limits_{i}G(i,j)=n_{2}(j)\] \[\sum\limits_{i}\sum\limits_{j}G(i,j)=k \tag{3}\] \[\forall(i,j),\quad G(i,j)\in\{0,1\}\] \[\forall(i),\quad n_{1}(i)\in[p_{min}(i),\ldots,p_{max}(i)]\] \[\forall(j),\quad n_{2}(j)\in[q_{min}(j),\ldots,q_{max}(j)],\]  
where \(k\) is the actual number of task-agent pairs. The numbers \(p_{min}(i)\), \(p_{max}(i)\), \(q_{min}(j)\), \(q_{max}(j)\), and \(k\) are problem-specific and given. They do satisfy some constraints, such as \(0\leq p_{min}(i)\leq p_{max}(i)\leq N_{2}\) and \(0\leq q_{min}(j)\leq q_{max}(j)\leq N_{1}\), as described above, as well as \(0<k\leq\sum_{i=1}^{N_{1}}p_{min}(i)\) and \(k\leq\sum_{j=1}^{N_{2}}q_{min}(j)\). We store those numbers in four vectors, \(P_{min}=(p_{min}(1),\ldots,p_{min}(N_{1}))\), \(P_{max}=(p_{max}(1),\ldots,p_{max}(N_{1}))\), \(Q_{min}=(q_{min}(1),\ldots,q_{min}(N_{2}))\), \(Q_{max}=(q_{max}(1),\ldots,q_{max}(N_{2}))\). Equation (3) recap most of the standard linear assignment problems:  
1. If \(k=N_{1}=N_{2}\) and \(p_{min}(i)=p_{max}(i)=q_{min}(j)=q_{max}(j)=1\) for all \(i\) and \(j\), we recover the balanced assignment problem,
2. If \(p_{min}(i)=q_{min}(j)=0\) and \(p_{max}(i)=q_{max}(j)=1\) for all \(i\) and \(j\), the equations correspond to the \(k\)-cardinality assignment problem [19; 20; 21]. In Equation (3), \(G(i,j)\), \(n_{1}(i)\) and \(n_{2}(j)\) are unknown, defining a total of \(N_{1}N_{2}+N_{1}+N_{2}\) variables. The solution to the general assignment problem is given by the functions \(n_{1}^{*}\) and \(n_{2}^{*}\) on \(S_{1}\) and \(S_{2}\), respectively, which identify which tasks and which agents are involved in the optimal assignment, the transportation matrix \(G^{*}\) that defines these correspondences, and the minimum assignment cost \(U^{*}=U(G^{*},C)\).