in hungarian method of solving an assignment problem the row reduction is obtained by

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.

Hungarian Method

Hungarian Method is for assigning jobs by a one-for-one matching to identify the lowest-cost solution. Each job must be assigned to only one machine. It is assumed that every machine is capable of handling every job, and that the costs or values associated with each assignment combination are known and fixed. The number of rows and columns must be the same.

Hungarian Method Applet will appear below in a Java enabled Internet browser.

• Subtract the smallest number in each row from every number in the row. This is called a row reduction. Enter the results in a new table.
• Subtract the smallest number in each column of the new table from every number in the column. This is called a column reduction. Enter the results in another table.
• Test whether an optimum assignment can be made. You do this by determining the minimum number of lines needed to cover (i.e., cross out) all zeros. If the number of lines equals the number of rows, an optimum assignment is possible. In that case, go to step 6. Otherwise go on to step 4.
• If the number of lines is less than the number of rows, modify the table in this way: a. Subtract the smallest uncovered number from every uncovered number in the table. b. Add the smallest uncovered number to the numbers at intersections of covering lines. c. Numbers crossed out but not at intersections of cross-out lines carry over unchanged to the next table.
• Repeat steps 3 and 4 until an optimal table is obtained.
• Make the assignments. Begin with rows or columns with only one zero. Match items that have zeros, using only one match for each row and each column. Cross out both the row and the column after the match.
• Press the Auto button to see how the user specified problem is solved automatically.
• Press the Start button to start solving the problem.
• Press the Prev button to go back to the previous step.
• Press the Next button to go to the next step.
• Press the Add button to add a new machine/job pair.
• Press the Delete button to delete an existing machine/job pair selected from the pull-down list.

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

Assignment problem: Hungarian method 3

Assignment problem: Hungarian Method Nui Ruppert (Mtk_Nr.: 373224) David Lenh (Mtk_Nr.: 368343) Amir Farshchi Tabrizi (Mtk-Nr.: 372894)

In this OR-Wiki entry we're going to explain the Hungarian method with 3 examples. In the first example you'll find the optimal solution after a few steps with the help of the reduced matrix. The second example illustrates a complex case where you need to proceed all the steps of the algorithm to get to an optimal solution. Finally in the third example we will show how to solve a maximization problem with the Hungarian method.

Inhaltsverzeichnis

• 1 Introduction
• 2 Example 1 – Minimization problem
• 3 Example 2 – Minimazation problem
• 4 Example 3 – Maximization problem
• 6 References

Introduction

The Hungarian method is a combinatorial optimization algorithm which was developed and published by Harold Kuhn in 1955. This method was originally invented for the best assignment of a set of persons to a set of jobs. It is a special case of the transportation problem. The algorithm finds an optimal assignment for a given “n x n” cost matrix. “Assignment problems deal with the question how to assign n items (e.g. jobs) to n machines (or workers) in the best possible way. […] Mathematically an assignment is nothing else than a bijective mapping of a finite set into itself […]” [1]

The assignment constraints are mathematically defined as:

To make clear how to solve an assignment problem with the Hungarian algorithm we will show you the different cases with several examples which can occur .

Example 1 – Minimization problem

In this example we have to assign 4 workers to 4 machines. Each worker causes different costs for the machines. Your goal is to minimize the total cost to the condition that each machine goes to exactly 1 person and each person works at exactly 1 machine. For comprehension: Worker 1 causes a cost of 6 for machine 1 and so on …

To solve the problem we have to perform the following steps:

Step 1 – Subtract the row minimum from each row.

Step 2 – Subtract the column minimum from each column from the reduced matrix.

The idea behind these 2 steps is to simplify the matrix since the solution of the reduced matrix will be exactly the same as of the original matrix.

Step 3 – Assign one “0” to each row & column.

Now that we have simplified the matrix we can assign each worker with the minimal cost to each machine which is represented by a “0”.

- In the first row we have one assignable “0” therefore we assign it to worker 3 .

