assignment problem linear programming hungarian method

Hungarian Method

The Hungarian method is a computational optimization technique that addresses the assignment problem in polynomial time and foreshadows following primal-dual alternatives. In 1955, Harold Kuhn used the term “Hungarian method” to honour two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry. Let’s go through the steps of the Hungarian method with the help of a solved example.

Hungarian Method to Solve Assignment Problems

The Hungarian method is a simple way to solve assignment problems. Let us first discuss the assignment problems before moving on to learning the Hungarian method.

What is an Assignment Problem?

A transportation problem is a type of assignment problem. The goal is to allocate an equal amount of resources to the same number of activities. As a result, the overall cost of allocation is minimised or the total profit is maximised.

Because available resources such as workers, machines, and other resources have varying degrees of efficiency for executing different activities, and hence the cost, profit, or loss of conducting such activities varies.

Assume we have ‘n’ jobs to do on ‘m’ machines (i.e., one job to one machine). Our goal is to assign jobs to machines for the least amount of money possible (or maximum profit). Based on the notion that each machine can accomplish each task, but at variable levels of efficiency.

Hungarian Method Steps

Check to see if the number of rows and columns are equal; if they are, the assignment problem is considered to be balanced. Then go to step 1. If it is not balanced, it should be balanced before the algorithm is applied.

Step 1 – In the given cost matrix, subtract the least cost element of each row from all the entries in that row. Make sure that each row has at least one zero.

Step 2 – In the resultant cost matrix produced in step 1, subtract the least cost element in each column from all the components in that column, ensuring that each column contains at least one zero.

Step 3 – Assign zeros

• Analyse the rows one by one until you find a row with precisely one unmarked zero. Encircle this lonely unmarked zero and assign it a task. All other zeros in the column of this circular zero should be crossed out because they will not be used in any future assignments. Continue in this manner until you’ve gone through all of the rows.
• Examine the columns one by one until you find one with precisely one unmarked zero. Encircle this single unmarked zero and cross any other zero in its row to make an assignment to it. Continue until you’ve gone through all of the columns.

Step 4 – Perform the Optimal Test

• The present assignment is optimal if each row and column has exactly one encircled zero.
• The present assignment is not optimal if at least one row or column is missing an assignment (i.e., if at least one row or column is missing one encircled zero). Continue to step 5. Subtract the least cost element from all the entries in each column of the final cost matrix created in step 1 and ensure that each column has at least one zero.

Step 5 – Draw the least number of straight lines to cover all of the zeros as follows:

(a) Highlight the rows that aren’t assigned.

(b) Label the columns with zeros in marked rows (if they haven’t already been marked).

(c) Highlight the rows that have assignments in indicated columns (if they haven’t previously been marked).

(d) Continue with (b) and (c) until no further marking is needed.

(f) Simply draw the lines through all rows and columns that are not marked. If the number of these lines equals the order of the matrix, then the solution is optimal; otherwise, it is not.

Step 6 – Find the lowest cost factor that is not covered by the straight lines. Subtract this least-cost component from all the uncovered elements and add it to all the elements that are at the intersection of these straight lines, but leave the rest of the elements alone.

Step 7 – Continue with steps 1 – 6 until you’ve found the highest suitable assignment.

Hungarian Method Example

Use the Hungarian method to solve the given assignment problem stated in the table. The entries in the matrix represent each man’s processing time in hours.

\(\begin{array}{l}\begin{bmatrix} & I & II & III & IV & V \\1 & 20 & 15 & 18 & 20 & 25 \\2 & 18 & 20 & 12 & 14 & 15 \\3 & 21 & 23 & 25 & 27 & 25 \\4 & 17 & 18 & 21 & 23 & 20 \\5 & 18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

With 5 jobs and 5 men, the stated problem is balanced.

\(\begin{array}{l}A = \begin{bmatrix}20 & 15 & 18 & 20 & 25 \\18 & 20 & 12 & 14 & 15 \\21 & 23 & 25 & 27 & 25 \\17 & 18 & 21 & 23 & 20 \\18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

Subtract the lowest cost element in each row from all of the elements in the given cost matrix’s row. Make sure that each row has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 5 & 10 \\6 & 8 & 0 & 2 & 3 \\0 & 2 & 4 & 6 & 4 \\0 & 1 & 4 & 6 & 3 \\2 & 2 & 0 & 3 & 4 \\\end{bmatrix}\end{array} \)

Subtract the least cost element in each Column from all of the components in the given cost matrix’s Column. Check to see if each column has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 3 & 7 \\6 & 8 & 0 & 0 & 0 \\0 & 2 & 4 & 4 & 1 \\0 & 1 & 4 & 4 & 0 \\2 & 2 & 0 & 1 & 1 \\\end{bmatrix}\end{array} \)

