Assignment problem with batching costs

Question

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.

Answer 1

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<i_2} \sum_j c_{i_1,i_2,j} x_{i_1,j} x_{i_2,j} \tag1$$ 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<i_2} \sum_j c_{i_1,i_2,j} y_{i_1,i_2,j} \tag4$$ subject to $(2)$, $(3)$, and \begin{align} y_{i_1,i_2,j} &\le x_{i_1,j} &&\text{for all $i_1<i_2$ and $j$} \tag5\\ y_{i_1,i_2,j} &\le x_{i_2,j} &&\text{for all $i_1<i_2$ and $j$} \tag6\\ y_{i_1,i_2,j} &\ge x_{i_1,j} + x_{i_2,j} - 1 &&\text{for all $i_1<i_2$ and $j$} \tag7\\ \end{align}

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