Sunday, April 8, 2018

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:

nn!
5120
103628800
100933262154439441526816992388562667004
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/MaxObjectiveIterationsNodesTotal Time (GAMS+Solver)
Minimization16.331
16.392
16.403
196
208
209
0
1
1
1.7 seconds
Maximization983.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/MaxObjectiveIterationsNodesTotal Time (GAMS+Solver)
Minimization16.331
16.392
16.403
580926916.2 seconds
Maximization983.015
982.997
982.980
736900414.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

1 comment:

  1. You might be interested in this paper that illustrates several methods, including Murty's algorithm (which solves smaller linear assignment problems as subroutines): https://support.sas.com/resources/papers/proceedings16/SAS3161-2016.pdf

    ReplyDelete