When the zeros are assigned, we get the following:

The present assignment is optimal because each row and column contain precisely one encircled zero.

Where 1 to II, 2 to IV, 3 to I, 4 to V, and 5 to III are the best assignments.

Hence, z = 15 + 14 + 21 + 20 + 16 = 86 hours is the optimal time.

Practice Question on Hungarian Method

Use the Hungarian method to solve the following assignment problem shown in table. The matrix entries represent the time it takes for each job to be processed by each machine in hours.

\(\begin{array}{l}\begin{bmatrix}J/M & I & II & III & IV & V \\1 & 9 & 22 & 58 & 11 & 19 \\2 & 43 & 78 & 72 & 50 & 63 \\3 & 41 & 28 & 91 & 37 & 45 \\4 & 74 & 42 & 27 & 49 & 39 \\5 & 36 & 11 & 57 & 22 & 25 \\\end{bmatrix}\end{array} \)

Stay tuned to BYJU’S – The Learning App and download the app to explore all Maths-related topics.

Frequently Asked Questions on Hungarian Method

What is hungarian method.

The Hungarian method is defined as a combinatorial optimization technique that solves the assignment problems in polynomial time and foreshadowed subsequent primal–dual approaches.

What are the steps involved in Hungarian method?

The following is a quick overview of the Hungarian method: Step 1: Subtract the row minima. Step 2: Subtract the column minimums. Step 3: Use a limited number of lines to cover all zeros. Step 4: Add some more zeros to the equation.

What is the purpose of the Hungarian method?

When workers are assigned to certain activities based on cost, the Hungarian method is beneficial for identifying minimum costs.

Leave a Comment Cancel reply

Your Mobile number and Email id will not be published. Required fields are marked *

Request OTP on Voice Call

Post My Comment

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures

Hungarian Algorithm for Assignment Problem | Set 2 (Implementation)

Given a 2D array , arr of size N*N where arr[i][j] denotes the cost to complete the j th job by the i th worker. Any worker can be assigned to perform any job. The task is to assign the jobs such that exactly one worker can perform exactly one job in such a way that the total cost of the assignment is minimized.

Input: arr[][] = {{3, 5}, {10, 1}} Output: 4 Explanation: The optimal assignment is to assign job 1 to the 1st worker, job 2 to the 2nd worker. Hence, the optimal cost is 3 + 1 = 4. Input: arr[][] = {{2500, 4000, 3500}, {4000, 6000, 3500}, {2000, 4000, 2500}} Output: 4 Explanation: The optimal assignment is to assign job 2 to the 1st worker, job 3 to the 2nd worker and job 1 to the 3rd worker. Hence, the optimal cost is 4000 + 3500 + 2000 = 9500.

Different approaches to solve this problem are discussed in this article .

Approach: The idea is to use the Hungarian Algorithm to solve this problem. The algorithm is as follows:

• For each row of the matrix, find the smallest element and subtract it from every element in its row.
• Repeat the step 1 for all columns.
• Cover all zeros in the matrix using the minimum number of horizontal and vertical lines.
• Test for Optimality : If the minimum number of covering lines is N , an optimal assignment is possible. Else if lines are lesser than N , an optimal assignment is not found and must proceed to step 5.
• Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to step 3.

Consider an example to understand the approach:

Let the 2D array be: 2500 4000 3500 4000 6000 3500 2000 4000 2500 Step 1: Subtract minimum of every row. 2500, 3500 and 2000 are subtracted from rows 1, 2 and 3 respectively. 0   1500  1000 500  2500   0 0   2000  500 Step 2: Subtract minimum of every column. 0, 1500 and 0 are subtracted from columns 1, 2 and 3 respectively. 0    0   1000 500  1000   0 0   500  500 Step 3: Cover all zeroes with minimum number of horizontal and vertical lines. Step 4: Since we need 3 lines to cover all zeroes, the optimal assignment is found.   2500   4000  3500  4000  6000   3500   2000  4000  2500 So the optimal cost is 4000 + 3500 + 2000 = 9500