- In the second row we also only have one assignable “0” therefore we assign it to worker 4 .

- In the third row we have two assignable “0”. We leave it as it is for now.

- In the fourth row we have one assignable “0” therefore we assign it. Consider that we can only assign each worker to each machine hence we can’t allocate any other “0” in the first column.

- Now we go back to the third row which now only has one assignable “0” for worker 2 .

As soon as we can assign each worker to one machine, we have the optimal solution . In this case there is no need to proceed any further steps. Remember also, if we decide on an arbitrary order in which we start allocating the “0”s then we may get into a situation where we have 3 assignments as against the possible 4. If we assign a “0” in the third row to worker 1 we wouldn’t be able to allocate any “0”s in column one and row two.

The rule to assign the “0”:

- If there is an assignable “0”, only 1 assignable “0” in any row or any column, assign it.

- If there are more than 1, leave it and proceed.

This rule would try to give us as many assignments as possible.

Now there are also cases where you won’t get an optimal solution for a reduced matrix after one iteration. The following example will explain it.

Example 2 – Minimazation problem

In this example we have the fastest taxi company that has to assign each taxi to each passenger as fast as possible. The numbers in the matrix represent the time to reach the passenger.

We proceed as in the first example.

Iteration 1:

Now we have to assign the “0”s for every row respectively to the rule that we described earlier in example 1.

- In the first row we have one assignable “0” therefore we assign it and no other allocation in column 2 is possible.

- In the second row we have one assignable “0” therefore we assign it.

- In the third row we have several assignable “0”s. We leave it as it is for now and proceed.

- In the fourth and fifth row we have no assignable “0”s.

Now we proceed with the allocations of the “0”s for each column .

- In the first column we have one assignable “0” therefore we assign it. No other “0”s in row 3 are assignable anymore.

Now we are unable to proceed because all the “0”s either been assigned or crossed. The crosses indicate that they are not fit for assignments because assignments are already made.

We realize that we have 3 assignments for this 5x5 matrix. In the earlier example we were able to get 4 assignments for a 4x4 matrix. Now we have to follow another procedure to get the remaining 2 assignments (“0”).

Step 4 – Tick all unassigned rows.

Step 5 – If a row is ticked and has a “0”, then tick the corresponding column (if the column is not yet ticked).

Step 6 – If a column is ticked and has an assignment, then tick the corresponding row (if the row is not yet ticked).

Step 7 - Repeat step 5 and 6 till no more ticking is possible.

In this case there is no more ticking possible and we proceed with the next step.

Step 8 – Draw lines through unticked rows and ticked columns. The number of lines represents the maximum number of assignments possible.

Step 9 – Find out the smallest number which does not have any line passing through it. We call it Theta. Subtract theta from all the numbers that do not have any lines passing through them and add theta to all those numbers that have two lines passing through them. Keep the rest of them the same.

(With this step we create a new “0”)

With the new assignment matrix we start to assign the “0”s after the explained rules. Nevertheless we have 4 assignments against the required 5 for an optimal solution. Therefore we have to repeat step 4 – 9.

Iteration 2:

Step 4 – Tick all unassigned row.

Note: The indices of the ticks show you the order we added them.

Iteration 3:

Iteration 4:

After the fourth iteration we assign the “0”s again and now we have an optimal solution with 5 assignments.

The solution:

- Taxi1 => Passenger1 - duration 12

- Taxi2 => Passenger4 - duration 11

- Taxi3 => Passenger2 - duration 8

- Taxi4 => Passenger3 - duration 14

- Taxi5 => Passenger5 - duration 11

If we define the needed duration as costs, the minimal cost for this problem is 56.

Example 3 – Maximization problem

Furthermore the Hungarian algorithm can also be used for a maximization problem in which case we first have to transform the matrix. For example a company wants to assign different workers to different machines. Each worker is more or less efficient with each machine. The efficiency can be defined as profit. The higher the number, the higher the profit.

