munkres' assignment algorithm modified for rectangular matrices

An extension of the Munkres algorithm for the assignment problem to rectangular matrices

Hacker News
Download PDF
Join the Discussion
View in the ACM Digital Library

The assignment problem, together with Munkres proposed algorithm for its solution in square matrices, is presented first. Then the authors develop an extension of this algorithm which permits a solution for rectangular matrices. Timing results obtained by using an adapted version of Silver's Algol procedure are discussed, and a relation between solution time and problem size is given.

View this article in the ACM Digital Library.

Submit an Article to CACM

CACM welcomes unsolicited submissions on topics of relevance and value to the computing community.

You Just Read

December 1971 Issue

Published: December 1, 1971

Vol. 14 No. 12

Pages: 802-804

munkres' assignment algorithm modified for rectangular matrices

Join the Discussion (0)

Become a member or sign in to post a comment, the latest from cacm.

Building Computing Systems for Embodied Artificial Intelligence

First Impressions: Designing Social Actions for Positive Social Change with Bard

Evergreen State College professor emeritus Douglas Schuler

The Artist’s Role on a Science and Engineering Campus

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres' algorithm

Published: September 1979
Volume 19 , pages 418–424, ( 1979 )

Cite this article

Jin Kue Wong 1 nAff2

257 Accesses

13 Citations

Explore all metrics

Existing implementations of Munkres' algorithm for the optimal assignment problem are shown to require O ( n 4 ) time in the worst n × n case. A new implementation is presented which runs in worst-case time O ( n 3 ) and compares favorably in performance with the algorithm of Edmonds and Karp for this problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems , JACM 19:2 (April 1972), 248–264.

Article Google Scholar

L. R. Ford, Jr. and D. R. Fulkerson, Flows in Networks , Princeton University Press, (1962), 53–55.

L. R. Kerr, The effect of algebraic structure on the computational complexity of matrix multiplication , (Ph.D. thesis), Cornell Univ., June 1970.

J. Munkres, Algorithms for the assignment and transportation problems , J. SIAM 5:1 (March 1957), 32–38.

Google Scholar

R. Silver, An algorithm for the assignment problem , Comm. ACM 3:11, (Nov. 1960), 605–606.

Download references

Author information

Jin Kue Wong

Present address: Department of Computer Science, University of Ottawa, Kin 6N5, Ottawa, Ontario, Canada

Authors and Affiliations

Department of Systems & Information Science, Vanderbilt University, 37235, Nashville, Tennessee, U.S.A.

You can also search for this author in PubMed Google Scholar

Additional information

The results of this paper were obtained by the author while at the Department of Computer Science, Cornell University. This work was supported in part by a Vanderbilt University Research Council Grant.

Rights and permissions

Reprints and permissions

About this article

Wong, J.K. A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres' algorithm. BIT 19 , 418–424 (1979). https://doi.org/10.1007/BF01930994

Download citation

Received : 22 November 1978

Issue Date : September 1979

DOI : https://doi.org/10.1007/BF01930994

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

Keywords and phrases

Optimal assignment problem
worst-case time
analysis of algorithms

CR categories

Find a journal
Publish with us
Track your research

Introduction

Assignment problem.

Let C be an n by n matrix representing the costs of each of n workers to perform any of n jobs. The assignment problem is to assign jobs to workers in a way that minimizes the total cost. Since each worker can perform only one job and each job can be assigned to only one worker the assignments represent an independent set of the matrix C .

One way to generate the optimal set is to create all permutations of the indexes necessary to traverse the matrix so that no row and column are used more than once. For instance, given this matrix (expressed in Python):

You could use this code to generate the traversal indexes:

After the call to permute(), the results matrix would look like this:

You could then use that index matrix to loop over the original cost matrix and calculate the smallest cost of the combinations:

While this approach works fine for small matrices, it does not scale. It executes in O( n !) time: Calculating the permutations for an n x n matrix requires n ! operations. For a 12x12 matrix, that’s 479,001,600 traversals. Even if you could manage to perform each traversal in just one millisecond, it would still take more than 133 hours to perform the entire traversal. A 20x20 matrix would take 2,432,902,008,176,640,000 operations. At an optimistic millisecond per operation, that’s more than 77 million years.