For implementing the above algorithm, the idea is to use the max_cost_assignment() function defined in the dlib library . This function is an implementation of the Hungarian algorithm (also known as the Kuhn-Munkres algorithm) which runs in O(N 3 ) time. It solves the optimal assignment problem. 

Below is the implementation of the above approach:

Time Complexity: O(N 3 ) Auxiliary Space: O(N 2 )

Please Login to comment...

Similar reads.

• Mathematical

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Index     Assignment problem     Hungarian algorithm     Solve online    

The Hungarian algorithm: An example

We consider an example where four jobs (J1, J2, J3, and J4) need to be executed by four workers (W1, W2, W3, and W4), one job per worker. The matrix below shows the cost of assigning a certain worker to a certain job. The objective is to minimize the total cost of the assignment.

Below we will explain the Hungarian algorithm using this example. Note that a general description of the algorithm can be found here .

Step 1: Subtract row minima

We start with subtracting the row minimum from each row. The smallest element in the first row is, for example, 69. Therefore, we substract 69 from each element in the first row. The resulting matrix is:

Step 2: Subtract column minima

Similarly, we subtract the column minimum from each column, giving the following matrix:

Step 3: Cover all zeros with a minimum number of lines

We will now determine the minimum number of lines (horizontal or vertical) that are required to cover all zeros in the matrix. All zeros can be covered using 3 lines:

Step 4: Create additional zeros

First, we find that the smallest uncovered number is 6. We subtract this number from all uncovered elements and add it to all elements that are covered twice. This results in the following matrix:

Now we return to Step 3.

Again, We determine the minimum number of lines required to cover all zeros in the matrix. Now there are 4 lines required:

Because the number of lines required (4) equals the size of the matrix ( n =4), an optimal assignment exists among the zeros in the matrix. Therefore, the algorithm stops.

The optimal assignment

The following zeros cover an optimal assignment:

This corresponds to the following optimal assignment in the original cost matrix:

Thus, worker 1 should perform job 3, worker 2 job 2, worker 3 job 1, and worker 4 should perform job 4. The total cost of this optimal assignment is to 69 + 37 + 11 + 23 = 140.

Solve your own problem online

HungarianAlgorithm.com © 2013-2024

• MapReduce Algorithm
• Linear Programming using Pyomo
• Networking and Professional Development for Machine Learning Careers in the USA
• Predicting Employee Churn in Python
• Airflow Operators

Solving Assignment Problem using Linear Programming in Python

Learn how to use Python PuLP to solve Assignment problems using Linear Programming.

In earlier articles, we have seen various applications of Linear programming such as transportation, transshipment problem, Cargo Loading problem, and shift-scheduling problem. Now In this tutorial, we will focus on another model that comes under the class of linear programming model known as the Assignment problem. Its objective function is similar to transportation problems. Here we minimize the objective function time or cost of manufacturing the products by allocating one job to one machine.

If we want to solve the maximization problem assignment problem then we subtract all the elements of the matrix from the highest element in the matrix or multiply the entire matrix by –1 and continue with the procedure. For solving the assignment problem, we use the Assignment technique or Hungarian method, or Flood’s technique.

The transportation problem is a special case of the linear programming model and the assignment problem is a special case of transportation problem, therefore it is also a special case of the linear programming problem.

In this tutorial, we are going to cover the following topics:

Assignment Problem

A problem that requires pairing two sets of items given a set of paired costs or profit in such a way that the total cost of the pairings is minimized or maximized. The assignment problem is a special case of linear programming.

For example, an operation manager needs to assign four jobs to four machines. The project manager needs to assign four projects to four staff members. Similarly, the marketing manager needs to assign the 4 salespersons to 4 territories. The manager’s goal is to minimize the total time or cost.

Problem Formulation

A manager has prepared a table that shows the cost of performing each of four jobs by each of four employees. The manager has stated his goal is to develop a set of job assignments that will minimize the total cost of getting all 4 jobs.  

Initialize LP Model

In this step, we will import all the classes and functions of pulp module and create a Minimization LP problem using LpProblem class.

Define Decision Variable

In this step, we will define the decision variables. In our problem, we have two variable lists: workers and jobs. Let’s create them using  LpVariable.dicts()  class.  LpVariable.dicts()  used with Python’s list comprehension.  LpVariable.dicts()  will take the following four values:

• First, prefix name of what this variable represents.
• Second is the list of all the variables.
• Third is the lower bound on this variable.
• Fourth variable is the upper bound.
• Fourth is essentially the type of data (discrete or continuous). The options for the fourth parameter are  LpContinuous  or  LpInteger .

Let’s first create a list route for the route between warehouse and project site and create the decision variables using LpVariable.dicts() the method.

Define Objective Function

In this step, we will define the minimum objective function by adding it to the LpProblem  object. lpSum(vector)is used here to define multiple linear expressions. It also used list comprehension to add multiple variables.

Define the Constraints

Here, we are adding two types of constraints: Each job can be assigned to only one employee constraint and Each employee can be assigned to only one job. We have added the 2 constraints defined in the problem by adding them to the LpProblem  object.

Solve Model

In this step, we will solve the LP problem by calling solve() method. We can print the final value by using the following for loop.

From the above results, we can infer that Worker-1 will be assigned to Job-1, Worker-2 will be assigned to job-3, Worker-3 will be assigned to Job-2, and Worker-4 will assign with job-4.

In this article, we have learned about Assignment problems, Problem Formulation, and implementation using the python PuLp library. We have solved the Assignment problem using a Linear programming problem in Python. Of course, this is just a simple case study, we can add more constraints to it and make it more complicated. You can also run other case studies on Cargo Loading problems , Staff scheduling problems . In upcoming articles, we will write more on different optimization problems such as transshipment problem, balanced diet problem. You can revise the basics of mathematical concepts in  this article  and learn about Linear Programming  in this article .

• Solving Blending Problem in Python using Gurobi
• Transshipment Problem in Python Using PuLP

You May Also Like

Understanding Convolutional Neural Network (CNN) using Python

Python Iterators Examples

Handling Missing Values in Pandas

Quantitative Techniques: Theory and Problems by P. C. Tulsian, Vishal Pandey

Get full access to Quantitative Techniques: Theory and Problems and 60K+ other titles, with a free 10-day trial of O'Reilly.

There are also live events, courses curated by job role, and more.

HUNGARIAN METHOD

Although an assignment problem can be formulated as a linear programming problem, it is solved by a special method known as Hungarian Method because of its special structure. If the time of completion or the costs corresponding to every assignment is written down in a matrix form, it is referred to as a Cost matrix. The Hungarian Method is based on the principle that if a constant is added to every element of a row and/or a column of cost matrix, the optimum solution of the resulting assignment problem is the same as the original problem and vice versa. The original cost matrix can be reduced to another cost matrix by adding constants to the elements of rows and columns where the total cost or the total completion time of an ...

Get Quantitative Techniques: Theory and Problems now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Don’t leave empty-handed

Get Mark Richards’s Software Architecture Patterns ebook to better understand how to design components—and how they should interact.

It’s yours, free.

Check it out now on O’Reilly

Dive in for free with a 10-day trial of the O’Reilly learning platform—then explore all the other resources our members count on to build skills and solve problems every day.

The Hungarian Method for the Assignment Problem

• First Online: 01 January 2009

Cite this chapter

• Harold W. Kuhn 9  

9939 Accesses

187 Citations

11 Altmetric

This paper has always been one of my favorite “children,” combining as it does elements of the duality of linear programming and combinatorial tools from graph theory. It may be of some interest to tell the story of its origin.

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

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Unable to display preview.  Download preview PDF.

Similar content being viewed by others

On weighted means and their inequalities

The Alternating Least-Squares Algorithm for CDPCA

Introduction

H.W. Kuhn, On the origin of the Hungarian Method , History of mathematical programming; a collection of personal reminiscences (J.K. Lenstra, A.H.G. Rinnooy Kan, and A. Schrijver, eds.), North Holland, Amsterdam, 1991, pp. 77–81.

Google Scholar  

A. Schrijver, Combinatorial optimization: polyhedra and efficiency , Vol. A. Paths, Flows, Matchings, Springer, Berlin, 2003.

MATH   Google Scholar  

Download references

Author information

Authors and affiliations.

Princeton University, Princeton, USA

Harold W. Kuhn

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Harold W. Kuhn .

Editor information

Editors and affiliations.

Inst. Informatik, Universität Köln, Pohligstr. 1, Köln, 50969, Germany

Michael Jünger

Fac. Sciences de Base (FSB), Ecole Polytechnique Fédérale de Lausanne, Lausanne, 1015, Switzerland