As you can see, the maximal profit of the matrix is 13. The simple twist that we do is rather than try to maximize the profit, we’re going to try to minimize the profit that you don’t get. If every value is taken away from 13, then we can minimize the amount of profit lost. We receive the following matrix:

From now on we proceed as usual with the steps to get to an optimal solution.

With the determined optimal solution we can compute the maximal profit:

- Worker1 => Machine2 - 9

- Worker2 => Machine4 - 11

- Worker3 => Machine3 - 13

- Worker4 => Machine1 - 7

Maximal profit is 40.

The optimal solution is found if there is one assigned “0” for each row and each column.

[1] Linear Assignment Problems and Extensions, Rainer E. Burkard, Eranda Cela

[2] Operations Research Skript TU Kaiserslautern, Prof. Dr. Oliver Wendt

[3] The Hungarian method for the assignment problem, H. W. Kuhn, Bryn Mawr College

Fundamental of Operations Research, Lec. 16, Prof. G. Srinivasan

Navigationsmenü

• Quelltext anzeigen
• Versionsgeschichte

Meine Werkzeuge

• Gemeinschaftsportal
• Operations Research
• Studentenbeiträge zum Thema Operations Research
• Wirtschaftsinformatik
• Aktuelle Ereignisse
• Letzte Änderungen
• Zufällige Seite
• Links auf diese Seite
• Änderungen an verlinkten Seiten
• Spezialseiten
• Druckversion
• Permanenter Link
• Seiten­informationen

• Diese Seite wurde zuletzt am 1. Juli 2013 um 11:03 Uhr geändert.
• Datenschutz
• Über Operations-Research-Wiki

Hungarian Method to solve Assignment Problem

For obtaining an optimal assignment, Hungarian method involves following steps :

Subtract the minimum of each row of the cost matrix,from all the elements of respective rows.

Subtract the minimum of each column of the modified cost matrix, from all the elements of respective columns.

Then draw the minimum number of horizontal and vertical line to cover all the zeros in the modified cost matrix.

Let the number of lines be $N$.

• If $N=n$, the number of rows (columns) of given cost matrix, then an optimal assignment can be made. Go to Step 6.
• If $N<n$, then go to next step.

Determine the smallest element in the matrix, not covered by the $N$ lines. Subtract this smallest element from all the uncovered elements and add the same element at the intersection of horizontal and vertical lines. And obtain the second modified matrix.

Repeat Steps 3 and 4 until minimum number of lines become equal to the number of rows (columns) of the given matrix i.e. $N =n$.

Examine the row successively until a row-wise exactly single zero is found, mark this zero by $\square$ to make the assignment and mark cross $(\times)$ over all zeros in that column. Continue in this manner until all the rows have been examined. Repeat the same procedure for columns also.

Repeat the Step 6 successively until one of the following situations arise :

• if no unmarked zero is left, the process ends; or
• if there lie more than one of the unmarked zeros in any column or row, then mark $\square$ one of the unmarked zeros arbitrarily and cross over all zeros lying in that row or column. Repeat the process until no unmarked zero is left in the matrix.

Thus, in each row and in each column exactly one marked $\square$ zero is obtained. The assignment corresponding to these marked zeros will give an optimal assignment.

• Feb 20, 2024

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.

Difference between solving Assignment Problem using the Hungarian Method vs. LP

When trying to solve for assignments given a cost matrix, what is the difference between

using Scipy's linear_sum_assignment function (which I think uses the Hungarian method)

describing the LP problem using a objective function with many boolean variables, add in the appropriate constraints and send it to a solver, such as through scipy.optimize.linprog ?

Is the later method slower than Hungarian method's O(N^3) but allows for more constraints to be added?

• linear-programming
• combinatorial-optimization
• assignment-problem

