File Exchange

image thumbnail

Fast Linear Assignment Problem using Auction Algorithm (mex)

version 2.6.0.0 (5.7 KB) by Florian Bernard
Mex Implementation of Bertsekas' auction algorithm for solving the linear assignment problem

18 Downloads

Updated 01 Feb 2017

View License

Mex implementation of Bertsekas' auction algorithm [1] for a very fast solution of the linear assignment problem.
The implementation is optimised for sparse matrices where an element A(i,j) = 0 indicates that the pair (i,j) is not possible as assignment. Solving a sparse problem of size 950,000 by 950,000 with around 40,000,000 non-zero elements takes less than 8 mins. The method is also efficient for dense matrices, e.g. it can solve a 20,000 by 20,000 problem in less than 3.5 mins.
Both, the auction algorithm and the Kuhn-Munkres algorithm have worst-case time complexity of (roughly) O(N^3). However, the average-case time complexity of the auction algorithm is much better. Thus, in practice, with respect to running time, the auction algorithm outperforms the Kuhn-Munkres (or Hungarian) algorithm significantly.
When using this implementation in your work, in addition to [1], please cite our paper [2].

[1] Bertsekas, D.P. 1998. Network Optimization: Continuous and Discrete Models. Athena Scientific.
[2] Bernard, F., Vlassis, N., Gemmar, P., Husch, A., Thunberg, J., Goncalves, J. and Hertel, F. 2016. Fast correspondences for statistical shape models of brain structures. SPIE Medical Imaging, San Diego, CA, 2016.

The author would like to thank Guangning Tan for helpful feedback. If you want to use the Auction algorithm without Matlab, please check out Guangning Tan's C++ interface, available here: https://github.com/tgn3000/fastAuction .

Comments and Ratings (21)

fudong

fudong (view profile)

@Florian Bernard: I'm so appreciate for your suggestion~ This is my first time hearing about k-cardinality assignment problem, and the related works on k-LAP are very helpful to me.

@Fudong: The problem you want to solve is known as k-cardinality assignment problem. I suggest you check out "The k-cardinality assignment problem" (Dell'Amico & Martello, 1997) and follow-up works.

fudong

fudong (view profile)

@Florian Bernard:
Do you have any idea about solving a specific variant of LAP as follows: assign only k of the m persons (1<k<m) a proper job such that the total cost is minimized?
Namely, min z = sum_ij x_ij*c_ij, s.t. sum_j x_ij <= 1, sum_i x_ij <= 1, sum_ij x_ij = k (< m), where i = 1,..,m, j = 1,...,n, m <= n.
This problem can be solved by a linear programming solver, of course. Moreover, can it be solved by an improvement version of the Hungarian algorithm or the auction algorithm?

Hyoseung Kang

Came through Wikipedia.

fudong

fudong (view profile)

@Florian Bernard: Yes, you are right. This time I test scale values from 1 to 10^6 respectively. Larger scale value achieves better optimum while takes a little longer time.

@Fudong: Thanks a lot! When I run my code (see below) I achieve the same objective value as the Hungarian algorithm achieves. Have you made sure that you scale the input appropriately (as documented in the .m file and shown in the test() function therein).

I used the following code:
Ascaled = -A*10^6; % scale appropriately, use minus to make a benefit matrix from the cost matrix A
Ascaled = Ascaled - min(Ascaled)+1; % ensure that benefits are positive
[~, X] = sparseAssignmentProblemAuctionAlgorithm(Ascaled);

fudong

fudong (view profile)

@Florian Bernard:
A=0.3284 0.9926 0.1204 0.9133 0.8046 0.0906 0.0092 0.1624 0.0013 0.6293
0.1816 0.5427 0.4091 0.3121 0.1789 0.1114 0.1979 0.7627 0.8741 0.1436
0.5114 0.8758 0.3421 0.0098 0.7218 0.0577 0.9200 0.5581 0.8914 0.7092
0.7389 0.0078 0.2631 0.9785 0.6973 0.0965 0.3330 0.7415 0.1816 0.7842
0.2884 0.3933 0.4848 0.3790 0.3191 0.6244 0.1495 0.2723 0.4140 0.2276
0.6578 0.2537 0.0045 0.9220 0.2062 0.1739 0.3360 0.8244 0.6068 0.0654
0.4299 0.5241 0.4180 0.9536 0.0331 0.5241 0.9324 0.7244 0.5428 0.2428
0.5807 0.3906 0.5739 0.6941 0.3919 0.7941 0.4150 0.2567 0.1967 0.5740
0.2997 0.4018 0.8931 0.3856 0.0338 0.3221 0.2419 0.2101 0.2905 0.1191
0.5607 0.7032 0.7795 0.3133 0.6908 0.3426 0.7702 0.2282 0.6390 0.6351
The optimal values of min sum(sum(A.*X)) are: Hungarian = 1.0081, LAPJV = 1.0081, LP = 1.0081, this_code = 1.2537,
However, if we set B = floor(10*A), the optimal value of min sum(sum(B.*X)) is 6 for all methods.

@fudong: could you please provide an example problem along with the optimal solution that is obtained by the other methods, so that I can look into this?

fudong

fudong (view profile)

The solution obtained by this code is different from those by Hungarian/LAPJV/linear program. Moreover, its optimal value is a little bigger than optimal values of Hungarian/LAPJV/linear program.

Thank you.
Tested it on a 3000x3000 array.
works!

Windows SDK C++ does not have reserve as a member of std::unordered_map, so if using such a compiler then the line
objectToAssignmentIndex.reserve(n);
should be replaced by the equivalent
objectToAssignmentIndex.rehash(ceil(n / objectToAssignmentIndex.max_load_factor()));

Zorah Lähner

ary die

@Murat Uney: yes, the current code is tailored towards symmetric problems.

Dmitry

Dmitry (view profile)

Murat Uney

I suppose this version is particularly for NxN problems with the MxN variant being the forward-reverse auction* not covered by this function, is that right?
(*) Bertsekas, Castanon, "A forward/reverse auction algorithm for asymmetric assignment problems," Computational Optimization and Applications
December 1992, Volume 1, Issue 3, pp 277–297.

ws86406

bugfix related to the epsilon heuristic

Guangning Tan

I appreciate the author's constant and timely support. Very nice code. Thank you!

Evan Oman

Fantastic! There are far too few Auction Algorithm implementations available online(besides Bertsekas' Fortran version). Your code is readable, efficient, and exactly what I was looking for.

Thanks!

Updates

2.6.0.0

- use of dmperm() to perform fast feasibility check
- added reference to C++ interface

2.4.0.0

- improved performance for very large sparse matrices
- added feasibility check

2.2.0.0

bugfix (concerned benefit matrices where for some of the rows exactly one assignment is allowed, thanks to Gary Guangning Tan for pointing out this problem)

2.1.0.0

bugfix related to the epsilon heuristic (2)

2.1.0.0

bugfix related to the epsilon heuristic

2.0.0.0

updated description

2.0.0.0

- mex implementation, which leads to a significant performance improvement
- support for sparse matrices

1.2.0.0

.

1.1.0.0

.

MATLAB Release Compatibility
Created with R2016a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Discover Live Editor

Create scripts with code, output, and formatted text in a single executable document.


Learn About Live Editor