Munkres (Hungarian) Algorithm

Warnings

• breaking As of version 1.1.0, the `munkres` library dropped support for Python 2. Users on Python 2 must use an older version (pre-1.1.0).
  Fix: Upgrade to Python 3 or use `munkres` version < 1.1.0 if Python 2 is strictly required.
• gotcha The Munkres algorithm natively solves minimization problems. To solve maximization problems (e.g., maximizing profit), the cost matrix must be transformed. A common approach is to subtract all matrix elements from a sufficiently large constant (e.g., the maximum value in the matrix).
  Fix: Transform your profit matrix `P` into a cost matrix `C` by `C[i][j] = MAX_PROFIT - P[i][j]`, where `MAX_PROFIT` is greater than or equal to any profit in the matrix.
• gotcha The `munkres` module automatically pads rectangular cost matrices with zeros to make them square, as the algorithm requires a square matrix. However, this operation works on a *copy* of the input matrix, so the caller's original matrix is not modified.
  Fix: Be aware that the input matrix is copied and potentially padded. If you need to observe the padded matrix for debugging or further processing, manually pad it before passing it to `Munkres.compute()`.
• gotcha Using the `DISALLOWED` constant correctly marks an assignment as impossible. However, if using `DISALLOWED` results in a scenario where a row or column has no possible valid assignments, the `compute` method will raise an `UnsolvableMatrix` exception, indicating that no complete assignment can be found under the given constraints.
  Fix: Ensure that your `DISALLOWED` constraints still allow for at least one valid assignment path for every row and column. If intentional non-assignments are needed, `munkres` does not directly support 'no match' if it leads to an unsolvable matrix. Consider augmenting your matrix with dummy rows/columns with zero costs to represent unassigned items if that aligns with your problem.
• gotcha The utility function `munkres.print_matrix()` might raise a `ValueError` (e.g., `math.log10(0)`) if the matrix contains zero values, especially in older versions or specific Python environments. This function is for display and does not affect the core algorithm.
  Fix: If encountering issues, avoid `print_matrix()` and implement a custom matrix printing function, or ensure only positive values are passed to it.

Install

• pip install munkres Install latest version

Imports

• Munkres

  from munkres import Munkres

  The primary class for running the algorithm.
• DISALLOWED

  from munkres import Munkres, DISALLOWED

  Constant to mark impossible assignments in the cost matrix.

Quickstart

This quickstart demonstrates how to create a cost matrix, initialize the Munkres solver, and compute the optimal (minimum cost) assignments. It also shows how to use the `DISALLOWED` constant for impossible assignments. The `compute` method returns a list of (row, column) tuples representing the optimal assignments.

from munkres import Munkres, DISALLOWED

def create_cost_matrix():
    # Example cost matrix: 3 workers, 3 tasks
    # cost[i][j] is cost of worker i doing task j
    return [
        [5, 9, 1],
        [10, 3, DISALLOWED],
        [8, 7, 4]
    ]

m = Munkres()
matrix = create_cost_matrix()

# The algorithm operates on a copy of the matrix,
# so the original 'matrix' is not modified.
indexes = m.compute(matrix)

total_cost = 0
print('Assignments:')
for row, column in indexes:
    value = matrix[row][column]
    total_cost += value
    print(f'  Worker {row} assigned to task {column} with cost {value}')

print(f'Total cost: {total_cost}')