# Maximum flow on a tripartite graph

I have to solve an assignment problem between $$\{1,\dots, N\}$$ agents and $$\{1,\dots, M\}$$ objects, which comes to maximize : $$$$\sum_{ij}\beta_{ij}x_{ij}$$$$ 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 : $$$$\sum_i x_{ij} = 1~,~~\sum_j x_{ij} = 1$$$$ 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 : $$$$\sum_{j\in \mathcal{J}_k}\sum_i x_{ij} \le P_k$$$$

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 : $$$$0\le\sum_i y_{ik} \le P_k$$$$ 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 :

$$$$\sum_i y_{ik} = \sum_j z_{kj}$$$$ 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: $$$$|\mathcal{K}_j| x_{ij} = \sum_{k\in\mathcal{K}_j} y_{ik}$$$$ 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 : $$$$\sum_{k\in\mathcal{K}_j} z_{kj} + |\mathcal{K}_j| x_{sj} = |\mathcal{K}_j|$$$$ 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 : $$$$\sum_k (|\mathcal{J}_k| -P_k) - \sum_j (|\mathcal{K}_j| - 1)$$$$ objects unassigned. The second term accounts for objects that belong to more than one constraint. Thus : $$$$\sum_j x_{sj} \ge \sum_k (|\mathcal{J}_k| -P_k) - \sum_j (|\mathcal{K}_j| - 1)$$$$

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

So, for the problem to be feasible, I need at the least : $$$$\sum_i M_i$$$$ objects whereas there are at least $$$$\sum_k P_k - \sum_j (|\mathcal{K}_j| - 1)$$$$ of them available. The difference between both will also remain unassigned at the end : $$$$\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}$$$$ 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 : $$$$\sum_j x_{sj} - (M-N) = \sum_k y_{sk}$$$$

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

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{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}$$$$

$$$$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}$$$$

$$$$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$$$$

$$$$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|$$$$

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

$$$$E = -\sum_{ik} \lambda_k y_{ik} - \sum_k\lambda_k y_{sk} + \sum_k\lambda_k P_k$$$$

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

Finally : $$$$\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}$$$$

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

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.

• 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. – deb2014 Jan 22 '20 at 15:42

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.