Thomas M. Liebling

Ensimag, Institut Polytechnique de Grenoble, avenue Félix Viallet 46, Grenoble CX 1, 38031, France

Denis Naddef

School of Industrial &, Georgia Institute of Technology, Ferst Drive NW., 765, Atlanta, 30332-0205, USA

George L. Nemhauser

IBM Corporation, Route 100 294, Somers, 10589, USA

William R. Pulleyblank

Inst. Informatik, Universität Heidelberg, Im Neuenheimer Feld 326, Heidelberg, 69120, Germany

Gerhard Reinelt

ed Informatica, CNR - Ist. Analisi dei Sistemi, Viale Manzoni 30, Roma, 00185, Italy

Giovanni Rinaldi

Center for Operations Reserach &, Université Catholique de Louvain, voie du Roman Pays 34, Leuven, 1348, Belgium

Laurence A. Wolsey

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this chapter

Kuhn, H.W. (2010). The Hungarian Method for the Assignment Problem. In: Jünger, M., et al. 50 Years of Integer Programming 1958-2008. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68279-0_2

Download citation

DOI : https://doi.org/10.1007/978-3-540-68279-0_2

Published : 06 November 2009

Publisher Name : Springer, Berlin, Heidelberg

Print ISBN : 978-3-540-68274-5

Online ISBN : 978-3-540-68279-0

eBook Packages : Mathematics and Statistics Mathematics and Statistics (R0)

Share this chapter

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

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Hungarian Method: Assignment Problem

Hungarian Method is an efficient method for solving assignment problems .

This method is based on the following principle:

• If a constant is added to, or subtracted from, every element of a row and/or a column of the given cost matrix of an assignment problem, the resulting assignment problem has the same optimal solution as the original problem.

Hungarian Algorithm

The objective of this section is to examine a computational method - an algorithm - for deriving solutions to the assignment problems. The following steps summarize the approach:

Steps in Hungarian Method

1. Identify the minimum element in each row and subtract it from every element of that row.

2. Identify the minimum element in each column and subtract it from every element of that column.

3. Make the assignments for the reduced matrix obtained from steps 1 and 2 in the following way:

• For every zero that becomes assigned, cross out (X) all other zeros in the same row and the same column.
• If for a row and a column, there are two or more zeros and one cannot be chosen by inspection, then you are at liberty to choose the cell arbitrarily for assignment.

4. An optimal assignment is found, if the number of assigned cells equals the number of rows (and columns). In case you have chosen a zero cell arbitrarily, there may be alternate optimal solutions. If no optimal solution is found, go to step 5.

5. Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix obtained from step 3 by adopting the following procedure:

• Mark all the rows that do not have assignments.
• Mark all the columns (not already marked) which have zeros in the marked rows.
• Mark all the rows (not already marked) that have assignments in marked columns.
• Repeat steps 5 (i) to (iii) until no more rows or columns can be marked.
• Draw straight lines through all unmarked rows and marked columns.

You can also draw the minimum number of lines by inspection.

6. Select the smallest element from all the uncovered elements. Subtract this smallest element from all the uncovered elements and add it to the elements, which lie at the intersection of two lines. Thus, we obtain another reduced matrix for fresh assignment.

7. Go to step 3 and repeat the procedure until you arrive at an optimal assignment.

For the time being we assume that number of jobs is equal to number of machines or persons. Later in the chapter, we will remove this restrictive assumption and consider a special case where no. of facilities and tasks are not equal.

Share This Article

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Transportation Problem

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Assignment problem using Hungarian method

There are five jobs to be assigned to five machines and associated cost matrix is as follows $$ \begin{matrix} \text{Machine} & 1 & 2 & 3 & 4 & 5 \\ \text{Job A} & [11, &17, &8, &16, &20] \\ \text{Job B} & [9, &7, &12, &6, &15] \\ \text{Job C} & [13, &16, &15, &12, &16] \\ \text{Job D} & [21, &24, &16, &28, &26] \\ \text{Job E} & [14, &10, &12, &11, &15] \end{matrix} $$ The question is now: Find the assignment of machines to jobs that will minimize the total cost?

I solved it using the Hungarian method but for job A and D I had only one zero that too in the same column. I don't know how to solve further if this happens.

• linear-programming
• assignment-problem

