QUAD_ASSIGN

Overview

The QUAD_ASSIGN function solves the Quadratic Assignment Problem (QAP), one of the fundamental combinatorial optimization problems in operations research. First introduced by Koopmans and Beckmann (1957), QAP models facility location scenarios where the goal is to assign a set of facilities to locations in a way that minimizes the total cost based on both the flow between facilities and the distances between locations.

Given a set of n facilities and n locations, along with a flow matrix F (where F_{ij} represents the interaction or transport flow between facilities i and j) and a distance matrix D (where D_{kl} represents the distance between locations k and l), the problem seeks an assignment that minimizes:

\min_{P \in \Pi_n} \text{trace}(F^T P D P^T)

where \Pi_n is the set of all n \times n permutation matrices. Intuitively, this formulation encourages facilities with high flows between them to be placed at locations that are close together.

This implementation uses SciPy’s quadratic_assignment function, which employs the Fast Approximate QAP (FAQ) algorithm by default. The FAQ method, described by Vogelstein et al. (2015), provides an effective balance between computational speed and solution quality. Since QAP is NP-hard, no polynomial-time algorithm exists that guarantees an optimal solution for all instances. The results returned are approximations and may not be globally optimal.

Common applications of QAP include facility layout planning (e.g., arranging departments in a building to minimize transport costs), placement of electronic components on circuit boards, keyboard layout optimization, and graph matching problems where node alignment is required.

The function returns a list of facility-to-location assignment pairs, representing the optimal (or near-optimal) mapping found by the solver.

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

Excel Usage

=QUAD_ASSIGN(flow_matrix, distance_matrix)

flow_matrix (list[list], required): Square array describing the interaction or flow quantity between facilities, where flow_matrix[i][j] is the flow from facility i to facility j
distance_matrix (list[list], required): Square array of distances or costs between locations, where distance_matrix[i][j] is the distance from location i to location j

Returns (list[list]): 2D list of [[facility, location]] pairs representing optimal assignments, or error message string.

Examples

Example 1: Demo case 1

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:

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

Expected output:

Result
0	2
1	1
2	0

Example 2: Demo case 2

Inputs:

flow_matrix		distance_matrix
0	1	0	1
1	0	1	0

Excel formula:

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

Expected output:

Result
0	0
1	1

Example 3: Demo case 3

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:

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

Expected output:

Result
0	0
1	1
2	2

Example 4: Demo case 4

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:

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

Expected output:

Result
0	0
1	1
2	2

Python Code

import numpy as np
from scipy.optimize import quadratic_assignment as scipy_quadratic_assignment

def quad_assign(flow_matrix, distance_matrix):
    """
    Solve a quadratic assignment problem using SciPy's implementation.

    See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.quadratic_assignment.html

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

    Args:
        flow_matrix (list[list]): Square array describing the interaction or flow quantity between facilities, where flow_matrix[i][j] is the flow from facility i to facility j
        distance_matrix (list[list]): Square array of distances or costs between locations, where distance_matrix[i][j] is the distance from location i to location j

    Returns:
        list[list]: 2D list of [[facility, location]] pairs representing optimal assignments, or error message string.
    """
    def to2d(x):
        return [[x]] if not isinstance(x, list) else x

    flow_matrix = to2d(flow_matrix)
    distance_matrix = to2d(distance_matrix)

    def _validate_matrix(name, matrix):
        if not isinstance(matrix, list) or len(matrix) == 0:
            return f"Error: {name} must be a 2D list with at least one row."
        size = None
        converted_rows = []
        for row_index, row in enumerate(matrix):
            if not isinstance(row, list) or len(row) == 0:
                return f"Error: Each row in {name} must be a non-empty list."
            if size is None:
                size = len(row)
            elif len(row) != size:
                return f"Error: {name} must be square; row {row_index + 1} has a different length."
            converted_row = []
            for col_index, value in enumerate(row):
                try:
                    numeric_value = float(value)
                except (TypeError, ValueError):
                    return (
                        f"Error: {name} values must be numeric. "
                        f"Problem at row {row_index + 1}, column {col_index + 1}."
                    )
                if not np.isfinite(numeric_value):
                    return (
                        f"Error: {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"Error: {name} must be a square matrix."
        return np.asarray(converted_rows, dtype=float)

    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 "Error: flow_matrix and distance_matrix must have the same size."

    try:
        result = scipy_quadratic_assignment(flow_array, distance_array)
    except Exception as exc:
        return f"Error: Solver error: {exc}"

    if not hasattr(result, "col_ind") or result.col_ind is None:
        return "Error: Solver did not return a valid assignment."

    assignments = [[int(i), int(j)] for i, j in enumerate(result.col_ind.tolist())]
    return assignments

Overview

Excel Usage

Examples

Python Code

Online Calculator