• $\begingroup$ The main difference between a mathematical model and a heuristic algorithm to solve a specific problem is more likely to prove optimality rather feasibility. Now, one can decide which one to be selected in order to satisfy needs. $\endgroup$ –  A.Omidi Commented Mar 20, 2022 at 7:54
• 4 $\begingroup$ @A.Omidi the Hungarian method is an exact algorithm $\endgroup$ –  fontanf Commented Mar 20, 2022 at 8:26
• $\begingroup$ @fontanf, you are right. What I said was to compare the exact and heuristic methods and it is not specific to Hungarian alg. Thanks for your hint. $\endgroup$ –  A.Omidi Commented Mar 20, 2022 at 10:32

The main differences probably are that there is a somewhat large overhead you have to pay when solving the AP as a linear program: You have to build an LP model and ship it to a solver. In addition, an LP solver is a generalist. It solves all LP problems and focus in development is to be fast on average on all LPs and also to be fast-ish in the pathological cases.

When using the Hungarian method, you do not build a model, you just pass the cost matrix to a tailored algorithm. You will then use an algorithm developed for that specific problem to solve it. Hence, it will most likely solve it faster since it is a specialist.

So if you want to solve an AP you should probably use the tailored algorithm. If you plan on extending your model to handle other more general constraints as well, you might need the LP after all.

Edit: From a simple test in Python, my assumption is confirmed in this specific setup (which is to the advantage of the Hungarian method, I believe). The set up is as follows:

• A size is chosen in $n\in \{5,10,\dots,500\}$
• A cost matrix is generated. Each coefficient $c_{ij}$ is generated as a uniformly distributed integer in the range $[250,999]$ .
• The instance is solved using both linear_sum_assignment and as a linear program. The solution time is measured as wall clock time and only the time spent by linear_sum_assignment and the solve function is timed (not building the LP and not not generating the instance)

For each size, I have generated and solved ten instances, and I report the average time only.

And then there is of course the "but". I am not a ninja in Python and I have used pyomo for modelling the LPs. I believe that pyomo is known to be slow-ish whenbuilding models, hence I have only timed the solver.solve(model) part of the code - not building the model. There is however possibly a hugh overhead cost coming from pyomo translating the model to "gurobian" (I use gurobi as solver).