• 4 $\begingroup$ Since this looks a lot like a homework question, it would be best to show you intermediate steps of your attempt to solve it $\endgroup$ –  Michael Feldmeier Commented Jun 18, 2019 at 9:20
• 1 $\begingroup$ As a note, I voted to reject a tag edit of "self-study" because I think that would be a meta-tag. Not sure that we fully settled on that as a policy, but I think we were leaning that direction. ( or.meta.stackexchange.com/questions/163/… ) Also, welcome to OR.SE, @Tango! $\endgroup$ –  E. Tucker Commented Jun 18, 2019 at 14:15
• $\begingroup$ @E. Tucke At Cross Validated stats.stackexchange.com , self-study tag is applied to all homework problems, and even for questions requesting help understanding passages in textbooks, even f being used in self-study outside any courses. $\endgroup$ –  Mark L. Stone Commented Jun 18, 2019 at 23:12
• 1 $\begingroup$ @MarkL.Stone Sounds good! The tag seems accurate; it's more that it's a meta-tag. If the community wants to go that direction, that's fine by me. $\endgroup$ –  E. Tucker Commented Jun 19, 2019 at 12:13

I assume you're applying the matrix version of the algorithm. When you happen to have only one $0$ for A and D the matrix is \begin{align*} \pmatrix{2&9&0&8&8\\2&1&6&0&5\\0&4&3&0&0\\4&8&0&12&6\\3&0&2&1&1} \end{align*} Now continue with Step 3 : cover all zeros minimally, and adjust the weights. After that step you will find a solution.

• $\begingroup$ That is exact matrix I got now when covering all zeros I have r=4 covering lines and since problem has n=5 since r<n. STEP3: now 1 is least uncovered element subtracting 1 from all uncover element and adding 1 to element at intersection of covering line I am left with matrix that has same problem only one zero in A and D but now r=n . Can i use same step again when I have r=n $\endgroup$ –  Tango Commented Jun 18, 2019 at 14:26
• $\begingroup$ The least uncovered element will be $2$. Note that line $5$ will be unmarked after step 3. $\endgroup$ –  Marcus Ritt Commented Jun 19, 2019 at 5:14

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged linear-programming assignment-problem or ask your own question .

• Featured on Meta
• Announcing a change to the data-dump process
• Upcoming initiatives on Stack Overflow and across the Stack Exchange network...
• We spent a sprint addressing your requests — here’s how it went

Hot Network Questions

• How does Biden staying in the presidential race hurt Democrats in Congress?
• How would I translate GPT to German?
• Whence comes the expression ‘’starve a cold, feed a fever?”
• What is exactly Randstorm vulnerability?
• Is an EU ID card enough to fly from the UK to Ireland with Aer Lingus in July 2024?
• How does a quantized signal represent all magnitudes?
• What is the meaning of "yard" in "a yard across the street"?
• Which battles were the swords of the initial structure of the Iron Throne taken from?
• Constant volatge at the output of LM311
• Can trusted timestamping be faked by altering some bytes within the document?
• Could there be another relative language of the ancient Egyptian language closer to it than the Coptic?
• Why don't we call value investing "timing the market"?
• Why does the B-29 bomber not have propeller control lever in Cockpit/Engineer station
• What was the correct semantics of the FORTRAN "plus" carriage control character?
• Why must the ntp server using the local clock use the default loopback ip (127.127.1.0) ？
• What hidden class abilities are there in D&D 5e?
• Are foldable tires less puncture resistant?
• Tankless Electric Water Heater 80 amp disconnects
• Identify the open tag file
• When Barbie Alexandra says, "I don't even know how I got here", is she refering to a physical location or a metaphorical or emotional state?
• Tiny worms in blackberries
• Movie with a snake-like monster escaping from a borehole in Antarctica?
• Can't certain parts of my mesh during retopo
• How to address past academic misconduct as a new faculty member?

• MATLAB Answers
• File Exchange
• AI Chat Playground
• Discussions
• Communities
• Treasure Hunt
• Community Advisors
• Virtual Badges
• MathWorks.com
• Trial software

You are now following this Submission

• You may receive emails, depending on your communication preferences

Hungarian Algorithm for Linear Assignment Problems (V2.3)

View License

• Open in MATLAB Online
• Version History
• Reviews (35)
• Discussions (25)