The Munkres algorithm runs in O( n ^3) time, rather than O( n !). This package provides an implementation of that algorithm.

This version is based on http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html

This version was written for Python by Brian Clapper from the algorithm at the above web site. (The Algorithm:Munkres Perl version, in CPAN, was clearly adapted from the same web site.)

Construct a Munkres object:

Then use it to compute the lowest cost assignment from a cost matrix. Here’s a sample program:

Running that program produces:

The instantiated Munkres object can be used multiple times on different matrices.

Non-square Cost Matrices

The Munkres algorithm assumes that the cost matrix is square. However, it’s possible to use a rectangular matrix if you first pad it with 0 values to make it square. This module automatically pads rectangular cost matrices to make them square.

The module operates on a copy of the caller’s matrix, so any padding will not be seen by the caller.
The cost matrix must be rectangular or square. An irregular matrix will not work.

Calculating Profit, Rather than Cost

The cost matrix is just that: A cost matrix. The Munkres algorithm finds the combination of elements (one from each row and column) that results in the smallest cost. It’s also possible to use the algorithm to maximize profit. To do that, however, you have to convert your profit matrix to a cost matrix. The simplest way to do that is to subtract all elements from a large value. For example:

The munkres module provides a convenience method for creating a cost matrix from a profit matrix. By default, it calculates the maximum profit and subtracts every profit from it to obtain a cost. If, however, you need a more general function, you can provide the conversion function; but the convenience method takes care of the actual creation of the matrix:

So, the above profit-calculation program can be recast as:

Disallowed Assignments

You can also mark assignments in your cost or profit matrix as disallowed. Simply use the munkres.DISALLOWED constant.

Running this program produces:

http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html

Harold W. Kuhn. The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly , 2:83-97, 1955.
Harold W. Kuhn. Variants of the Hungarian method for assignment problems. Naval Research Logistics Quarterly , 3: 253-258, 1956.
Munkres, J. Algorithms for the Assignment and Transportation Problems. Journal of the Society of Industrial and Applied Mathematics , 5(1):32-38, March, 1957.
http://en.wikipedia.org/wiki/Hungarian_algorithm

Getting and installing munkres

Because munkres is available via PyPI , if you have pip installed on your system, installing munkres is as easy as running this command:

WARNING: As of version 1.1.0, munkres no longer supports Python 2. If you need to use it with Python 2, install an earlier version (e.g., 1.0.12):

Installing from source

You can also install munkres from source. Either download the source (as a zip or tarball) from http://github.com/bmc/munkres/downloads , or make a local read-only clone of the Git repository using one of the following commands:

Once you have a local munkres source directory, change your working directory to the source directory, and type:

To install it somewhere other than the default location (such as in your home directory) type:

Documentation

Consult the API documentation for details. The API documentation is generated from the source code, so you can also just browse the source .

http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html

This module is released under the Apache Software License, version 2. See the license file for details.

RcppArmadillo
RcppExamples
Dirk's Rcpp page
Romain's Rcpp page
Rcpp at CRAN
Rcpp at GitHub
Rcpp at R-Forge
Rcpp-Devel list at Gmane
StackOverflow on Rcpp

Munkres' Assignment Algorithm with RcppArmadillo

Lars Simon Zehnder — written Sep 24, 2013 — source

Munkres’ Assignment Algorithm ( Munkres (1957) , also known as hungarian algorithm ) is a well known algorithm in Operations Research solving the problem to optimally assign N jobs to N workers.

