Assignment Problem Python

Introduction

The Munkres module provides an implementation of the Munkres algorithm (also called the Hungarian algorithm or the Kuhn-Munkres algorithm). The algorithm models an assignment problem as an NxM cost matrix, where each element represents the cost of assigning the ith worker to the jth job, and it figures out the least-cost solution, choosing a single item from each row and column in the matrix, such that no row and no column are used more than once.

Getting and installing munkres

Installing

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

Installing from source

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

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

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

Documentation

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

References

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

License

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

Solve the linear sum assignment problem.

The linear sum assignment problem is also known as minimum weight matching in bipartite graphs. A problem instance is described by a matrix C, where each C[i,j] is the cost of matching vertex i of the first partite set (a “worker”) and vertex j of the second set (a “job”). The goal is to find a complete assignment of workers to jobs of minimal cost.

Formally, let X be a boolean matrix where \(X[i,j] = 1\) iff row i is assigned to column j. Then the optimal assignment has cost

\[\min \sum_i \sum_j C_{i,j} X_{i,j}\]

s.t. each row is assignment to at most one column, and each column to at most one row.

This function can also solve a generalization of the classic assignment problem where the cost matrix is rectangular. If it has more rows than columns, then not every row needs to be assigned to a column, and vice versa.

The method used is the Hungarian algorithm, also known as the Munkres or Kuhn-Munkres algorithm.

Parameters:

cost_matrix : array

The cost matrix of the bipartite graph.

Returns:

row_ind, col_ind : array

An array of row indices and one of corresponding column indices giving the optimal assignment. The cost of the assignment can be computed as . The row indices will be sorted; in the case of a square cost matrix they will be equal to .

Notes

References

  1. http://csclab.murraystate.edu/bob.pilgrim/445/munkres.html
  2. Harold W. Kuhn. The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2:83-97, 1955.
  3. Harold W. Kuhn. Variants of the Hungarian method for assignment problems. Naval Research Logistics Quarterly, 3: 253-258, 1956.
  4. Munkres, J. Algorithms for the Assignment and Transportation Problems. J. SIAM, 5(1):32-38, March, 1957.
  5. https://en.wikipedia.org/wiki/Hungarian_algorithm

Examples

>>> cost=np.array([[4,1,3],[2,0,5],[3,2,2]])>>> fromscipy.optimizeimportlinear_sum_assignment>>> row_ind,col_ind=linear_sum_assignment(cost)>>> col_indarray([1, 0, 2])>>> cost[row_ind,col_ind].sum()5

0 comments

Leave a Reply

Your email address will not be published. Required fields are marked *