# Assignment problem with batching costs

I am studying an assignment problem with batching costs, and I would like to know if there is a standard name or algorithm for this problem. I know this problem can be formulated as mixed-integer programming and be solved using the solvers, but I am looking for algorithms that are faster than the standard MILP methods. Both exact and approximated algorithms are appreciated, and polynomial-time methods are expected if exist.

The problem is: We have $$i$$ jobs that can be assigned to $$j$$ workers, $$j>i$$. Each job $$i$$ has a cost when assigned to worker $$j$$, namely, $$w_{ij}$$. Each worker $$j$$ can work with one or two job(s). When worker $$j$$ only works with one job, there is no additional cost. However, if worker $$j$$ works with two jobs, there is an additional cost. This additional cost can be regarded as a batching cost as it only exists when two jobs are assigned to the same worker. The additional cost for worker $$j$$ with job $$i_1$$ and $$i_2$$ is $$c_{i_1i_2j}$$, and it can be arbitrarily positive or negative. In this case, the total cost for worker $$j$$ with job $$i_1$$ and $$i_2$$ is $$w_{i_1j}+w_{i_2j}+c_{i_1i_2j}$$. Our objective is to assign all the jobs with a minimum total cost.

• Welcome to OR.SE. Are you sure that $j \ge i$? If so, you can assign all jobs to all workers without any additional cost? Apr 5 '21 at 13:13
• @A.Omidi Thx for the reply. We surely can assign all jobs without any additional cost, but the costs $w_{ij}$ are different for $i$ and $j$. If we assign all jobs without any additional cost, we might not have a minimum total cost. Apr 5 '21 at 13:19
• Is there any way to convert these different costs $w_(i,j)$ to their corresponding time? If so, one possible way would be formulating the problem as a varient of the parallel machine scheduling with sequence depending setup time to minimize sum of the completion time which the converted $w_(i,j)$ can be interpreted as the setup time. Apr 5 '21 at 14:13
• @A.Omidi This is a good idea. Unfortunenately, our costs include more than one factors(time, quality, etc.), so it cannot be converted in this way. Apr 5 '21 at 14:26
• What's the order of magnitude of $i$ and $j$? Have you already tried the MILP implementation? How long does it take to solve your problem with a MILP solver or to find a good enough solution? What computation time would you expect? Apr 5 '21 at 15:25

You can formulate this as an instance of the quadratic assignment problem by duplicating the workers and incurring the batching cost only for pairs of duplicate workers.

Here's an alternative MIQP formulation that does not double the number of workers. Let binary decision variable $$x_{i,j}$$ indicate whether job $$i$$ is assigned to worker $$j$$. The problem is to minimize $$\sum_{i,j} w_{i,j} x_{i,j} + \sum_{i_1 subject to \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all i} \tag2\\ \sum_i x_{i,j} &\le 2 &&\text{for all j} \tag3\\ \end{align} You can use an MIQP solver directly or linearize.

The most straightforward linearization is to introduce a new binary (optionally nonnegative) decision variable $$y_{i_1,i_2,j}$$ to represent the product $$x_{i_1,j} x_{i_2,j}$$ and then minimize $$\sum_{i,j} w_{i,j} x_{i,j} + \sum_{i_1 subject to $$(2)$$, $$(3)$$, and \begin{align} y_{i_1,i_2,j} &\le x_{i_1,j} &&\text{for all i_1

You can strengthen this formulation by replacing $$(5)$$ and $$(6)$$ with the valid inequality \begin{align} \sum_{i < i_2} y_{i,i_2,j} + \sum_{i > i_2} y_{i_2,i,j} &\le x_{i_2,j} &&\text{for all i_2 and j} \tag8\\ \end{align} Note that $$(8)$$ is obtained via RLT by multiplying both sides of $$(3)$$ by $$x_{i_2,j}$$.

I would be interested to hear how your MILP compares with:

• MIQP: minimize $$(1)$$ subject to $$(2)$$ and $$(3)$$.
• MILP: minimize $$(4)$$ subject to $$(2)$$, $$(3)$$, $$(7)$$, and $$(8)$$.
• Thx. As far as I know, the QAP is proven to be NP-hard, and solving it seem to be too time-consuming for my applications. Any fast algorithm for QAP recommend? Apr 5 '21 at 13:53
• @LuoArChen LocalSolver is efficient in solving QAP problems in practice: localsolver.com/benchmarkqap.html. LocalSolver is commercial software. If you're just interested in good-quality solutions, then a local-search heuristic based on k-exchange will be ok. If your instances are large (thousands of jobs and workers), then incremental evaluation of the exchanges will be a must to hope high-quality solutions in minutes. Apr 5 '21 at 15:23
• Also, this is a special case where the quadratic part is quite sparse, so you should expect better performance than the worst case. Apr 5 '21 at 16:12
• @LocalSolver Thx for providing your solution. Can you refer some good reference for the local-search heuristic based on k-exchange? Apr 6 '21 at 7:14
• @LuoArChen By searching "QAP local search" on the web, you will find many references. For example, have a look at neighborhoods described in archive.alvb.in/msc/04_infoea/seminar/papers/…. The so-called 2-exchange is conceptually simple. Given an assignment of jobs to workers, swap the jobs of 2 workers. Evaluate the new assignment; if better, take it, otherwise leave it. Then, you can generalize to k-exchange. The evaluation of the new assignment can be done incrementally, then allowing to get fast convergence. Apr 6 '21 at 20:23