Code covered by the BSD License  

Highlights from
LAPJV - Jonker-Volgenant Algorithm for Linear Assignment Problem V3.0

4.875
4.9 | 16 ratings Rate this file 37 Downloads (last 30 days) File Size: 4.35 KB File ID: #26836

LAPJV - Jonker-Volgenant Algorithm for Linear Assignment Problem V3.0

by

Yi Cao (view profile)

 

03 Mar 2010 (Updated )

A Matlab implementation of the Jonker-Volgenant algorithm solving LAPs.

| Watch this File

File Information
Description

The Jonker-Volgenant algorithm is much faster than the famous Hungarian algorithm for the Linear Assignment Problem (LAP). This Matlab implementation is modified from the original C++ code made by Roy Jonker, one of the inventors of the algorithm. It is about 10 times faster than the munkres code (v2.2) of the author. It can solve a 1000 x 1000 problem in about 3 seconds in a normal Intel Centrino processor.

V1.1 returns the dual variables and the reduced cost matrix as well.
V1.2 can deal with nonsquare assignment problems.
V2.0 is faster for problems with a large range of costs.
V2.1 includes an option to change the cost resolution to improve performance for some problems.
v2.2 removes a small bug to avoid NAN for 1x1 case.
v2.3 removes a small bug to handle a cost matrix with all inf's.
v2.4 fixes a bug associated with resolution to address the known problem of the algorithm.
v3.0 fixes a bug introduced since v2.0.
Reference:
R. Jonker and A. Volgenant, "A shortest augmenting path algorithm for dense and spare linear assignment problems", Computing, Vol. 38, pp. 325-340, 1987.

Acknowledgements

Munkres Assignment Algorithm and Hungarian Algorithm For Linear Assignment Problems (V2.3) inspired this file.

This file inspired K Best Assignment Algorithm and Faster Jonker Volgenant Assignment Algorithm.

