\[\bbox[lightcyan,10px,border:3px solid darkblue]{\begin{align}\min\>&\sum_{i,j} c_{i,j} x_{i,j}\\ & \sum_j x_{i,j} = 1 && \forall i\\ & \sum_i x_{i,j} = 1 && \forall j\\&x_{i,j} \in \{0,1\} \end{align}}\]

There are highly efficient specialized algorithms for this problem [1]. I often solve these problems just as an LP (the integer variables are automatically integer valued for this particular problem). That sounds like a dumb approach, but there are some reasons:

- LP solvers are actually very good in solving this quickly (often faster than a specialized method that is not implemented with very much care for efficiency [2]).
- Variants and extensions are (often) easily handled.

The standard model above assumes the sets \(i \in I\) (sources) and \(j \in J\) (destinations) have the same size. Let \(n=|I|\) and \(m=|J|\) be the number of \(i\)'s and \(j\)'s. Thus the standard model has \(n=m\). Now assume we have more \(j\)'s than \(i\)'s: \(m>n\). The model can be updated to:

\[\bbox[lightcyan,10px,border:3px solid darkblue]{\begin{align}\min\>&\sum_{i,j} c_{i,j} x_{i,j}\\ & \sum_j x_{i,j} = 1 && \forall i\\ & \sum_i x_{i,j} \le 1 && \forall j\\&x_{i,j} \in \{0,1\} \end{align}}\]

I.e. each \(i\) is connected to a unique \(j\), but some \(j\)'s are not assigned. A solution for a random data set with \(n=5\) and \(m=10\) can look like:

---- 41 PARAMETER c cost coefficients j1 j2 j3 j4 j5 j6 j7 j8 j9 j10 i1 0.661 0.756 0.627 0.284 0.086 0.103 0.641 0.545 0.032 0.792 i2 0.073 0.176 0.526 0.750 0.178 0.034 0.585 0.621 0.389 0.359 i3 0.243 0.246 0.131 0.933 0.380 0.783 0.300 0.125 0.749 0.069 i4 0.202 0.005 0.270 0.500 0.151 0.174 0.331 0.317 0.322 0.964 i5 0.994 0.370 0.373 0.772 0.397 0.913 0.120 0.735 0.055 0.576 ---- 41 VARIABLE x.L assignment variables j2 j5 j6 j9 j10 i1 1 i2 1 i3 1 i4 1 i5 1

Let's add a picture to this post (created with

**tikz**):

Original assignment and new variant |

In [3] an unusual variant is asked for:

**the assigned \(j\)'s should be adjacent**. The required configuration can be seen in the right picture above.

The first thing we do is to keep track if a \(j\) node is assigned. For this we introduce new binary variables \(y_j\) and replace the second assignment constraint \(\sum_i x_{i,j} \le 1\) by:

\[\begin{align} &y_j = \sum_i x_{i,j}\\&y_j \in \{0,1\}\end{align}\]

The variable \(y_j\) will be zero for the unassigned nodes (grey in the picture above), and one if connected (red). We can make sure we don't have "holes" in the \(y\) vector by requiring that we see the pattern \([0,\> 1]\) only once. This we can model as:

\[\begin{align} &z_j \ge y_j - y_{j-1}\\& \sum_j z_j \le 1\\&z_j \in \{0,1\} \end{align}\]

This approach is often used in machine scheduling or power generation: prevent a generator to be turned on too many times.

This model has as results:

---- 44 VARIABLE x.L assignment variables j5 j6 j7 j8 j9 i1 1 i2 1 i3 1 i4 1 i5 1 ---- 44 VARIABLE y.L destination is used j5 1, j6 1, j7 1, j8 1, j9 1 ---- 44 VARIABLE z.L 0-1 transition j5 1

The complete GAMS model looks like:

Notes:

- The variables \(y\) and \(z\) can be relaxed to be continuous between zero and one.
- The \(x\) variables are no longer automatically integer valued. We need to solve this model as a real MIP and can not use just an LP solver.
- When using leads and lags we always have to look at the boundary case. Here we have the special case \(z_1 \ge y_1 - 0\). In GAMS when we index out-of-domain we get a zero. That is exactly what we need in this case.
- The problem can also be attacked by solving \(m-n+1\) assignment problems (and then pick the best one).

#### References

- Rainer Burkard, Mauro Dell'Amico, Silvano Martello,
*Assignment Problems*, SIAM, 2009 - Assignment problem, http://yetanothermathprogrammingconsultant.blogspot.com/2009/11/assignment-problem.html
- Combinatorial optimization: assignment (matching) with “consecutive” assignments, https://stackoverflow.com/questions/48049506/combinatorial-optimization-assignment-matching-with-consecutive-assignments

## No comments:

## Post a Comment