LINEAR_ASSIGNMENT

Overview

The LINEAR_ASSIGNMENT function solves the classic assignment problem by wrapping scipy.optimize.linear_sum_assignment. The Hungarian algorithm searches for the minimum-cost pairing between rows and columns of a rectangular cost matrix by iteratively subtracting row and column minima, covering zeros, and adjusting uncovered entries until the optimal permutation is found. This is useful for staffing, scheduling, transportation, and other logistics scenarios where each worker or resource must be matched to exactly one task. This example function is provided as-is without any representation of accuracy.

Usage

To evaluate the function in Excel:


=LINEAR_ASSIGNMENT(cost_matrix)

cost_matrix (2D list, required): Numeric matrix of assignment costs. Must have at least one row and one column, and each row must contain the same number of columns.

The function returns a 2D list of [row_index, column_index] pairs describing the optimal assignment, or a string error message if validation fails or the solver cannot find a solution.

Examples

Example 1: Balanced 3×3 Assignment

This example matches three workers to three jobs using a square cost matrix.

Inputs:

cost_matrix
4	1	3
2	0	5
3	2	2

Excel formula:


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

Expected output:

Assignment Row	Assignment Column
0	1
1	0
2	2

Example 2: Rectangular 3×4 Assignment

Three sales teams are assigned to four territories with differing costs.

Inputs:

cost_matrix
10	19	8	15
10	18	7	17
13	16	9	14

Excel formula:


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

Expected output:

Assignment Row	Assignment Column
0	0
1	2
2	3

Example 3: Balanced 4×4 Matrix

Four machines are matched to four production jobs, with optional overtime costs included.

Inputs:

cost_matrix
9	2	7	8
6	4	3	7
5	8	1	8
7	6	9	4

Excel formula:


=LINEAR_ASSIGNMENT({9,2,7,8;6,4,3,7;5,8,1,8;7,6,9,4})

Expected output:

Assignment Row	Assignment Column
0	1
1	0
2	2
3	3

Example 4: Rectangular 2×3 Matrix

Two vehicles are assigned to three delivery routes, minimizing travel time.

Inputs:

cost_matrix
3	1	2
4	6	5

Excel formula:


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

Expected output:

Assignment Row	Assignment Column
0	1
1	0

Python Code


from typing import List, Union
 
import numpy as np
from scipy.optimize import linear_sum_assignment
 
 
Number = Union[int, float]
 
 
def linear_assignment(cost_matrix: List[List[Number]]) -> Union[List[List[int]], str]:
    """Solve the linear assignment problem using scipy.optimize.linear_sum_assignment.
 
    This function solves the assignment problem by finding the minimum-cost pairing
    between rows and columns of a rectangular cost matrix. It uses the Hungarian algorithm
    implementation from SciPy to find the optimal assignment.
    For more information: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html
 
    Args:
        cost_matrix: 2D list representing the assignment costs. Each row must have the same
            number of columns, the matrix must contain at least one row and one column, and
            every value must be a finite number.
 
    Returns:
        2D list of ``[row_index, column_index]`` pairs describing the optimal assignment, or
        an error message string if the input is invalid or the solver fails.
 
    This example function is provided as-is without any representation of accuracy.
    """
    # Normalize scalar inputs (single-element 2D lists may be passed as scalars)
    def normalize_to_2d_list(value):
        if not isinstance(value, list):
            return [[value]]
        return value
 
    cost_matrix = normalize_to_2d_list(cost_matrix)
 
    if not isinstance(cost_matrix, list) or len(cost_matrix) == 0:
        return "Invalid input: cost_matrix must be a 2D list with at least one row."
 
    column_count: int | None = None
    validated_rows: List[List[float]] = []
 
    # Validate structure and convert each value to a finite float.
    for row_index, row in enumerate(cost_matrix):
        if not isinstance(row, list) or len(row) == 0:
            return "Invalid input: each row of cost_matrix must be a non-empty list."
        if column_count is None:
            column_count = len(row)
        elif len(row) != column_count:
            return "Invalid input: all rows in cost_matrix must have the same length."
 
        converted_row: List[float] = []
        for col_index, value in enumerate(row):
            try:
                numeric_value = float(value)
            except (TypeError, ValueError):
                return (
                    "Invalid input: cost_matrix values must be numeric. "
                    f"Problem at row {row_index + 1}, column {col_index + 1}."
                )
            if not np.isfinite(numeric_value):
                return (
                    "Invalid input: cost_matrix values must be finite. "
                    f"Problem at row {row_index + 1}, column {col_index + 1}."
                )
            converted_row.append(numeric_value)
        validated_rows.append(converted_row)
 
    # Convert to a NumPy array for SciPy compatibility.
    cost_array = np.asarray(validated_rows, dtype=float)
    if cost_array.ndim != 2:
        return "Invalid input: cost_matrix must be a 2D list."
 
    # Call SciPy's Hungarian algorithm implementation to solve the assignment problem.
    try:
        row_indices, col_indices = linear_sum_assignment(cost_array)
    except Exception as exc:
        return f"linear_sum_assignment error: {exc}"
 
    # Build the result as a 2D list of integer index pairs.
    assignment: List[List[int]] = [
        [int(row), int(col)] for row, col in zip(row_indices.tolist(), col_indices.tolist())
    ]
    return assignment

Example Workbook

Link to Workbook