# Assignment problem with constraints - dual formulation - auction algorithm

I have to solve with an auction algorithm a typical assignment problem between $$N$$ agents and $$M\ge N$$ objects, but with some less usual constraints.

Let me first introduce the general formulation without any additional constraints.

The benefit for assigning object $$j$$ to agent $$i$$ is the non negative value $$\beta_{ij}$$. So, the assignment problem turns to maximizing the sum of benefits :

$$$$\sum_{ij} \beta_{ij}x_{ij}$$$$

where $$x_{ij} = 1$$ if object $$j$$ is assigned to $$i$$, $$0$$ otherwise.

This is known as the primal formulation, which usually comes with some constraints :

• an object $$j$$ can only be assigned once : $$$$\forall j~,~~\sum_i x_{ij} = 1$$$$
• an agent $$i$$ has to assign $$M_i$$ objects : $$$$\forall i~,~~\sum_j x_{ij} = M_i$$$$

Let's say $$\sum_{i=1}^N M_i = M$$ to ensure the problem is feasible and assume $$M_i = 1~,~\forall i$$ for the moment.

To solve this with an auction algorithm, I need to write the dual formulation, which is obtained by writing the lagrangian : $$$$L = \sum_{ij} (-\beta_{ij}) x_{ij} + \sum_i \pi_i (\sum_j x_{ij} - 1) + \sum_j p_j (\sum_i x_{ij} - 1)$$$$ $$$$L = \sum_{ij}(\pi_i + p_j - \beta_{ij}) x_{ij} - \sum_i \pi_i -\sum_j p_j$$$$ where I replaced the maximization problem by a minimization one and introduced dual variables for constraints on agents ($$\pi_i$$) and objects ($$p_j$$).

The dual function is the minimum of the Lagrangian on $$x_{ij}$$ values. If $$\pi_i + p_j > \beta_{ij}$$, the minimum is obtained with $$x_{ij} = 0$$, if $$\pi_i + p_j < \beta_{ij}$$, there is no minimum as $$x_{ij}$$ goes to infinity. When $$\pi_i + p_j = \beta_{ij}$$, $$x_{ij}$$ can be taken to unity. So the dual function to maximize is $$$$- \sum_i \pi_i -\sum_j p_j$$$$ with the constraint $$\pi_i + p_j \ge \beta_{ij}$$ and there is equality for the optimal assignment set.

The dual variables $$p_j$$ for objects are called their prices, the ones for agents are called marginal profits and equal : $$$$\pi_i = \max_j (\beta_{ij} - p_j)$$$$

Very shortly, the auction algorithm consists in letting each agent bid on its most profitable object $$$$j_i = \arg\max_j (\beta_{ij} - p_j)$$$$ and its bid $$b_i$$ is computed by the difference between $$\pi_i$$ and the second one most profitable object : $$$$b_i = \pi_i - \max_{j\ne j_i} (\beta_{ij} - p_j) + \varepsilon$$$$ where $$\varepsilon$$ is a small value guaranting bids to never be null.

Then, the bidded objects are attributed to the agent with highest bid and the object price is raised by that bid, so that prices can only strictly increase.

And so on, until there are no more unassigned agents.

===============

I come now to my question which is how to adapt the previous development in order to account for additional constraints on objects.

These ones consist in saying that if one object is assigned then some other ones will be forbidden to be assigned by any other agent.

You may think for example as renting cars. People may bid to get the car but at different times. You have several benefits at renting a given car at several times, say you want it more in the morning than in the afternoon, the opposite for another person.

Assume further that the car is rented for all day, which means that if you rent it for the morning, it will not be available in the afternoon for anyone. Conversely, if someone rents if for the afternoon, it is lost for you in the morning.

The object is then the couple (car, time) where time is either morning or afternoon. It is then clear that if you win the bid for (car, morning), the object (car, afternoon) becomes unassignable, and conversely.

