K best solutions for an assignment problem

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

The problem is simple:

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

The answer can be complicated [2].

Assignment Problem

The assignment problem is somewhat special: even for large problems LP solvers can solve this problem very quickly. When writing your own version of the Hungarian algorithm, it is likely to be slower than a good LP solver.

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

1. JGraphT: getting ranked solutions from e.g. KuhnMunkresMinimalWeightBipartitePerfectMatching, https://stackoverflow.com/questions/49694736/jgrapht-getting-ranked-solutions-from-e-g-kuhnmunkresminimalweightbipartiteper
2. Paul Rubin, K Best Solutions, https://orinanobworld.blogspot.com/2012/04/k-best-solutions.html
3. 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
4. FICO, MIP Solution Pool, Reference Manual, Release 31.01, https://www.msi-jp.com/xpress/learning/square/02-mipsolpool.pdf
5. 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
6. 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