File Exchange

Functions for the rectangular assignment problem

version 1.5.0.0 (18.7 KB) by
This package provides m- and mex-functions for solving the rectangular assignment problem.

Updated 17 Mar 2014

View Version History

With this package, I provide some MATLAB-functions regarding the rectangular assignment problem. This problem appears for example in tracking applications, where one has M existing tracks and N new measurements. For each possible assignment, a cost or distance is computed. All cost values form a matrix, where the row index corresponds to the tracks and the column index corresponds to the measurements. The provided functions return an optimal or suboptimal assignment - in the sense of minimum overall costs - for the given matrix.
In the process of gating, typically very unlikely assignments are forbidden. The given functions can handle forbidden assignments, which are marked by setting the corresponding assignment cost to infinity.
The optimal solution is computed using Munkres algorithm, also known as Hungarian Algorithm.

The functions are called like
[assignment, cost] = assignmentalgorithm(distMatrix);

Cite As

Markus Buehren (2020). Functions for the rectangular assignment problem (https://www.mathworks.com/matlabcentral/fileexchange/6543-functions-for-the-rectangular-assignment-problem), MATLAB Central File Exchange. Retrieved .

James Heald

Markus Buehren

It's not a bug, it's a feature :-) The functions containing "suboptimal" in their name are a lot faster but do not always return the optimal solution.

yu xianguo

Bug found! When testing distMatrix=[29,80,75,90,65; 87,91,22,16,45; 34,75,42,95,43; 15,20,63,81,67; 78,59,8,83,45; 86,78,7,100,93]; Function assignmentsuboptimal1 & assignmentsuboptimal2 outputs the assignment [0 4 5 1 2 3] with total cost=140. While the optimal assignment should be [1 4 5 2 0 3] with total cost=115.

kerwin shi

thank you very much

Huang ming

Thank you

Aleksejs Fomins

Absolutely amazing work. I especially appreciate the forbidden arguments - it is typical in my application that some pairings are too bad to consider, and because of that some tracks and some measurements will naturally have no good pair at all.

amir zamani

Peyruz Gasimov

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

Jacob Mevorach

Any Idea how I might find unassignedDetections and unassignedTracks after finding assignments?

Julian Schork

Alex Nikitin

Uubu

Shan Muga

Xin Liu

Matteo

Hi people,
I a question about the hungarian algorithm. this algorithm is optimal algorithm for the assignment problem, and the time complexity is O(n^3), right?
But , if the input is the multidimensional matrix, it's possible to use the hungarian algorithm? how does it change the algorithm and the time complexity ?
thanks

Charles Nelatury

Michal Kvasnicka

Excellent piece of work!

Thanks to guys like Markus MATLAB is the best computing environment in the world!

Markus, could you add to the readme file releveant references (Munkres, Hungarian algorithms, assigment problem in general)?

Umit

Is 'assignmentoptimal(rectMatrix)' is the implementation of Munkres algorithm for rectangular case? It says it is Munkres algorithm but original algorithm is for square matrices. This one should be extended version for rectangular cases, right? Can you confirm this.

Yu

It is very useful for me, especially can handle rectangle situation. Thanks a lot!

Yu

yair

Hello Markus.

Is it a O(n^3) implementaion?

James

Great work

Andy

Nazmul Islam

Nazmul Islam

Thanks a lot for posting this !! I am looking for a Matlab implementation of a maximum weighted matching algorithm in a general graph (not bipartite). Does anyone know a Mathworks thread/link where it has already been posted?

Olivier Planchon

Excellent !
I especially like the easy-to-use MEX files, and the outstanding test file.
I could optimize my problem beyond my best hope.

Bruno Luong

Great, does what it claims and fast (I use for multi-target tracking.)

michele pace

Hi, I used assignmentoptimal.* in a multitracking application, exactly in the scenario you described. It works very well. Great job, thank you.

Greg Fricke

Thank you Markus!
This has helped me pass a critical practicality hurdle in my Master's Research without spending a week or two reading, writing, and debugging!

Clemens Yu

Harrison Woods

Great, thanks for sharing this code!!

Salha Al-Kuwaiti

Perfect! Keep the good work Up!

Leonid Chindelevitch

You saved me a lot of trouble, thank you!

Stephen Pan

Excellent!

Francois Berthiaume

Francois Berthiaume

Many thanks for the code, it works great!

Markus Buehren

Ldd Lasss, please let me know why you gave a bad rating for my package!

Ldd Lasss

Tom Pinkiewicz

Thanks Markus. This code works great. I re-packaged your c function and integrated it into Simulink. I've posted it on this website.

Tom Pinkiewicz

Thanks Markus. This code works great. I re-packaged your c function and integrated it into Simulink. I've posted it on this website.

Hao Cheng

Very nice work. I do appreciate.

A Alpers

praveen kuppili

very good one!!!!!!!

Coffee Bear

very fast

Tium Tium

works great, easy to use

Raimund Leitner

Very very good and easy to use implementation of the Munkres algorithm.

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