Men's K-2 1000 metres medalist at the 1960 Summer Olympics in Rome |

Find the \(k\) best solutions for an assignment problem [1]

The answer can be complicated [2].

#### Assignment Problem

A second observation is that complete enumeration of all possible solutions is not feasible. If \(n\) is the size of the problem (i.e., \(n\) = number source nodes = number of destination nodes), we have \(n!\) possible solutions. The next table always amazes me:

n | n! |
---|---|

5 | 120 |

10 | 3628800 |

100 | 933262154439441526816992388562667004 907159682643816214685929638952175999 932299156089414639761565182862536979 208272237582511852109168640000000000 00000000000000 |

An \(n=100\) assignment problem is considered small, but this number \(100!\) should give you pause.

#### Lo-Tech Approach

The simplest approach is to add a cut to forbid a previously found solution, and solve again. If we record optimal solutions of round \(k\) in \(\alpha_{k,i,j} := x^*_{i,j}\), then this cut can be written as:\[\sum_{i,j} \alpha_{k,i,j} x_{i,j} \le n-1\] I.e. we need to solve MIP models of the form\[\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\\&\sum_{i,j} \alpha_{k,i,j} x_{i,j} \le n-1 &\forall k\\&x_{i,j}\in \{0,1\}\end{align}}\]Note that we no longer can assume we can solve this as an LP as we destroyed the network structure by adding the cuts.

For a problem with say \(k=3\) and \(n=100\) this looks like a perfectly suitable approach. I do minimization and maximization so we get two observations. I see:

Min/Max | Objective | Iterations | Nodes | Total Time (GAMS+Solver) |
---|---|---|---|---|

Minimization | 16.331 16.392 16.403 | 196 208 209 | 0 1 1 | 1.7 seconds |

Maximization | 983.015 982.997 982.980 | 251 296 320 | 0 1 1 | 1.8 seconds |

These models solve easily (especially after being scared to death by this number \(100!\)).

There is a number of advantages using this approach:

- It is very simple, and works with any MIP solver or modeling system.
- The cuts are linear and don't add any variables to the model. A single cut is needed to exclude a single solution.
- The problems can be solved with full presolving (some other methods require reducing presolve levels). Some problems are heavily affected by this.

#### Hi-Tech Approach

Some solvers have built-in a tool called the "

**solution pool**". This allows us to do this in one swoop. There is some heavy machinery behind this tool [3]. The results with Gurobi are:

Min/Max | Objective | Iterations | Nodes | Total Time (GAMS+Solver) |
---|---|---|---|---|

Minimization | 16.331 16.392 16.403 | 580 | 9269 | 16.2 seconds |

Maximization | 983.015 982.997 982.980 | 736 | 9004 | 14.0 seconds |

Notes:

- Interestingly our lo-tech approach outperforms the solution pool by a large margin: lo-tech is almost 10 times as fast. Of course, for difficult MIP models this will likely not be the case.
- The
**Gurobi**pool settings were:*PoolSearchMode=2 (k-best), PoolSolutions=3*. - I believe the
**Cplex**implementation of the solution pool does not allow to search for the \(k\) best solutions [2]. The pool settings*SolnPoolReplace=1, SolnPoolIntensity=4, SolnPoolCapacity=3*look promising, but they don't give the three best solutions. **Xpress**also has a solution pool. It supports finding the \(k\) best solutions, although some real effort from the modeler is needed (need to turn off a bunch of heuristic and presolve options [4]).

To be complete, I want to mention: there are specialized implementations for the \(k\)-best assignment problem (e.g. [5,6]).

#### References

- JGraphT: getting ranked solutions from e.g. KuhnMunkresMinimalWeightBipartitePerfectMatching, https://stackoverflow.com/questions/49694736/jgrapht-getting-ranked-solutions-from-e-g-kuhnmunkresminimalweightbipartiteper
- Paul Rubin, K Best Solutions, https://orinanobworld.blogspot.com/2012/04/k-best-solutions.html
- Danna E., Fenelon M., Gu Z., Wunderling R. (2007) Generating Multiple Solutions for Mixed Integer Programming Problems. In: Fischetti M., Williamson D.P. (eds) Integer Programming and Combinatorial Optimization. IPCO 2007. Lecture Notes in Computer Science, vol 4513. Springer, Berlin, Heidelberg
- FICO, MIP Solution Pool, Reference Manual, Release 31.01, https://www.msi-jp.com/xpress/learning/square/02-mipsolpool.pdf
- C.R. Pedersen, L.R. Nielsen, K.A. Andersen, An algorithm for ranking assignments using reoptimization, Computers & Operations Research, 35 (11) (2008), pp. 3714-3726
- M.L. Miller, H.S. Stone, I.J. Cox, Optimizing Murty's ranked assignment method, IEEE Transactions on Aerospace and Electronic Systems, 33 (1997), pp. 851-862

## No comments:

## Post a Comment