Stores the solution of an assigment problem

Can be directly used to index the appropriate values from the cost matrix

findbestassignment(C, maximize=false) = solution

Solve the two-dimensional assignment problem with a rectangular cost matrix C, scanning row-wise.

Note that cost returned can overflow if using smaller integer types

Example

julia> M=rand(1:100,3,4)
3×4 Matrix{Int64}:
 77  51  42  67
 72  53  47   4
 24  50  77  96

 julia> sol = find_best_assignment(M)
 AssignmentSolution(CartesianIndex.(1:3, [3, 4, 1]), 70)
 
 julia> sum(M[sol])
 70
 
 julia> max_sol = find_best_assignment(M', true)
 AssignmentSolution(CartesianIndex.([1, 2, 4], 1:3), 226)

This code is a port of Matlab code released [1] in the public domain by the US Naval Research Laboratory.

This work is not affliated or endorsed by the Naval Research Laboratory.

The algorithm is described in detail in D. F. Crouse, "Advances in displaying uncertain estimates of multiple targets," in Proceedings of SPIE: Signal Processing, Sensor Fusion, and Target Recognition XXII, vol. 8745, Baltimore, MD, Apr. 2013.

REFERENCES: [1] D. F. Crouse, "The Tracker Component Library: Free Routines for Rapid Prototyping," IEEE Aerospace and Electronic Systems Magazine, vol. 32, no. 5, pp. 18-27, May. 2017

findkbestassignments(C, k, maximize=false) -> kbest_sols

Find the k lowest [or highest] cost 2D assignments for the two-dimensional assignment problem with a rectangular cost matrix C.

Example

julia> M=rand(1:100,3,4)
3×4 Matrix{Int64}:
 77  51  42  67
 72  53  47   4
 24  50  77  96

 julia> sols = find_kbest_assigments(M, 5)
 5-element Vector{Assignment.AssignmentSolution{Int64, Int64}}:
  AssignmentSolution(CartesianIndex.(1:3, [3, 4, 1]), 70)
  AssignmentSolution(CartesianIndex.(1:3, [2, 4, 1]), 79)
  AssignmentSolution(CartesianIndex.(1:3, [3, 4, 2]), 96)
  AssignmentSolution(CartesianIndex.(1:3, [3, 2, 1]), 119)
  AssignmentSolution(CartesianIndex.(1:3, [2, 3, 1]), 122)
  
 julia> max_sols = find_kbest_assignments(M, 5, true)
 5-element Vector{Assignment.AssignmentSolution{Int64, Int64}}:
  AssignmentSolution(CartesianIndex.(1:3, [1, 2, 4]), 226)
  AssignmentSolution(CartesianIndex.(1:3, [1, 3, 4]), 220)
  AssignmentSolution(CartesianIndex.(1:3, [2, 1, 4]), 219)
  AssignmentSolution(CartesianIndex.(1:3, [4, 1, 3]), 216)
  AssignmentSolution(CartesianIndex.(1:3, [3, 1, 4]), 210)

This is an implementation of Murty's method, which is described in [1]. The algorithm relies on the existence of a 2D assignment algorithm. The 2D assignment algorithm of [2] is used. Additionally, the dual variable inheritance methods described in [3] is used to reduce the computational complexity of the technique.

Murty's algorithm runs 2D assignment algorithms a number of times with an increasing number of constraints. Instances of MurtyData are stored in an ordered list implemented using the BinaryMinHeap class.

This code is a port of Matlab code released in the public domain by the US Naval Research Laboratory [4].

This work is not affliated or endorsed by the Naval Research Laboratory.

References

[1] K. G. Murty, "An algorithm for ranking all the assignments in order of increasing cost;" Operations Research; vol. 16; no. 3; pp. 682-687 May-Jun. 1968. [2] D. F. Crouse, "On Implementing 2D Rectangular Assignment Algorithms," IEEE Transactions on Aerospace & Electronic Systems; vol. 52; no. 4 pp. 1679-1696; Aug. 2016. [3] M. L. Miller, H. S. Stone, & J. Cox, Ingemar, "Optimizing Murty's ranked assignment method;" IEEE Transactions on Aerospace & Electronic Systems; vol. 33; no. 3; pp. 851-862; Jul. 1997. [4] D. F. Crouse, "The Tracker Component Library: Free Routines for Rapid Prototyping," IEEE Aerospace and Electronic Systems Magazine, vol. 32, no. 5, pp. 18-27, May. 2017

October 2013 David F. Crouse; Naval Research Laboratory; Washington D.C. (UNCLASSIFIED) DISTRIBUTION STATEMENT A. Approved for public release.