MATLAB release MATLAB 7.10 (R2010a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (48)
16 Feb 2015 Bill Otto

Jay, you should have picked a cost matrix with a unique solution. Magic(90) has several solutions all with a cost of 134460. You should verify this by checking the cost from several different algorithms. Bottom-line: Lapjv v. 3.0 is giving a correct solution, it is just not flagging it as non-unique. Bill

Comment only
22 Aug 2014 Jay

Jay (view profile)

Granted I ran this in Octave but I'm fairly certain it gave me an incorrect alignment using the following code "px = lapjv(magic(90))"

The result was
px =

Columns 1 through 31: (Note: beware of line wrapping)

72 23 73 74 75 76 77 78 79 71 24 88 86 84 85 83 87 82 89 90 81 80 1 45 44 43 42 41 40 39 38

Columns 32 through 62:

37 36 35 34 33 32 31 30 29 28 27 26 70 25 68 22 21 67 66 18 20 65 64 19 63 57 62 17 61 16 60

Columns 63 through 90:

15 59 14 58 13 46 12 56 11 10 55 54 9 53 8 52 7 51 6 50 5 49 4 3 48 47 2 69

When it should have been this (obtained in R using GraphAlignment package LinearAssignment function)

> px1
Cols 1 through 37 (Again Note: beware of line wrapping)
23 89 87 84 82 80 78 76 74 73 71 69 66 64 62 61 58 56 54 52 50 49 2 11 45 10 1 3 4 5 6 7 8 9 22 21 18

Cols 38 through 74
16 14 15 13 17 12 19 20 68 88 86 85 83 81 79 77 75 72 70 57 67 65 63 60 59 51 55 53 48 47 46 90 44 43 42 41 40

Cols 75 through 90
39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24

08 Jan 2014 pang kuo

great!

10 Jun 2013 Don Natale

Hi Yi,

I'm running the example you have in the comments of your code:

% Example 2: 1000 x 1000 random data
%{
n=1000;
A=randn(n)./rand(n);
tic
[a,b]=lapjv(A);
toc % about 0.5 seconds
%}

And it's taking substantially longer than a few seconds to solve, more like 40 seconds. This is on a fairly new Intel core i5-2400 3.10GHz processor with 64-bit Windows 7 and 16 Gb RAM.

In your great amount of experience optimizing your code here, could you suggest a reason why this may be taking so long to compute?

Comment only
22 Apr 2013 Fabio

Fabio (view profile)

Hi,
This code looks very interesting.
I am using v3.0 and I possibly hit a bug/problem. It seems to me that, for different cost matrices (coming from the underlying problem with a varying size) the solution switches between being in row mode and col mode.
I don't see any parameter/switch to control this behavior, is it intended to be like that? how can I get the solution always in term of e.g. col indices? Fabio

Comment only
11 Apr 2013 Bill Otto

v3.0 seems to give correct result every time, with a 4x speed advantage over Munkres for a 100 by 100 matrix. Thanks for the great routine, Yi.

05 Apr 2013 Bill Otto

Yi, It seems to fail for 2x2 (0.0022% of the time) and 3x3 cost matrices about 0.014% of random cases. For 4x4, it hasn't failed in over 1 million cases, but that doesn't mean that it won't in some larger sample. That means it's a real tough bug to track down, I would guess. Bill

Comment only
05 Apr 2013 Bill Otto

Yi, I have tried Jen's example below, and it appears to be a bona fide bug. Bill

Comment only
13 Jan 2013 Jacob

Jacob (view profile)

I have the following error, can anybody help me here?

??? Error: File: lapjv.m Line: 146 Column: 7
Expression or statement is incorrect--possibly unbalanced (, {, or [.

Comment only
26 Oct 2012 Jen

Jen (view profile)

It seems like the code returns the wrong solution for this cost matrix:

costs =
[0.2593 0.0697 0.7715;
0.1671 0.3699 0.0671;
0.1117 0.1462 0.0611]

[a, b] = lapjv(costs);
a = [2 1 3]
b = 0.2979

The correct solution would be a = [2 3 1] with b = 0.2486.

Comment only
25 Sep 2012 Kristofer Kusano

Thanks for the post, this worked great.

02 Jul 2012 joshua vogelstein

this is a really great piece of code, thanks!
i noticed that "Faster Jonker-Volgenant Assignment Algorithm" seems to have a nice feature which is not yet implemented in this version? do you have plans to include it? many thanks, joshua

20 Jun 2012 Ming

Ming (view profile)

Great

06 May 2012 Yi Cao

Yi Cao (view profile)

Thank you Dmitri, the bug has been fixed now.

Yi

Comment only
03 May 2012 Dmitri Kamenetsky

I think I found a bug in lapjv when Inf values are used. In the following lapjv gives the wrong answer (compared to munkres):

A=magic(5);
A(1,3)=Inf
[munkresAssignment munkresCost]=munkres(A)
[lapjvAssignment lapjvCost]=lapjv(A)

The problem goes away when Inf is replaced with a large value:

A(1,3)=1000
[munkresAssignment munkresCost]=munkres(A)
[lapjvAssignment lapjvCost]=lapjv(A)

25 May 2011 Andy

Andy (view profile)

My post was deleted somehow

I am having a problem with bad assignments. The data I am using is two sets of 8x2 centroids specified by (row,col). The first set is measured data and tsecond data is predicted via alpha-beta filter. I using the assignemtn algorithm to match up masured data with existing filter pipelines, but even for a simple scenario such as:

meas =
[122.9178,122.9178;122.9178,202.9178;0,0;0,0;0,0;0,0;0,0;0,0];
pred =
[122.4879,121.0182;0,0;0,0;0,0;0,0;0,0;0,0;0,0];

i get
rowsol = [2;3;6;7;8;1;4;5],

wich is obviously not right. Even with Munkres i get
rowsol_munkres = [2;1;3;4;5;6;7;8],

which is still off.

Any suggestions?

Comment only
25 May 2011 Andy

Andy (view profile)

Sorry here is the costmat code:

costMat = zeros(n,n);

%Populate nxn error matrix
%--------------------------------
for j = 1:n
for k = 1:n
costMat(j,k) = ( x_pred(j)-x_meas(k) )^2 + ( y_pred(j)-y_meas(k) )^2;
end
end

Comment only
22 Mar 2011 Eric Trautmann

Eric Trautmann (view profile)

I've been using both of your Munkres and JV LAP algorithm implementations. JV is much faster for a single matrix, as expected, but I also found that when I used the JV algorithm within the Murty k-best assignment algorithm, it was much slower than your implementation of Munkres. When I dug into this, I found that the JV implementation does not cull out rows or columns all marked as inf. When I made this modification (copied the validRow/validCols lines from munkres.m), it sped up the algorithm by a factor of ~7.

Comment only
14 Jan 2011 Andrew McFarland

Alexander,
Thanks for the help...I tried this out and it did help a lot, but it is still taking much longer with my dataset (for example, 80X80 cost matrix takes ~150 seconds to solve) vs the example ones. Any ideas--maybe normalizing of some sort?

Comment only
14 Jan 2011 Alexander Kosenkov

Andrew McFarland, you should specify second parameter - minimum resoulution for your data. If several values are very close to each other, then it hangs because of a minor bug in programming.

I made a patch to the function - originally EPS function was used incorrectly. I hope, Mr. Cao will fix this in next releases.

Index: lapjv.m
@@ -68,7 +68,7 @@
if nargin<2
- resolution=eps;
+ resolution=4 * eps(max(max(A)));
end
@@ -164,7 +164,7 @@
i0 = colsol(j1);
- if usubmin - umin > eps
+ if usubmin - umin > resolution
% change the reduction of the minmum column to increase the

14 Jan 2011 Andrew McFarland

Great code--I have found some interesting behavior. When I run the "standard" examples like A=rand(1000,1000) for the cost matrix, solves in seconds. However, I have an assignment problem (for PCB assignment) and when I run a 500X500 cost matrix it takes more than a day to solve. I have tried scaling the matrix values and also randomly shuffling the matrix elements and still doesn't reduce the solver time. Is there something inherent in the structure of the cost matrix that can cause the solution to take longer??

Comment only
19 Nov 2010 KS

KS (view profile)

 
19 Nov 2010 Yi Cao

Yi Cao (view profile)

KS,

The code is updated with more clear explaination. Wish this helps.

Yi

Comment only
12 Nov 2010 KS

KS (view profile)

What does N stand for in the function parameters? Thanks.

Comment only
10 Nov 2010 Yi Cao

Yi Cao (view profile)

Roberto,

Thanks for pointing this out. Initially, a full Inf cost matrix is not considered. Now, this has been corrected in v2.3.

Yi

Comment only
10 Nov 2010 Roberto Olmi

I've noticed a little bug for scalar input Inf ( lapjv(inf) ). The error occurs at line 85.

Comment only
10 Nov 2010 Roberto Olmi

Very usefull code!! Compared to the version 1.1 the version 2.2 seems to be also capable to manage Inf values in the cost matrix. Yi, is it correct?

14 Oct 2010 Jiangmin zhang

i think matlab should take this code into itself as a build-in function

18 Aug 2010 Amir

Amir (view profile)

anyone has lapjv v1.2?

Comment only
18 Aug 2010 Immanuel Weber

Hi Yi,
that was fast! Okay, that's the solution I want to avoid, as the task in my case is very time critical and resizing an existing 2d array appears to be very unattractive. But nevertheless thanks for your information and your good code.

Immanuel

Comment only
17 Aug 2010 Yi Cao

Yi Cao (view profile)

Immanuel,

Thanks for pointing out the bug. It has been removed in v2.2. In terms of rectangular matriices, I did not know these two references you mentioned. I just used a simple approach to fill the cost matrix with zeros to square it.

Yi

Comment only
17 Aug 2010 Immanuel Weber

Hi Yi,
as I used your Hungarian-Code before and I want to implement Jonkers&Volgenant's algorithm for rectangular matrices in C, your code was a nice finding. Do you use any of the algorithm modifications presented in Volgenant's papers "Linear and semi-assignment problems, a core oriented approach"[1996] and/or "Solving the Rectangular assignment problem and applications"[2010] to solve rectangular matrices? Or do you use a different, maybe simplier to understand approach?
I'm trying to implement the modifications presented in the last one, but I'm having difficulties with some of the lines in the pseudo code.
In addition I want to point out a little bug, which rarely will occur, but if you use 1x1 matrix as an input for your code, it will compute a NaN cost.

Immanuel

13 Aug 2010 Yi Cao

Yi Cao (view profile)

Hi, Kishore,

No, this is not an error. This is a new feature of Matlab since 2009(a?), which indicates that the corresponding output arguments are not needed. If you use an older version, you need to replace ~ with a dummy variable.

Yi

Comment only
12 Aug 2010 Kishore Mosaliganti

Hi,

There is an error in line 85 in the downloaded code. It is not running.
[~,c]=min(v1);

Should the ~ be r ?

27 Jul 2010 Amir

Amir (view profile)

it is a wonderful code. I have some questions which directly or indirectly are related to your code. I would really appreciate if you could find some time and answer my questions:

1. If I want to exclude some assignments such as i-->i assignment, I consider Cii as Big-M. Does the value of Big-M affect the computing time? What is the best value?
2. If I have a matrix whose elements are random integers from the following interval [0 10000] and another one whose elements are from [0 100], does the computing time differ? My experience is that the first one is lengthier.
3. Do you have any experience working with a sparse matrix?
Everybody claims the computing time has to decrease. However, I have a different experience. It remains more or less the same. I think the main reason can be referred to the above item. I think solving a matrix with larger element with LAPJV is lengthier.
4. Can I have negative elements?
5. Is LAPJV v1.1 faster than LAPJV v1.2? Because, in that one you don't calculate dual variables and reduced cost matrix.

24 Jul 2010 Chaoran Du

Hi Yi, I've got the m-file, thanks a lot!!!

Chaoran

Comment only
23 Jul 2010 Yi Cao

Yi Cao (view profile)

Chaoran,

The page has not been updated. You can check the 'updates' list for another 22 Jul 2010 item to ensure the file has been updated.

Yi

Comment only
23 Jul 2010 Chaoran Du

Hi Yi,

I still can't download the updated version and I don't know if there is something wrong here. Do you mind email me the updated m-file? Thank you very much for all your help!

Email: C.Du@ed.ac.uk

Comment only
22 Jul 2010 Yi Cao

Yi Cao (view profile)

Chaoran,

I reloaded the file now. Wish this time it works.

Yi

Comment only
22 Jul 2010 Chaoran Du

Yi, I download the file but the m-file is the same as V1.1, and it shows that the m-file was modified on 19th July while license.txt was modified today. Could you please check the file?

Really appreciate all your help!

Chaoran

Comment only
22 Jul 2010 Yi Cao

Yi Cao (view profile)

Chaoran,

Yes, it has been posted and should be online within a day.

Yi

Comment only
22 Jul 2010 Chaoran Du

Fantastic!
But I can't find V1.2, have you posted it yet?
Thanks again for all your help!

Chaoran

Comment only
22 Jul 2010 Yi Cao

Yi Cao (view profile)

Chaoran,

The new version (V1.2) has the ability to deal with nonsquare cases.

Yi

Comment only
21 Jul 2010 Chaoran Du

Thank you for your code. Its really useful.
Do you know how to solve an asymmetric assignment problem by using the Jonker-Volgenant algorithm? (assign n people to m jobs and n<m)

Comment only
20 Jul 2010 Yi Cao

Yi Cao (view profile)

Amir,

In the new version (V1.1), dual variables are returned.

Yi

Comment only
05 Jul 2010 Amir

Amir (view profile)

it is a great code. how can i get the dual variables?

Comment only
05 Jul 2010 Amir Hossein  
12 Apr 2010 Turkay YILDIZ

Thank you. Great algorithm and matlab code. I would also very much like to see this algorithm's solution for TSP and other problems, if it's possible.

Updates
04 Mar 2010

update descriptions

31 Mar 2010

a bug fixed

19 Jul 2010

Version 1.1 returns dual variables and reduced cost matrix

22 Jul 2010

V1.2 is able to deal with nonsquare cases.

22 Jul 2010

update the file

28 Jul 2010

V2.0 is faster for problems with a large range of cost values.

13 Aug 2010

option to change cost resolution.

17 Aug 2010

v2.2 removes a small bug to avoid NAN for 1x1 case.

10 Nov 2010

Removes a small bug to handle a cost matrix with all inf's.

18 Nov 2010

update description

16 Jan 2011

Big fix

07 May 2012

A bugg fix

11 Apr 2013

A bug introduced since v2.0 is fixed

Contact us