Maximum flow on a tripartite graph

Question

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.

Answer 1

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.