QUADRATIC_ASSIGNMENT

Overview

The QUADRATIC_ASSIGNMENT function solves the quadratic assignment problem (QAP), a classic combinatorial optimization problem in operations research. The QAP models the assignment of a set of facilities to a set of locations with the goal of minimizing the total cost, which is determined by the flow between facilities and the distance between locations. Mathematically, the objective is to find a permutation $\pi$ that minimizes:

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

This function uses scipy.optimize.quadratic_assignment to efficiently solve the QAP for small to medium-sized matrices. The QAP is widely used in facility layout, keyboard design, and other resource allocation problems. See the scipy.optimize.quadratic_assignment documentation for more details. This example function is provided as-is without any representation of accuracy.

Usage

To use the QUADRATIC_ASSIGNMENT function in Excel, enter it as a formula in a cell, specifying your flow and distance matrices as 2D lists or Excel ranges:


=QUADRATIC_ASSIGNMENT(flow_matrix, distance_matrix)

flow_matrix (2D list of float, required): The flow between facilities (square matrix).
distance_matrix (2D list of float, required): The distances between locations (square matrix).

The function returns a 2D list of [facility, location] pairs representing the optimal assignment, or an error message string if the input is invalid.

Examples

Example 1: Assigning Facilities to Minimize Cost

Assign 3 facilities to 3 locations to minimize total cost.

In Excel:


=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: Handling Invalid Input

If the matrices are not square or not the same size, an error message is returned.

In Excel:


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

Expected output:

“Both matrices must be square and of the same size.”

Python Code


import numpy as np
from scipy.optimize import quadratic_assignment as scipy_quadratic_assignment
 
def quadratic_assignment(flow_matrix, distance_matrix):
    """Solves the quadratic assignment problem (QAP) for given flow and distance matrices.
 
    Args:
        flow_matrix (list[list[float]]): 2D list representing the flow between facilities (square matrix).
        distance_matrix (list[list[float]]): 2D list representing the distances between locations (square matrix).
 
    Returns:
        list[list[int]]: 2D list of [facility, location] assignments, or error message string.
 
    This example function is provided as-is without any representation of accuracy.
    """
    flow = np.array(flow_matrix)
    dist = np.array(distance_matrix)
    if flow.ndim != 2 or dist.ndim != 2:
        return "Both inputs must be 2D lists (matrices)."
    if flow.shape != dist.shape or flow.shape[0] != flow.shape[1]:
        return "Both matrices must be square and of the same size."
    result = scipy_quadratic_assignment(flow, dist)
    if not hasattr(result, 'col_ind'):
        return str(result)
    assignment = [[int(i), int(j)] for i, j in enumerate(result.col_ind)]
    return assignment

Live Notebook

Edit this function in a live notebook .