Coming back to the mathematical formulation, such a constraint on a set $$J$$ of objects can be formulated as follows : $$$$\sum_{j\in J} \sum_i x_{ij} = 1$$$$ from which it is clear that if there is $$j'\in J$$ such that $$x_{ij} =1$$ then $$\forall j\in J~, j\ne j'~,~\forall i~,~~x_{ij} = 0$$

My question is then how to integrate this constraint in the lagrangian in order to get the right dual function to optimize, with the auction algorithm.

Here is how I would do.

Because the new constraint on objects in J is stronger than the former one $$\sum_i x_{ij} = 1$$. This latter could be completely relaxed because implied by the additional constraint. So $$$$L = \sum_{ij} (-\beta_{ij}) x_{ij} + \sum_i \pi_i (\sum_j x_{ij} - 1) + \sum_{j\notin J} p_j (\sum_i x_{ij} - 1) + \lambda (\sum_{j\in J} \sum_i x_{ij} - 1)$$$$ then $$$$L = \sum_{i,j\in J}(\pi_i + \lambda - \beta_{ij}) x_{ij} +\sum_{i,j\notin J}(\pi_i + p_j - \beta_{ij}) x_{ij}- \sum_i \pi_i -\sum_{j\notin J} p_j -\lambda$$$$

where $$\lambda$$ is the dual variable for the additional constraint.

I wonder if this is the correct formulation and how the auction algorithm can be adapted to this case. How agents bids on objects in $$J$$ ?

Regards

I wonder if my problem could be better managed by reviewing completely the assignment problem.

Indeed, consider still $$N$$ agents bidding on $$M$$ objects at $$P$$ time slots. The sum of benefits to maximize is $$$$\sum_{i=1}^N\sum_{j=1}^M\sum_{k=1}^P \beta_{ijk}x_{ijk}$$$$ with the constraints :

• an agent $$i$$ has to allocate $$M_i$$ (objects-time slots) $$(j,k)$$ $$$$\forall i~,~\sum_{j,k} x_{ijk} = M_i~,~~0\le x_{ijk} \le M_i$$$$ consider objects as being the parkings where you want to rent $$M_i$$ cars. You may want to rent all of them in the same parking $$j$$ and at the same time slot, $$x_{ijk} = M_i$$, or dispatch the rentings on several parkings and several time slots.

• the number of rentings for a given parking must not exceed its capacity : $$$$\forall j~,~\sum_{i,k} x_{ijk} \le Q_j$$$$

• the additional constraint is that for a given parking $$j$$, there is a limited number of renting per time slot : $$$$\forall j,k~,~\sum_{i} x_{ijk} \le P_{jk}$$$$

The benefit cannot be defined apart of either the parking or the time slot : an agent $$i$$ has a benefit at renting a car from that parking $$j$$ at a given time slot $$k$$ : $$\beta_{ijk}$$.

Then the Lagrangian is : $$$$L = \sum_{ijk}(-\beta_{ijk})x_{ijk} + \sum_i \pi_i (\sum_{jk} x_{ijk} - M_i) +\sum_j p_j (\sum_{ik} x_{ijk} - Q_j) + \sum_{jk} \lambda_{jk} (\sum_i x_{ijk} - P_{jk})$$$$ $$$$L = \sum_{ijk}(\pi_i + p_j + \lambda_{jk}-\beta_{ijk})x_{ijk} - \sum_i\pi_iM_i - \sum_j p_jQ_j -\sum_{jk} \lambda_{jk} P_{jk}$$$$

Then, we have to minimize $$$$\sum_i\pi_iM_i + \sum_j p_jQ_j +\sum_{jk} \lambda_{jk} P_{jk}$$$$ with the constraints : $$$$\pi_i + p_j + \lambda_{jk}\ge \beta_{ijk}$$$$ and $$0\le x_{ijk}\le M_i$$

I wonder if this formulation is more tractable and efficiently solvable by an auction algorithm than previous one.