I have to solve an assignment problem between $\{1,\dots, N\}$ agents and $\{1,\dots, M\}$ objects, which comes to maximize : \begin{equation} \sum_{ij}\beta_{ij}x_{ij} \end{equation} where $x_{ij}$ equals one if object $j$ is assigned to $i$, $0$ otherwise. The benefit of such an assignment is the non-negative value $\beta_{ij}$.

This problem usually comes wih some constraints : \begin{equation} \sum_i x_{ij} = 1~,~~\sum_j x_{ij} = 1 \end{equation} stating that an object can only be assigned once and that an agent can only assign one object.

As far as I understand, this problem can also be viewed as a maximum flow on a bipartite graph and can be efficiently solved by an auction algorithm (see Bertsekas et al.)

I have to implement additional constraints labeled $k=1,\dots, K$ which are all of the same form : the $k^{th}$ one imposes that on a subset of object $\mathcal{J}_k$, only a limited number of them, say $P_k$, can be assigned in the same time : \begin{equation} \sum_{j\in \mathcal{J}_k}\sum_i x_{ij} \le P_k \end{equation}

My question is that I find quite difficult to solve former problem with these new constraints on a bipartite graph and I wonder if a tripartite graph would be more convenient.

Here is below how I would do, I would like to call upon more experienced people in this field to assess whether this approach is well suited or if there is a simpler one.

I put the former problem with the additional constraints in the form of a tripartite graph : the first column is still that of agents and the third one that of objects, except that agents and objects are no more directly linked.

Between first and third column, I insert the column of the $\{1,\dots,K\}$ constraints. Let $y_{ik}\in\{0,1\}$ be the link between agent $i$ and constraint $k$. The additional constraint $k$ now reads : \begin{equation} 0\le\sum_i y_{ik} \le P_k \end{equation} The flow of agents onto constraint $k$ is limited.

Furthermore, let $z_{kj}\in\{0,1\}$ be the link between constraint $k$ and object $j$.

That is to note, an object $j$ can be linked to several constraints, let $\mathcal{K}_j$ be the subset of constraints in which object $j$ is involved, i.e. $j\in \mathcal{J}_k$.

The flow from constraint $k$ to objects must equal that of agents to this constraint :

\begin{equation} \sum_i y_{ik} = \sum_j z_{kj} \end{equation} which means that an agent $i$ is connected to constraint $k$ because there is some object $j$ linked to it, and conversely.

Then, coming back to the bipartite graph, the link $x_{ij}$ between agent $i$ and object $j$ is now given by: \begin{equation} |\mathcal{K}_j| x_{ij} = \sum_{k\in\mathcal{K}_j} y_{ik} \end{equation} There is equality only if the agent $i$ is connected to all constraints $k$ in which object $j$ is involved.

Because $P_k< |\mathcal{J}_k|$ there will always remain at least $|\mathcal{J}_k| - P_k$ unassigned objects due to constraint $k$.

Let's define a virtual agent $s$ to which we attach all objects (at zero benefit) not linked with any constraint $k$, $\forall k~~ z_{kj} = 0$. The link is denoted $x_{sj}\in\{0,1\}$ because it is a direct link between an agent and an object.

Each object $j$ must fulfill : \begin{equation} \sum_{k\in\mathcal{K}_j} z_{kj} + |\mathcal{K}_j| x_{sj} = |\mathcal{K}_j| \end{equation} Then, either object $j$ is connected to all its constraints, $\forall k\in\mathcal{K}_j~,~z_{kj} = 1$, or it is connected to the virtual node, $x_{sj}=1$.

It is clear that if the flow on all constraints reach its maximum, there will remain at least : \begin{equation} \sum_k (|\mathcal{J}_k| -P_k) - \sum_j (|\mathcal{K}_j| - 1) \end{equation} objects unassigned. The second term accounts for objects that belong to more than one constraint. Thus : \begin{equation} \sum_j x_{sj} \ge \sum_k (|\mathcal{J}_k| -P_k) - \sum_j (|\mathcal{K}_j| - 1) \end{equation}

I assume now that each agent $i$ must be granted $M_i \ge 1$ objects : \begin{equation} \sum_j x_{ij} = M_i \end{equation}

So, for the problem to be feasible, I need at the least : \begin{equation} \sum_i M_i \end{equation} objects whereas there are at least \begin{equation} \sum_k P_k - \sum_j (|\mathcal{K}_j| - 1) \end{equation} of them available. The difference between both will also remain unassigned at the end : \begin{equation} \begin{split} \sum_j x_{sj} &\ge \sum_k (|\mathcal{J}_k| -P_k) - \sum_j (|\mathcal{K}_j| - 1) +\sum_k P_k - \sum_j (|\mathcal{K}_j| - 1)- \sum_i M_i\\ &\ge \underbrace{\sum_k |\mathcal{J}_k| - \sum_j (|\mathcal{K}_j| - 1)}_M - \biggl(\underbrace{\sum_i M_i + \sum_j (|\mathcal{K}_j| - 1)}_N\biggr) \end{split} \end{equation} where $M$ is the true number of objects and $N$ is the true number of objects required by agents.

Then, each time the links between an object and its constraints are broken, the object becomes unassigned, so that : \begin{equation} \sum_j x_{sj} - (M-N) = \sum_k y_{sk} \end{equation}

where $y_{sk}$ is the link between the virtual agent and the constraint $k$, whose capacity is $\{0,\dots,P_k\}$ and checks : \begin{equation} \sum_i y_{ik} + y_{sk} = P_k~,~~0\le y_{sk}\le P_k \end{equation}