This is an extremely fast implementation of the famous Hungarian algorithm (aslo known as Munkres' algorithm). It can solve a 1000 x 1000 problem in about 20 seconds in a Core Duo (T2500 @ 2.00GHz) XP laptop with Matlab 2008a, which is about 2.5 times faster than the mex code "assignmentoptimal" in FEX ID 6543, about 6 times faster than the author's first version in FEX ID 20328, and at least 30 times faster than other Matlab implementations in the FEX.

The code can also handle rectangular prolems and problems with forbiden allocations.

The new version (V2.3)is able to conduct a partial assignment if a full assignment is not feasible.

For more details of the Hungarian algorithm, visit http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html

Yi Cao (2024). Hungarian Algorithm for Linear Assignment Problems (V2.3) (https://www.mathworks.com/matlabcentral/fileexchange/20652-hungarian-algorithm-for-linear-assignment-problems-v2-3), MATLAB Central File Exchange. Retrieved July 22, 2024 .

MATLAB Release Compatibility

Platform compatibility.

• Mathematics and Optimization > Global Optimization Toolbox > Particle Swarm >

Tags Add Tags

Acknowledgements.

Inspired by: assignprob.zip , Functions for the rectangular assignment problem , Munkres Assignment Algorithm

Inspired: Hungarian Algorithm for Linear Sum Assignment Problem , Minimum Cost Constrained Input-Output and Control Configuration Co-Design Problem , Eigenshuffle , LAPJV - Jonker-Volgenant Algorithm for Linear Assignment Problem V3.0 , Hungarian based particle linking , simpletracker , Smooth Point-set Registration using Neighboring Constraints , TACTICS Toolbox

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Discover Live Editor

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

Learn About Live Editor

• munkres(costMat)

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: .

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)
• 简体中文 Chinese
• 日本 Japanese (日本語)
• 한국 Korean (한국어)

Contact your local office

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Assignment problem using Hungarian method

There are5 jobs to ne assigned one each to five machine and associated cost matrix is as follows Machine 1. 2. 3. 4. 5 Job. A [11 17 8 16 20] B [9. 7. 12. 6 15] C [13 16 15 12 16] D [21 24 16 28 26] E [14.10. 12 11 15] Find assignment of machines to job that will minimize the total cost?

solved it using Hungarian method but for job A and D I had only one zero that too in same column don't know how to solve further if this happens.

• linear-programming
• operations-research

• 2 $\begingroup$ I would consider moving this to or.stackexchange.com $\endgroup$ –  Rodrigo de Azevedo Commented Jun 15, 2019 at 8:28
• 1 $\begingroup$ Use LaTeX please. $\endgroup$ –  Michael Rozenberg Commented Jun 15, 2019 at 8:47
• $\begingroup$ See post on OR.SE or.stackexchange.com/questions/574/… $\endgroup$ –  Marcus Ritt Commented Jun 19, 2019 at 18:59

You must log in to answer this question.

Browse other questions tagged linear-programming operations-research ..

• Featured on Meta
• Announcing a change to the data-dump process
• Upcoming initiatives on Stack Overflow and across the Stack Exchange network...
• We spent a sprint addressing your requests — here’s how it went

Hot Network Questions

• Can trusted timestamping be faked by altering some bytes within the document?
• How to save coordinates from paths
• - Economics 101
• What's the fastest real-world travel time to the opposite side of the world?
• Which word can be used to describe either the beat or the subdivision?
• Tagging of Included Graphics
• What is the meaning of "yard" in "a yard across the street"?
• I found a counterexample to one of the intermediate assertions in a proof but not (necessarily) to the overall result – how to publish this?
• Prince Rupert' Drop Armor: How Expensive?
• How do I distinguish between "e" the natural log base and a variable conventionally referred to as "e"?
• How does Biden staying in the presidential race hurt Democrats in Congress?
• Is the term 標準語 considered sensitive in modern Japan?
• What drives the mechanical challenges which make trailing-edge flaps an (almost) ubiquitous solution vs leading-edge flaps?
• What was the correct semantics of the FORTRAN "plus" carriage control character?
• Competing Risks that are not mutually exclusive in Survival Analysis
• t() function with not-english language
• What is exactly Randstorm vulnerability?
• Can a group have a subgroup whose complement is closed under the group operation?
• Fire (as in shooting) in plural
• Is it rude to ask my PhD student to give a daily report?
• Which battles were the swords of the initial structure of the Iron Throne taken from?
• Event viewer showing 'logon' events, even when I'm currently using that PC
• How would I translate GPT to German?
• Did projectiles start being rifled before barrels?