hungarian assignment python

Hungarian Algorithm Introduction & Python Implementation

How to use hungarian method to resolve the linear assignment problem..

By Eason on 2021-08-02

In this article, I will introduce how to use Hungarian Method to resolve the linear assignment problem and provide my personal Python code solution.

So… What is the linear assignment problem?

The linear assignment problem represents the need to maximize the available resources (or minimize the expenditure) with limited resources. For instance, below is a 2D matrix, where each row represents a different supplier, and each column represents the cost of employing them to produce a particular product. Each supplier can only specialize in the production of one of these products. In other words, only one element can be selected for each column and row in the matrix, and the sum of the selected elements must be minimized (minimized cost expense).

The cost of producing different goods by different producers:

Indeed, this is a simple example. By trying out the possible combinations, we can see that the smallest sum is 13, so supplier A supplies Bubble Tea , supplier B supplies milk tea, and supplier C supplies Fruit Tea . However, such attempts do not follow a clear rule and become inefficient when applied to large tasks. Therefore, the next section will introduce step by step the Hungarian algorithm, which can be applied to the linear assignment problem.

Hungarian Algorithm & Python Code Step by Step

In this section, we will show how to use the Hungarian algorithm to solve linear assignment problems and find the minimum combinations in the matrix. Of course, the Hungarian algorithm can also be used to find the maximum combination.

Step 0. Prepare Operations

First, an N by N matrix is generated to be used for the Hungarian algorithm (Here, we use a 5 by 5 square matrix as an example).

The above code randomly generates a 5x5 cost matrix of integers between 0 and 10.

If we want to find the maximum sum, we could do the opposite. The matrix to be solved is regarded as the profit matrix, and the maximum value in the matrix is set as the common price of all goods. The cost matrix is obtained by subtracting the profit matrix from the maximum value. Finally, the cost matrix is substituted into the Hungarian algorithm to obtain the minimized combination and then remapped back to the profit matrix to obtain the maximized sum value and composition result.

The above code randomly generates a 5x5 profit matrix of integers between 0 and 10 and generate a corresponding cost matrix

By following the steps above, you can randomly generate either the cost matrix or the profit matrix. Next, we will move into the introduction of the Hungarian algorithm, and for the sake of illustration, the following sections will be illustrated using the cost matrix shown below. We will use the Hungarian algorithm to solve the linear assignment problem of the cost matrix and find the corresponding minimum sum.

Example cost matrix:

Step 1. Every column and every row subtract its internal minimum

First, every column and every row must subtract its internal minimum. After subtracting the minimum, the cost matrix will look like this.

Cost matrix after step 1:

And the current code is like this:

Step 2.1. Min_zero_row Function Implementation

At first, we need to find the row with the fewest zero elements. So, we can convert the previous matrix to the boolean matrix(0 → True, Others → False).

Transform matrix to boolean matrix:

Corresponding Boolean matrix:

Therefore, we can use the “min_zero_row” function to find the corresponding row.

The row which contains the least 0:

Third, mark any 0 elements on the corresponding row and clean up its row and column (converts elements on the Boolean matrix to False). The coordinates of the element are stored in mark_zero.

Hence, the boolean matrix will look like this:

The boolean matrix after the first process. The fourth row has been changed to all False.

The process is repeated several times until the elements in the boolean matrix are all False. The below picture shows the order in which they are marked.

The possible answer composition:

Step 2.2. Mark_matrix Function Implementation

After getting Zero_mat from the step 2–1, we can check it and mark the matrix according to certain rules. The whole rule can be broken down into several steps:

Mark rows that do not contain marked 0 elements and store row indexes in the non_marked_row
Search non_marked_row element, and find out if there are any unmarked 0 elements in the corresponding column
Store the column indexes in the marked_cols
Compare the column indexes stored in marked_zero and marked_cols
If a matching column index exists, the corresponding row_index is saved to non_marked_rows
Next, the row indexes that are not in non_marked_row are stored in marked_rows

Finally, the whole mark_matrx function is finished and then returns marked_zero , marked_rows , marked_cols. At this point, we will be able to decide the result based on the return information.

If we use the example cost matrix, the corresponding marked_zero , marked_rows, and marked_cols are as follows:

marked_zero : [(3, 2), (0, 4), (1, 1), (2, 0), (4, 3)]
marked_rows : [0, 1, 2, 3, 4]
marked_cols : []

Step 3. Identify the Result

At this step, if the sum of the lengths of marked_rows and marked_cols is equal to the length of the cost matrix, it means that the solution of the linear assignment problem has been found successfully, and marked_zero stores the solution coordinates. Fortunately, in the example matrix, we find the answer on the first try. Therefore, we can skip to step 5 and calculate the solution.

However, everything is hardly plain sailing. Most of the time, we will not find the solution on the first try, such as the following matrix:

After Step 1 & 2 , the corresponding matrix, marked_rows, and marked_cols are as follows:

The sum of the lengths of Marked_Rows and Marked_Cols is 4 (less than 5).

Apparently, the sum of the lengths is less than the length of the matrix. At this time, we need to go into Step 4 to adjust the matrix.

Step 4. Adjust Matrix

In Step 4, we're going to put the matrix after Step 1 into the Adjust_Matrix function . Taking the latter matrix in Step 3 as an example, the matrix to be modified in Adjust_Matrix is:

The whole function can be separated into three steps:

Find the minimum value for an element that is not in marked_rows and not in marked_cols . Hence, we can find the minimum value is 1.

Subtract the elements which not in marked_rows nor marked_cols from the minimum values obtained in the previous step.

Add the element in marked_rows , which is also in marked_cols , to the minimum value obtained by Step 4–1.

Return the adjusted matrix and repeat Step 2 and Step 3 until the conditions satisfy the requirement of entering Step 5.

Step 5. Calculate the Answer

Using the element composition stored in marked_zero , the minimum and maximum values of the linear assignment problem can be calculated.

The minimum composition of the assigned matrix and the minimum sum is 18.

The maximum composition of the assigned matrix and the maximum sum is 43.

The code of the Answer_Calculator function is as follows:

The complete code is as follows:

Hungarian algorithm - Wikipedia

Continue Learning

Statistical tests with python.

A way to evaluate the evidence the data provides against a hypothesis

Union Find — Data Structure in Python

3 ways to connect django with mongodb.

Django — MongoDB — Djongo — MongoEngine — PyMongo

File Uploads and Downloads in FastAPI: A Comprehensive Guide

Everything you need to know about managing file uploads and downloads in your FastAPI applications

Find Out Who Doesn’t Follow You on Instagram

Top 70+ python project ideas beginners to expert with free source code [2024].

Beginner and intermediate-level Python project ideas with source code.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

Notifications You must be signed in to change notification settings

The Hungarian algorithm aims at solving an assignment problem.

gabrielmaia7/hungarian_algorithm

Folders and files, repository files navigation, the hungarian algorithm.

This repo contains a crude, but a good shot at, an implementation in Python of the Hungarian Algorithm (or the Munkres Assignment ALgorithm); one of the coolest algorithms I've studied in graph theory (you can't say it isn't). For a full description of the algorithm and its theoretical basis, visit the Wikipedia link .

In short, the Hungarian Algorithm (or Method) aims at solving a specific kind o problem, which is an assignment problem. More so, it tries to solve it in polynomial time, which is the most compelling reason to use it. An assignment problem consists mainly on associating a group of tasks T to a set of workers W , while considering the cost matrix C , which describes the cost C[i,j] of assigning task T[i] to worker W[j] .

This means that the algorithm solves the minimum cost - or the maximum gain, if you think about it differently - of a task assignment situation. This works when combining teams, passing down processing tasks to workers in a system, calculating delivery routes for drivers or service workers, you name it: if it can be reduced to an assignment problem, this is your guy.

When I said I studied it in graph theory, it's because, as I said, problems that can be reduced to an assignment problem can also be solved with the Hungarian. One of these is finding a perfect matching with minimal cost (or maximum gain) in a complete bipartite weighted graph, where partition T is the tasks and partition W the workers.

A matching would be a group of edges with no common vertices among them, and a perfect matching would be one that touches all vertices in the graph. So, in our graph, a perfect matching would associate every vertice in T to a sole vertice in W , and vice-versa. That's an assignment problem.

It's a common enough problem and a simple enough algorithm for me to train my python skills. So I end up with a code that, who knows, may just be useful for me, and I have some fun while I'm at it.

There are two main ways to see this method, as a problem in graphs, if your costs are a complete bipartite graph, or as a problem in matrix, if your costs are in a matrix. Since dealing with matrices in python is much more intuitive, we go with matrices, specifically the method presented in the Wikipedia page.

So, if you want to contribute, feel free to propose an implementation using graphs!

Simply import hungarian.py as a module. It contains a class HungarianAlg and some internal functions that you shouldn't mind. The use is documented in the code itself, which is not long, and proper use can be seen in the hungarian_test.py file. Run this test file to make sure the algorithm works.

Python 100.0%

munkres 1.1.4

pip install munkres Copy PIP instructions

Released: Sep 15, 2020

Munkres (Hungarian) algorithm for the Assignment Problem

Verified details

Maintainers.

Unverified details

Project links.

License: Apache Software License (Apache Software License)
Author: Brian Clapper

Classifiers

Science/Research
OSI Approved :: Apache Software License
OS Independent
Scientific/Engineering :: Mathematics
Software Development :: Libraries :: Python Modules

Project description

Introduction.

The Munkres module provides an implementation of the Munkres algorithm (also called the Hungarian algorithm or the Kuhn-Munkres algorithm), useful for solving the Assignment Problem.

For complete usage documentation, see: https://software.clapper.org/munkres/

Project details

Release history release notifications | rss feed.

Sep 15, 2020

Feb 15, 2019

Feb 12, 2019

Jun 27, 2017

May 23, 2017

Jan 2, 2017

Jun 22, 2016

Dec 3, 2014

Nov 3, 2013

Mar 29, 2010

Aug 2, 2009

Jun 30, 2008

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages .

Source Distribution

Uploaded Sep 15, 2020 Source

Built Distribution

Uploaded Sep 15, 2020 Python 2 Python 3

File details

Details for the file munkres-1.1.4.tar.gz .

File metadata

Download URL: munkres-1.1.4.tar.gz
Upload date: Sep 15, 2020
Size: 14.0 kB
Tags: Source
Uploaded using Trusted Publishing? No
Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.23.0 setuptools/49.2.0 requests-toolbelt/0.9.1 tqdm/4.49.0 CPython/3.8.4