I needed to solve the Minimal Assignment Problem for a relabeling algorithm in MCMC sampling for finite mixture distributions, where I use a random permutation Gibbs sampler. For each sample an optimal labeling must be found, i.e. I have N parameter vectors and must assign each vector to one of the N components of the finite mixture under the restriction that each component gets a parameter vector. For the assignment of parameters to components [Stephens (1997b)] (http://www.isds.duke.edu/~scs/Courses/Stat376/Papers/Mixtures/LabelSwitchingStephensJRSSB.pdf) suggests an algorithm relying on the Minimal Assignment in regard to a loss matrix . The labeling with the smallest loss is then considered as optimal.

After an unsuccessful search for libraries implementing the algorithm easily for C++ or C, I made the decision to program it myself using RcppArmadillo for good performance. I found some guidance by the websites of Bob Pilgrim and [TopCoder] (http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm). These websites offer excellent tutorials to understand the algorithm and to convert it to code. The order of this implementation of Munkres’ algorithm is of an order N to the power of 4. There exists also a version of order N to the power of 3, but an order of N to the power of 4 works very good for me and coding time is as usual a critical factor for me.

In the following I walk through the different steps of Munkres’ algorithm and explain the main parts and their functionality.

Let’s begin. The first step in Munkres’ algorithm is to subtract the minimal element of each row from each element in this row.

Note, that we use references for all function arguments. As we have to switch between the steps of the algorithm continously, we always must be able to determine which step should be chosen next. Therefore we give a mutable unsigned integer step as an argument to each step function of the algorithm.

Inside the function we can easily access a whole row by Armadillo’s row() method for matrices. In the second step, we then search for a zero in the modified cost matrix of step one.

Only the first zero in a row is taken. Then, the indicator matrix indM indicates this zero by setting the corresponding element at (r, c) to 1. A unique zero - the only or first one in a column and row - is called starred zero . In step 2 we find such a starred zero .

Note, that we use here Armadillo’s element access via the method at() , which makes no bound checks and improves performance.

Note Bene: This code is thoroughly debugged - never do this for fresh written code!

In step 3 we cover each column with a starred zero . If already N columns are covered all starred zeros describe a complete assignment - so, go to step 7 and finish. Otherwise go to step 4 .

We cover a column by looking for 1s in the indicator matrix indM (See step 2 for assuring that these are indeed only starred zeros ).

Step 4 finds noncovered zeros and primes them. If there are zeros in a row and none of them is starred , prime them. For this task we program a helper function to keep the code more readable and reusable. The helper function searches for noncovered zeros .

We can detect noncovered zeros by checking if the cost matrix contains at row r and column c a zero and row and column are not covered yet, i.e. rcov(r) == 0 , ccov(c) == 0 . This loop breaks, if we have found our first uncovered zero or no uncovered zero at all.

In step 4 , if no uncovered zero is found we go to step 6 . If instead an uncovered zero has been found, we set the indicator matrix at its position to 2. We then have to search for a starred zero in the row with the uncovered zero , uncover the column with the starred zero and cover the row with the starred zero . To indicate a starred zero in a row and to find it we create again two helper functions.

We know that starred zeros are indicated by the indicator matrix containing an element equal to 1. Now, step 4 .

Notice the rpath_0 and cpath_0 variables. These integer variables store the first vertex for an augmenting path in step 5 . If zeros could be primed we go further to step 5 .

Step 5 constructs a path beginning at an uncovered primed zero (this is actually graph theory - alternating and augmenting paths) and alternating between starred and primed zeros . This path is continued until a primed zero with no starred zero in its column is found. Then, all starred zeros in this path are unstarred and all primed zeros are starred . All primes in the indicator matrix are erased and all rows are uncovered . Then return to step 3 to cover again columns.

Step 5 needs several helper functions. First, we need a function to find starred zeros in columns.

Then we need a function to find a primed zero in a row. Note, that these tasks are easily performed by searching the indicator matrix indM .

In addition we need a function to augment the path, one to clear the covers from rows and one to erase the primed zeros from the indicator matrix indM .

The function to augment the path gets an integer matrix path of dimension 2 * N x 2. In it all vertices between rows and columns are stored row-wise. Now, we can set the complete step 5 :

Recall, if step 4 was successfull in uncovering all columns and covering all rows with a primed zero, it then calls step 6 . Step 6 takes the cover vectors rcov and ccov and looks in the uncovered region of the cost matrix for the smallest value. It then subtracts this value from each element in an uncovered column and adds it to each element in a covered row . After this transformation, the algorithm starts again at step 4 . Our last helper function searches for the smallest value in the uncovered region of the cost matrix.

Step 6 looks as follows:

At last, we must create a function that enables us to jump around the different steps of the algorithm. The following code shows the main function of the algorithm. It defines also the important variables to be passed to the different steps.

Note, this function takes the numeric cost matrix as an argument and returns the integer indicator matrix indM .

I chose to set the argument input_cost constant and copy it for reasons of reusability of the cost matrix in other C++ code. When working with rather huge cost matrices, it makes sense to make the argument mutable. Though, I used pass-by-reference for all the arguments in functions to avoid useless copying inside the functions.

To call the main function hungarian from R and to use our algorithm we construct an Rcpp Attribute :

If we want to provide this function also to other users we should probably ensure, that the matrix is square (There exists also an extension to rectangular matrices, see Burgeois and Lasalle (1971) ). This can be done easily with the exceptions provided by Rcpp passed over to R:

Note, that it is also possible to use for the attribute directly an Armadillo matrix, but following the recent discussion on the Rcpp-devel list , a pass-by-reference of arguments is not yet possible. Romain Francois’ proposals seem promising, so maybe we can expect in some of the next releases shallow copies allowing pass-by-reference in Rcpp Attributes .

Let us begin now with a very easy example that makes clear what is going on.

We can also compute a maximal assignment over a revenue matrix by simply considering the difference between a big value and this matrix as a cost matrix.

CoCost matrices containing negative values work as well:

Finally let us make some benchmarking. We load the rbenchmark package and take now a more realistic cost matrix.

But we also see, where the limitations of this algorithm lie

huge matrices:

Some last notes on the structure of the code. I prefer to put the code of the algorithm in an header file, e.g. hungarian.h . And use an attributes.cpp ( attributes.cc ) file to program the Rcpp Attributes . With this, I can easily reuse the algorithm in C++ code by simple inclusion ( #include "hungarian.h" ) and have a complete overview on all the C++ functions I export to R.

tags: armadillo

Extending R with C++ and Fortran — Dirk Eddelbuettel and JBrandon Duck-Mayr
Benchmarking Rcpp code with RcppClock — Zach DeBruine
Simulation Smoother using RcppArmadillo — Tomasz Woźniak

Search code, repositories, users, issues, pull requests...

Provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

Notifications

A C++ demo for Hungarian algorithm (Kuhn-Munkres algorithm).

RocShi/hungarian_optimizer

Folders and files, repository files navigation, hungarian optimizer.

A c++ demo for Hungarian algorithm (Kuhn-Munkres Algorithm) based on Apollo Hungarian Optimizer which is a implementation of Munkres’ Assignment Algorithm-Modified for Rectangular Matrices .

Eigen (V3.3.7 is used here, other versions may also work.)

Just run the run.sh script under the directory of repository.

For the given cost matrix example in the demo

You will the output result like

The result means row 1 is assigned to column 1, row 2 is assigned to column 2, and row 3 is assigned to column 0.

Attention, both the indices of rows and columns of the cost matrix start at 0.

Apollo Hungarian Optimizer
Munkres’ Assignment Algorithm-Modified for Rectangular Matrices

Help Center Help Center

Help Center
Trial Software
Product Updates
Documentation

assignmunkres

Munkres global nearest neighbor assignment algorithm

Description

[ assignments , unassignedrows , unassignedcolumns ] = assignmunkres( costmatrix , costofnonassignment ) returns a table of assignments of detections to tracks using the Munkres algorithm. The Munkres algorithm obtains an optimal solution to the global nearest neighbor (GNN) assignment problem. An optimal solution minimizes the total cost of the assignments.

The cost of each potential assignment is contained in the cost matrix, costmatrix . Each matrix entry represents the cost of a possible assignments. Matrix rows represent tracks and columns represent detections. All possible assignments are represented in the cost matrix. The lower the cost, the more likely the assignment is to be made. Each track can be assigned to at most one detection and each detection can be assigned to at most one track. If the number of rows is greater than the number of columns, some tracks are unassigned. If the number of columns is greater than the number of rows, some detections are unassigned. You can set an entry of costmatrix to Inf to prohibit an assignment.

costofnonassignment represents the cost of leaving tracks or detections unassigned. Higher values increase the likelihood that every existing object is assigned.

The function returns a list of unassigned tracks, unassignedrows , and a list of unassigned detections, unassignedcolumns

collapse all

Assign Detections to Tracks Using Munkres Algorithm

Use assignMunkres to assign three detections to two tracks.

Start with two predicted track locations in x-y coordinates.

Assume three detections are received. At least one detection will not be assigned.

Construct a cost matrix by defining the cost of assigning a detection to a track as the Euclidean distance between them. Set the cost of non-assignment to 0.2.

Use the Auction algorithm to assign detections to tracks.

Display the assignments.

Show that there are no unassigned tracks.

Display the unassigned detections.

Plot detection to track assignments.

The track to detection assignments are:

Detection 1 is assigned to track 1.

Detection 2 is assigned to track 2.

Detection 3 is not assigned.

Input Arguments

Costmatrix — cost matrix real-valued m -by- n.

Cost matrix, specified as an M -by- N matrix. M is the number of tracks to be assigned and N is the number of detections to be assigned. Each entry in the cost matrix contains the cost of a track and detection assignment. The matrix may contain Inf entries to indicate that an assignment is prohibited. The cost matrix cannot be a sparse matrix.

Data Types: single | double

costofnonassignment — cost of non-assignment of tracks and detections scalar

Cost of non-assignment, specified as a scalar. The cost of non-assignment represents the cost of leaving tracks or detections unassigned. Higher values increase the likelihood that every object is assigned. The value cannot be set to Inf .

The costofnonassignment is half of the maximum cost that a successful assignment can have.

Output Arguments

Assignments — assignment of tracks to detections integer-valued l -by-2 matrix.

Assignment of detections to track, returned as an integer-valued L -by-2 matrix where L is the number of assignments. The first column of the matrix contains the assigned track indices and the second column contains the assigned detection indices.

Data Types: uint32

unassignedrows — Indices of unassigned tracks integer-valued P -by-1 column vector

Indices of unassigned tracks, returned as an integer-valued P -by-1 column vector.

unassignedcolumns — Indices of unassigned detections integer-valued Q -by-1 column vector

Indices of unassigned detections, returned as an integer-valued Q -by-1 column vector.

[1] Samuel S. Blackman and Popoli, R. Design and Analysis of Modern Tracking Systems . Artech House: Norwood, MA. 1999.

Extended Capabilities

C/c++ code generation generate c and c++ code using matlab® coder™., version history.

Introduced in R2018b

assignauction | assignjv | assignkbest | assignkbestsd | assignsd | assignTOMHT | trackerTOMHT | trackerGNN

MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

Switzerland (English)
Switzerland (Deutsch)
Switzerland (Français)
中国 (English)

You can also select a web site from the following list:

How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

América Latina (Español)
Canada (English)
United States (English)
Belgium (English)
Denmark (English)
Deutschland (Deutsch)
España (Español)
Finland (English)
France (Français)
Ireland (English)
Italia (Italiano)
Luxembourg (English)
Netherlands (English)
Norway (English)
Österreich (Deutsch)
Portugal (English)
Sweden (English)
United Kingdom (English)

Asia Pacific

Australia (English)
India (English)
New Zealand (English)

Contact your local office

use Algorithm::Munkres;

assign(\@mat,\@out_mat);

DESCRIPTION

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

1 POD Error

The following errors were encountered while parsing the POD:

Non-ASCII character seen before =encoding in 'François'. Assuming UTF-8

Module Install Instructions

To install Algorithm::Munkres, copy and paste the appropriate command in to your terminal.

For more information on module installation, please visit the detailed CPAN module installation guide .

Keyboard Shortcuts

The Munkres type exposes the following members.

The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry.

James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial. Since then the algorithm has been known also as the Kuhn–Munkres algorithm or Munkres assignment algorithm.The time complexity of the original algorithm was O(n^4), however Edmonds and Karp, and independently Tomizawa noticed that it can be modified to achieve an O(n^3) running time. Ford and Fulkerson extended the method to general transportation problems. In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.

This code has been based on the original MIT-licensed code by R.A. Pilgrim, available in http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html, and on the BSD-licensed code by Yi Cao, available in http://fr.mathworks.com/matlabcentral/fileexchange/20652-hungarian-algorithm-for-linear-assignment-problems--v2-3-

Yi Cao (2011). Hungarian Algorithm for Linear Assignment Problems (V2.3). Available in http://fr.mathworks.com/matlabcentral/fileexchange/20652-hungarian-algorithm-for-linear-assignment-problems--v2-3-
R. A. Pilgrim (2000). Munkres' Assignment Algorithm Modified for Rectangular Matrices. Available in http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html
Wikipedia contributors. "Hungarian algorithm." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 23 Jan. 2016.