QUADRATIC_ASSIGNMENT

Overview

The QUADRATIC_ASSIGNMENT function wraps scipy.optimize.quadratic_assignment to solve quadratic assignment problems (QAPs). A QAP models the cost of assigning facilities to locations when flow between facilities interacts with distances between locations. The objective is to find a permutation $\pi$ that minimizes

\min_{\pi} \sum_{i=1}^n \sum_{j=1}^n F_{i,j} \cdot D_{\pi(i),\pi(j)}

where $F$ is the flow matrix and $D$ is the distance matrix. This problem arises in facility layout, logistics, and network design. The SciPy solver combines branch-and-bound strategies with linear assignment subproblems to search for the global optimum. This example function is provided as-is without any representation of accuracy.

Usage

To evaluate the function in Excel:


=QUADRATIC_ASSIGNMENT(flow_matrix, distance_matrix)

flow_matrix (2D list, required): Square array describing the interaction or flow between facilities. All rows must have the same length and contain finite numbers.
distance_matrix (2D list, required): Square array of distances or costs between locations. Must have the same shape as flow_matrix and contain finite numbers.

The function returns a 2D list of [facility_index, location_index] assignments achieving the minimum total cost, or an error message string if validation fails or SciPy is unable to solve the problem.

Examples

Example 1: Symmetric 3×3 Layout

Three facilities are assigned to three locations using symmetric flow and distance matrices.

Inputs:

flow_matrix			distance_matrix
0	5	2	0	2	3
5	0	3	2	0	1
2	3	0	3	1	0

Excel formula:


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

Expected output:

Facility	Location
0	2
1	1
2	0

Example 2: Identity Mapping

Two facilities map naturally onto two locations with identical flow and distance patterns.

Inputs:

flow_matrix		distance_matrix
0	1	0	1
1	0	1	0

Excel formula:


=QUADRATIC_ASSIGNMENT({0,1;1,0}, {0,1;1,0})

Expected output:

Facility	Location
0	0
1	1

Example 3: Zero Flow Baseline

When all flows and distances are zero, any permutation is optimal; SciPy returns the identity pairing.

Inputs:

flow_matrix			distance_matrix
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0

Excel formula:


=QUADRATIC_ASSIGNMENT({0,0,0;0,0,0;0,0,0}, {0,0,0;0,0,0;0,0,0})

Expected output:

Facility	Location
0	0
1	1
2	2

Example 4: Diagonal Preference

Unit flows and distances reinforce a diagonal assignment for three facilities.

Inputs:

flow_matrix			distance_matrix
1	0	0	1	0	0
0	1	0	0	1	0
0	0	1	0	0	1

Excel formula:


=QUADRATIC_ASSIGNMENT({1,0,0;0,1,0;0,0,1}, {1,0,0;0,1,0;0,0,1})

Expected output:

Facility	Location
0	0
1	1
2	2

Python Code


from typing import List, Union
 
import numpy as np
from scipy.optimize import quadratic_assignment as scipy_quadratic_assignment
 
 
Number = Union[int, float]
 
 
def quadratic_assignment(
    flow_matrix: List[List[Number]],
    distance_matrix: List[List[Number]],
) -> Union[List[List[int]], str]:
    """Solve a quadratic assignment problem using SciPy's implementation.
 
    Args:
        flow_matrix: Square 2D list describing the flow between facilities. All values must be
            finite numbers and every row must have the same length.
        distance_matrix: Square 2D list describing the distance or cost between locations. Must
            match the shape of ``flow_matrix`` and contain only finite numbers.
 
    Returns:
        2D list of ``[facility_index, location_index]`` assignments minimizing the quadratic
        cost, or an error message string if validation fails or the solver cannot produce a
        solution.
 
    This example function is provided as-is without any representation of accuracy.
    """
    # Normalize scalar inputs (Excel may pass single-element 2D lists as scalars)
    def normalize_to_2d_list(value):
        if not isinstance(value, list):
            return [[value]]
        return value
 
    # Define helper function inside the main function as per Excel Python Function Guidelines
    def _validate_matrix(name: str, matrix: List[List[Number]]) -> Union[np.ndarray, str]:
        if not isinstance(matrix, list) or len(matrix) == 0:
            return f"Invalid input: {name} must be a 2D list with at least one row."
        size: int | None = None
        converted_rows: List[List[float]] = []
        for row_index, row in enumerate(matrix):
            if not isinstance(row, list) or len(row) == 0:
                return f"Invalid input: each row in {name} must be a non-empty list."
            if size is None:
                size = len(row)
            elif len(row) != size:
                return (
                    f"Invalid input: {name} must be square; row {row_index + 1} has a different length."
                )
            converted_row: List[float] = []
            for col_index, value in enumerate(row):
                try:
                    numeric_value = float(value)
                except (TypeError, ValueError):
                    return (
                        f"Invalid input: {name} values must be numeric. "
                        f"Problem at row {row_index + 1}, column {col_index + 1}."
                    )
                if not np.isfinite(numeric_value):
                    return (
                        f"Invalid input: {name} values must be finite. "
                        f"Problem at row {row_index + 1}, column {col_index + 1}."
                    )
                converted_row.append(numeric_value)
            converted_rows.append(converted_row)
        if size is None or size != len(converted_rows):
            return f"Invalid input: {name} must be a square matrix."
        return np.asarray(converted_rows, dtype=float)
 
    flow_matrix = normalize_to_2d_list(flow_matrix)
    distance_matrix = normalize_to_2d_list(distance_matrix)
 
    flow_array_or_error = _validate_matrix("flow_matrix", flow_matrix)
    if isinstance(flow_array_or_error, str):
        return flow_array_or_error
    flow_array = flow_array_or_error
 
    distance_array_or_error = _validate_matrix("distance_matrix", distance_matrix)
    if isinstance(distance_array_or_error, str):
        return distance_array_or_error
    distance_array = distance_array_or_error
 
    if flow_array.shape != distance_array.shape:
        return "Invalid input: flow_matrix and distance_matrix must have the same size."
 
    # Solve the quadratic assignment using SciPy's robust implementation.
    try:
        result = scipy_quadratic_assignment(flow_array, distance_array)
    except Exception as exc:
        return f"quadratic_assignment error: {exc}"
 
    if not hasattr(result, "col_ind") or result.col_ind is None:
        return "quadratic_assignment failed: solver did not return a column assignment."
 
    assignments = [[int(i), int(j)] for i, j in enumerate(result.col_ind.tolist())]
    return assignments

Example Workbook

Link to Workbook