• 1 $\begingroup$ Do you have some benchmark results to support this claim? Intuitively, I would have thought that the Hungarian method would be much slower in practice $\endgroup$ –  fontanf Commented Mar 20, 2022 at 7:39
• $\begingroup$ @fontanf I only have anecdotal proof from past experiments. Maybe an LP solver can work faster for repeated solves, where you exploit that the model is already build and basis info is available. But I honestly don't know. $\endgroup$ –  Sune Commented Mar 20, 2022 at 9:37
• 1 $\begingroup$ It might be the case that the Hungarian method is faster for small problems (due to the overhead Sune mentioned for setting up an LP model) while simplex (or dual simplex, or maybe barrier) might be faster for large models because the setup cost is "amortized" better. (I'm just speculating here.) $\endgroup$ –  prubin ♦ Commented Mar 20, 2022 at 15:30
• 2 $\begingroup$ The Hungarian algorithm is, of course, O(n^3) for fully dense assignment problems. I don't know if there is a simplex bound explicitly for assignments. Simplex is exponential in the worst case and linear in variables plus constraints (n^2 + 2n here) in practice. But assignments are highly degenerate (n positive basics out of 2n rows). Dual simplex may fare better than primal. Hungarian is all integer for integer costs, whereas a standard simplex code won't be unless it knows to detect that in preprocessing. That may lead to some overhead for linear algebra. Ha, an idea for a class project! $\endgroup$ –  mjsaltzman Commented Mar 20, 2022 at 17:04
• 2 $\begingroup$ Just for the sake of completeness, here 's the same with gurobipy instead of Pyomo. On my machine, all LPs (n = 500) are solved in less than a second compared to roughly 4 seconds with Pyomo. $\endgroup$ –  joni Commented Mar 21, 2022 at 16:21

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 combinatorial-optimization assignment-problem or ask your own question .

• Featured on Meta
• Preventing unauthorized automated access to the network
• User activation: Learnings and opportunities
• Join Stack Overflow’s CEO and me for the first Stack IRL Community Event in...

Hot Network Questions

• In big band horn parts, should I write double flats (sharps) or the enharmonic equivalent?
• Krull dimension in non-algebraically closed fields
• BTD6 Kinetic Chaos (9/26/24 Odyssey)
• Remove an entire inner list that has any zeros
• How does 自由に不自由していない work here?
• How to write an Antagonist that is hot, manipulative, but has good reasoning for being the 'villain'?
• 2 NICs, PC is trying to use wrong one
• Geometry nodes mapping 0-1 UV to every mesh face
• In the Silmarillion or the Appendices to ROTK, do the Dwarves of Khazad-dûm know about the Balrog below prior to Durin receiving the ring?
• What is the role of this suffix for an opamp?
• Table Decimal Alignment using siunitx package
• Do we have volitional control over our level of skepticism?
• What is the average result of rolling Xd6 twice and taking the higher of the two sums?
• What is the name for this BC-BE back-to-back transistor configuration?
• How to enable (turn on) a 5V power rail with a 3.3V MCU power rail?
• Proof of existence of algebraic closure with Zorn's lemma
• If Voyager is still an active NASA spacecraft, does it have a flight director? Is that a part time job?
• Why are METAR issued at 53 minutes of the hour?
• Where is this NPC's voice coming from?
• Papersize - why does TeX add margins by default and how can I avoid them?
• What is the linguistic terminology for cases where the intonation or stress of a syllable determines its meaning?
• Differential Ordinary Generating Function
• Five Hundred Cigarettes
• This puzzle is delicious

Index     Assignment problem     Hungarian algorithm     Solve online    

Solve an assignment problem online

Fill in the cost matrix of an assignment problem and click on 'Solve'. The optimal assignment will be determined and a step by step explanation of the hungarian algorithm will be given.

Fill in the cost matrix ( random cost matrix ):

Don't show the steps of the Hungarian algorithm Maximize the total cost

HungarianAlgorithm.com © 2013-2024

• Interview Questions on Array
• Practice Array
• MCQs on Array
• Tutorial on Array
• Types of Arrays
• Array Operations
• Subarrays, Subsequences, Subsets
• Reverse Array
• Static Vs Arrays
• Array Vs Linked List
• Array | Range Queries
• Advantages & Disadvantages

Travelling Salesman Problem using Hungarian method

A travelling salesman plans to visit N cities in such a way that he visits each city exactly once and return to the city from where he started . The distance between City i and City j is C ij . Find the shortest tour he can take.

Note: Travelling from City i to City i is not possible and C ij may not be equal to C ji .

Input: See the routes in the image. Output: 80 Explanation: The shortest route can be achieved following the path C 1 -> C 2 -> C 4 -> C 3 -> C 1 .  So the route length is 10 + 25 + 30 + 15 = 80. Input: See the routes in the image. Output: 15 Explanation: The shortest route is C 1 -> C 2 -> C 3 -> C 4 -> C 5 -> C 1 . So the path length is 2 + 3 + 4 + 5 + 1 = 15.

Intuition: Suppose there are 3 cities namely city 1 ,city 2 , and city 3.  All the possible combinations to visit the cities are

1->2->3->1       (1->2, 2->3, 3->1) 1->3->2->1       (1->3, 3->2, 2->1) 2->1->3->2       (2->1, 1->3, 3->2) 2->3->1->2       (2->3, 3->1, 1->2) 3->1->2->3       (3->1, 1->2, 2->3) 3->2->1->3       (3->2, 2->1,1->3)

So, the cities can be visited in 6 different ways but if observed carefully it can be seen that tour 1st, 4th and 5th are equivalent and tour 2nd, 3rd and 6th are equivalent . Therefore, different combinations possible are actually 2 and those are

1->2->3->1 1->3->2->1

Hence, If there are N cities to visit then there can be (N-1)! ways to travel to each city exactly once and return to the starting city. This type of problem can be solved by the Hungarian method , branch and bound method, penalty method, and nearest neighbor method. We will see how to solve this type of problem using Hungarian method.

Approach: Mentioned below are the steps to follow to solve the problem using Hungarian method . Consider the example shown in the image: 

Follow the illustrations of solution of the above example for better understanding.

Step 1: Locate the smallest cost elements in each row of the cost matrix. Subtract this element from every other element of the corresponding row. As a result, there is at least one zero in each row of the reduced cost matrix

Illustration: Subtracting 1st row with the minimum value 1. Subtracting 2nd row with the minimum value 2. Subtracting 3rd row with the minimum value 4. Subtracting 4th row with the minimum value 4. Subtracting 5th row with the minimum value 1.

Step 2: Similarly, locate the smallest element of each column In the reduced cost matrix obtained and subtract that from each element of the corresponding column. As a result, there should be at least one zero in each row and columns of the second reduced cost matrix.

Illustration: Subtracting 1st column with the minimum value 0. Subtracting 2nd column with the minimum value 0. Subtracting 3rd column with the minimum value 1. Subtracting 4th column with the minimum value 0. Subtracting 5th column with the minimum value 0.

Step 3: Make assignment in the matrix as follows.

• Move row by row until a row with single zero is found .
• Assign the cell containing the zero and cross off all other zeros in its column. 
• Continue this process until all the rows with single zero is assigned. 
• Repeat the procedure for each column.
• If a row and ( or ) a column has two or more zeros and one cannot be chosen by inspection then assign arbitrary any one of these zeros and cross off all other zeros of that row / column.

Illustration: Row wise cell (1,5) is assigned. So, column wise cell (2,5) is crossed off. Row wise cell (2,3) is assigned. So, column wise cell (5,3) is crossed off. Row wise cell (3,4) is assigned. Row wise cell (4,2) is assigned. Row wise cell (5,1) is assigned. Here, the number of assignment is equal to the number of cities and the tour is 1->5->1 and 2->3->4->2 which means salesman will travel from city 1 to city 5 and return to city 1 and then again start from city , travel to city 3, city 4 and return to city 2. Therefore, we are getting two cycle and hence it is not the solution.

Step 4: The next best solution can be obtained by bringing the minimum non-zero element and repeat the step 2 and step 3

Illustration: In this case, minimum non-zero element is 1. Row wise cell (3,4) is assigned.       Row wise cell (1,2) is assigned. So, column wise cell (4,2) is crossed off and row wise cell (1,5) is crossed off. Row wise cell (2,5) is assigned. So, row wise cell (2,3) is crossed off and column wise cell (4,5) is crossed off. Row wise cell (4,3) is assigned. So, column wise cell (5,3) is crossed off. Row wise cell (5,1) is assigned. Now, the sequence is 1->2->5->1 and 3->4->3. Again, we are getting two cycle therefore this is also not the solution.

Step 5:  Make different possible assignment

Illustration: Row wise cell (3,4) is assigned. Row wise cell (1,2) is assigned. So, column wise cell (4,2) is crossed off and row wise cell (1,5) is crossed off. Row wise cell (2,3) is assigned. So, column wise cell (4,3) and (5,3) is crossed off and row wise cell (2,5) is crossed off. Row wise cell (4,5) is assigned. Row wise cell (5,1) is assigned. The sequence is 1->2->3->4->5->1. So, this solution is optimal and total distance of this tour is  Cell 12 + Cell 23 + Cell 34 + Cell 45 + Cell 51 = (2+3+4+5+1) =15.

Similar Reads

Please login to comment....

• How to Install & Use Kodi on FireStick
• How to Watch NFL on NFL+ in 2024: A Complete Guide
• Best Smartwatches in 2024: Top Picks for Every Need
• Top Budgeting Apps in 2024
• GeeksforGeeks Practice - Leading Online Coding Platform

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Procedure, Example Solved Problem | Operations Research - Solution of assignment problems (Hungarian Method) | 12th Business Maths and Statistics : Chapter 10 : Operations Research

Chapter: 12th business maths and statistics : chapter 10 : operations research.

Solution of assignment problems (Hungarian Method)

First check whether the number of rows is equal to the numbers of columns, if it is so, the assignment problem is said to be balanced.

Step :1 Choose the least element in each row and subtract it from all the elements of that row.

Step :2 Choose the least element in each column and subtract it from all the elements of that column. Step 2 has to be performed from the table obtained in step 1.

Step:3 Check whether there is atleast one zero in each row and each column and make an assignment as follows.

Step :4 If each row and each column contains exactly one assignment, then the solution is optimal.

Example 10.7

Solve the following assignment problem. Cell values represent cost of assigning job A, B, C and D to the machines I, II, III and IV.

Here the number of rows and columns are equal.

∴ The given assignment problem is balanced. Now let us find the solution.

Step 1: Select a smallest element in each row and subtract this from all the elements in its row.

Look for atleast one zero in each row and each column.Otherwise go to step 2.

Step 2: Select the smallest element in each column and subtract this from all the elements in its column.

Since each row and column contains atleast one zero, assignments can be made.

Step 3 (Assignment):

Thus all the four assignments have been made. The optimal assignment schedule and total cost is

The optimal assignment (minimum) cost

Example 10.8

Consider the problem of assigning five jobs to five persons. The assignment costs are given as follows. Determine the optimum assignment schedule.

∴ The given assignment problem is balanced.

Now let us find the solution.

The cost matrix of the given assignment problem is

Column 3 contains no zero. Go to Step 2.

Thus all the five assignments have been made. The Optimal assignment schedule and total cost is

The optimal assignment (minimum) cost = ` 9

Example 10.9

Solve the following assignment problem.

Since the number of columns is less than the number of rows, given assignment problem is unbalanced one. To balance it , introduce a dummy column with all the entries zero. The revised assignment problem is

Here only 3 tasks can be assigned to 3 men.

Step 1: is not necessary, since each row contains zero entry. Go to Step 2.

Step 3 (Assignment) :

Since each row and each columncontains exactly one assignment,all the three men have been assigned a task. But task S is not assigned to any Man. The optimal assignment schedule and total cost is

The optimal assignment (minimum) cost = ₹ 35

Related Topics

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

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.

Does the Hungarian Method find all optimal assignments?

I've just started learning about the Hungarian Method. Everywhere I look, I see that the Hungarian Method gives an optimal assignment/solution to the assignment problem at hand, which I understand. However, what if there are multiple different assignments with the same (optimal) cost? After trying some examples, I found that all optimal solutions are found by the Hungarian Method. But is this generally the case?

• graph-theory
• optimization

• 1 $\begingroup$ or.stackexchange.com $\endgroup$ –  Rodrigo de Azevedo Commented Oct 31, 2019 at 21:09

A very general argument for the case with multiple optimal solutions applies here.

Consider an $n\times n$ instance of the assignment problem with multiple optimal solutions. If we pick any specific optimal solution $S$ , then decrease the cost of every edge used in $S$ by a small amount $\epsilon$ , then the total cost of $S$ decreases by $n\epsilon$ , whereas the cost of any other optimal solution decreases by $k\epsilon$ for some $k<n$ . So the same solution $S$ is the unique optimal solution for the modified problem.

If you compare what the Hungarian algorithm does in the original problem and the modified problem, then (assuming $\epsilon$ is sufficiently small) there is only one way for the algorithm to make different choices in the two cases: when it's comparing two costs that were equal in the original problem, but where one cost ended up being decreased in the modified problem.

Therefore the Hungarian algorithm, which is guaranteed to find solution $S$ for the modified problem, is also capable of finding $S$ in the original program, if it breaks ties correctly: if, whenever it compares two equal costs, it does whatever it would for the modified problem.

Since $S$ was arbitrary, it follows that for every optimal solution to the original problem, the Hungarian algorithm is capable of finding it, depending on how it breaks ties. This is a sense in which the Hungarian algorithm finds all optimal solutions.

We could actually generate all the optimal solutions by forking into two paths every time that the Hungarian algorithm has a choice between two equally good options. But if there are many ties in the cost matrix, then this could require lots of forks, and might not be efficient.

• $\begingroup$ Thank you Misha or your elaboration! So performing the Hungarian method just once will not lead to all optimal solutions. This comes from the fact that the decisions that you make (covering rows and columns with lines to cover all zero elements for instance) lead to some specific optimal solution and hence taking another path in the algorithme could have given you another optimal solution. Is that correct? $\endgroup$ –  Ruudferguson Commented Nov 1, 2019 at 8:33
• $\begingroup$ Right, that's the idea. In cases with multiple optimal solutions, you'll have some choices about which zero elements to pick as assignments, and how to cover rows/columns. $\endgroup$ –  Misha Lavrov Commented Nov 1, 2019 at 13:14
• $\begingroup$ Actually, just the covering-zeroes-by-the-fewest-rows-and-columns aspect of things shouldn't be the reason for multiple solutions, since it can happen whether or not there are ties between costs. The reason for multiple outcomes is when you have more than one zero in a row or column to pick as the "assigned" zero. $\endgroup$ –  Misha Lavrov Commented Nov 1, 2019 at 13:35
• $\begingroup$ So if I understand correctly, you say that once the Hungarian method is performed and an optimal solution (or 0-assignment) is found in some modified matrix, all other optimal solutions (if any) should also be visible in this modified matrix? So it is not possible that there are two optimal assignments for which only one of them is visible in the final step of the Hungarian method and the other assignment does not contain all zero elements? $\endgroup$ –  Ruudferguson Commented Nov 1, 2019 at 14:15
• $\begingroup$ I'm not saying that either. It might be true, though. $\endgroup$ –  Misha Lavrov Commented Nov 2, 2019 at 4:21

You must log in to answer this question.

Not the answer you're looking for browse other questions tagged graph-theory optimization ..

• Featured on Meta
• User activation: Learnings and opportunities
• Preventing unauthorized automated access to the network
• A Limited Advertising Test on this Site

Hot Network Questions

• What are major reasons why Republicans support the death penalty?
• How can I award a player an additional Feat?
• Is it ethical to edit grammar, spelling, and wording errors in survey questions after the survey has been administered, prior to publication?
• Is this solar system mechanically possible?
• Did Sauron refer to Morgoth as "Morgoth" (Sindarin for "Black Foe" or "Dark Tyrant")?
• God the Father punished the Son as sin-bearer: how does that prove God’s righteousness?
• What is the role of this suffix for an opamp?
• Lilypond Orchestral score: how to show duplicated tempo marking for violins?
• Permutation of a set that gives multiple of 2010
• If I'm turning humans into crude oil, would removing their skeletons accelerate this process?
• Papersize - why does TeX add margins by default and how can I avoid them?
• What is the linguistic terminology for cases where the intonation or stress of a syllable determines its meaning?
• What is the name for this BC-BE back-to-back transistor configuration?
• Can I possibly win in this kind of situation?
• How to enable (turn on) a 5V power rail with a 3.3V MCU power rail?
• Randomly color the words
• How to Organise/Present Built Worlds?
• is it correct to say "can you stop clinking the cup of coffee"?
• Is it considered vulgar to use "massive" to describe female breast size?
• Propagation of Sansevieria – Is My Cutting Going to Succeed?
• How do you measure exactly 31 minutes by burning the ropes?
• If a 'fire temple' was built in a gigantic city, with many huge perpetual flames inside, how could they keep smoke from bothering non-worshippers?
• Proof of existence of algebraic closure with Zorn's lemma
• Compact operators vs Bounded operators between infinite dimensional spaces