I would like then to write the dual formulation of this problem in order to solve it with an auction algorithm. Coming back to the assignment problem, its lagrangian is :

\begin{equation} \begin{split} \mathcal{L} = & \underbrace{\sum_{ij} (-\beta_{ij})x_{ij}}_A + \underbrace{\sum_i \pi_i \biggl(\sum_j x_{ij} - M_i \biggr)}_B + \underbrace{\sum_j p_j \biggl(\sum_{k\in\mathcal{K}_j} z_{kj} + |\mathcal{K}_j| x_{sj} - |\mathcal{K}_j| \biggr)}_C\\ & + \underbrace{\sum_k \mu_k \biggl(\sum_i y_{ik} - \sum_{j\in\mathcal{J}_k} z_{kj} \biggr)}_D + \underbrace{\sum_k ( -\lambda_k) \biggl(\sum_i y_{ik} + y_{sk} - P_k\ \biggr)}_E\\ & + \underbrace{(-\lambda)\biggl(\sum_j x_{sj} - (M -N) - \sum_k y_{sk} \biggr)}_F \end{split} \end{equation}

\begin{equation} A = \sum_{ij} (-\beta_{ij})x_{ij} = \sum_{ij} (-\beta_{ij})\frac{1}{|\mathcal{K}_j|}\sum_{k\in\mathcal{K}_j} y_{ik} = \sum_{ik}\biggl(-\sum_{j\in\mathcal{J}_k}\frac{\beta_{ij}}{|\mathcal{K}_j|}\biggr)y_{ik} \end{equation}

\begin{equation} B = \sum_i \pi_i \biggl[\sum_j\biggl(\frac{1}{|\mathcal{K}_j|}\sum_{k\in\mathcal{K}_j} y_{ik}\biggr) - M_i \biggr] = \sum_{ik}\pi_i \biggl(\sum_{j\in\mathcal{J}_k}\frac{1}{|\mathcal{K}_j|} \biggr)y_{ik} - \sum_i \pi_i M_i \end{equation}

\begin{equation} C = \sum_k\sum_{j\in\mathcal{J}_k} p_j z_{kj} + \sum_j p_j |\mathcal{K}_j| x_{sj} - \sum_j p_j |\mathcal{K}_j| \end{equation}

\begin{equation} D = \sum_{ik} \mu_k y_{ik} - \sum_k\sum_{j\in\mathcal{J}_k}\mu_k z_{kj} \end{equation}

\begin{equation} E = -\sum_{ik} \lambda_k y_{ik} - \sum_k\lambda_k y_{sk} + \sum_k\lambda_k P_k \end{equation}

\begin{equation} F = -\sum_j \lambda x_{sj} + \lambda (M -N) + \sum_k \lambda y_{sk} \end{equation}

Finally : \begin{equation} \begin{split} \mathcal{L} = & \sum_{ik}\biggl[\pi_i \biggl(\sum_{j\in\mathcal{J}_k}\frac{1}{|\mathcal{K}_j|}\biggr) + \mu_k - \lambda_k -\sum_{j\in\mathcal{J}_k}\frac{\beta_{ij}}{|\mathcal{K}_j|}\biggr] y_{ik}\\ &+\sum_k\sum_{j\in\mathcal{J}_k}(p_j - \mu_k) z_{kj} + \sum_k(\lambda - \lambda_k)y_{sk} + \sum_j (p_j|\mathcal{K}_j| - \lambda)x_{sj}\\ &- \sum_i \pi_i M_i -\sum_j p_j |\mathcal{K}_j| + \sum_k\lambda_k P_k+ \lambda (M -N) \end{split} \end{equation}

The dual formulation consists then in minimizing : \begin{equation} \sum_i \pi_i M_i +\sum_j p_j |\mathcal{K}_j| - \sum_k\lambda_k P_k - \lambda (M -N) \end{equation}

under the constraints : \begin{align} \pi_i \biggl(\sum_{j\in\mathcal{J}_k}\frac{1}{|\mathcal{K}_j|}\biggr) + \mu_k &\ge \lambda_k +\sum_{j\in\mathcal{J}_k}\frac{\beta_{ij}}{|\mathcal{K}_j|}\\ p_j &\ge \mu_k \\ p_j|\mathcal{K}_j| &\ge \lambda \end{align} and

  • if $\lambda > \lambda_k$ then $y_{sk} = 0$

  • if $\lambda = \lambda_k$ then $y_{sk} \in\{1, \dots, P_k -1\}$

  • if $\lambda < \lambda_k$ then $y_{sk} = P_k$

Then, how to perform the auction algorithm ? agents now bid on constraints.

  • $\begingroup$ I made some corrections and went a little further in the development. But it is hard for me to assess if this is correct and how to perform the auction algorithm. $\endgroup$
    – deb2014
    Jan 22 '20 at 15:42

Your problem is NP-hard. With the extra constraint, it is at least as hard as max independent set.

In particular, suppose we have an undirected graph $G$. Let there be one object per vertex in $G$. For each edge in $G$, we'll have a constraint saying that at most one of the two endpoints of that edge can be assigned (using your new constraint type). We'll then have one actor per object, and the $\beta_{ij}$ can be all 1 (or you can have $\beta_{ii}=1$ and $\beta_{ij}=0$ for $i \ne j$). Now the maximum assignment corresponds to the maximum independent set. So, any efficient algorithm for your problem would also provide an efficient algorithm for max independent set -- something which we expect probably does not exist.

So, I wouldn't expect any efficient algorithm for your problem. Instead, I would suggest using heuristics, an ILP solver, or looking for an approximation algorithm or some kind of parametrized-complexity algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.