LINEAR_ASSIGNMENT

Overview

The LINEAR_ASSIGNMENT function solves the classic assignment problem (Hungarian algorithm) using the scipy.optimize.linear_sum_assignment method. This algorithm finds the optimal assignment that minimizes the total cost for a given cost matrix, which is widely used in operations research, scheduling, and logistics.

The Hungarian algorithm operates on a cost matrix $C$ of size $m \times n$ and seeks a one-to-one assignment between rows and columns that minimizes the total cost. The algorithm works by:

Subtracting the row minima from each row.
Subtracting the column minima from each column.
Covering all zeros in the matrix using a minimum number of lines.
Adjusting the uncovered elements and repeating the process until an optimal assignment is found.

Mathematically, the goal is to find a permutation $\sigma$ that minimizes the total cost:

\min_{\sigma} \sum_{i=1}^n c_{i,\sigma(i)}

where $c_{i,j}$ is the cost of assigning worker $i$ to task $j$ and $\sigma$ is a permutation of assignments. The algorithm guarantees an optimal solution in polynomial time and can handle both square and rectangular matrices.

This example function is provided as-is without any representation of accuracy.

Usage

To use the LINEAR_ASSIGNMENT function in Excel, enter it as a formula in a cell, specifying your cost matrix as a 2D list or Excel range:


=LINEAR_ASSIGNMENT(cost_matrix)

cost_matrix (2D list, required): The cost matrix (m x n) for the assignment. Example: {4,1,3;2,0,5;3,2,2}

The function returns a 2D list of [row, col] pairs representing the optimal assignment, or an error message string if calculation fails.

Examples

Assigning Workers to Tasks

Assign 3 workers to 3 tasks to minimize total cost.


=LINEAR_ASSIGNMENT({4,1,3;2,0,5;3,2,2})

Expected output:

Row	Col
0	1
1	0
2	2

Scheduling Jobs with Unequal Tasks

Assign 3 workers to 4 jobs to minimize total cost (rectangular matrix).


=LINEAR_ASSIGNMENT({10,19,8,15;10,18,7,17;13,16,9,14})

Expected output:

Row	Col
0	0
1	2
2	3

Python Code


import numpy as np
from scipy.optimize import linear_sum_assignment
 
def linear_assignment(cost_matrix):
    """
    Solves the linear assignment problem (Hungarian algorithm) for a given cost matrix.
 
    Args:
        cost_matrix (list[list[float]]): 2D list representing the cost matrix.
 
    Returns:
        list[list[int]]: 2D list of [row, col] assignments, or error message string.
 
    This example function is provided as-is without any representation of accuracy.
    """
    try:
        arr = np.array(cost_matrix)
        if arr.ndim != 2:
            return "Input must be a 2D list (matrix)."
        row_ind, col_ind = linear_sum_assignment(arr)
        assignment = [[int(r), int(c)] for r, c in zip(row_ind, col_ind)]
        return assignment
    except Exception as e:
        return str(e)

Live Notebook

Edit this function in a live notebook .