Constructive Heuristics for Quadratic Assignment Problem (QAP)

Problem

The Quadratic Assignment Problem (QAP) is one of the most challenging combinatorial optimization problems.

• Given: Two matrices - flow matrix (between facilities) and distance matrix (between locations)

• Objective: Assign facilities to locations to minimize total cost

• Constraints: Each facility must be assigned to exactly one location

Algorithm Design Task

The task is to design a constructive heuristic that assigns all facilities to locations in one call.

• Inputs: Flow matrix, distance matrix

• Outputs: Complete assignment (permutation of locations)

Evaluation

• Dataset: 8 instances, 20 facilities

• Fitness: Average total cost (minimized)

Template

template_program = '''
import numpy as np
from typing import List

def select_next_assignment(flow_matrix: np.ndarray, distance_matrix: np.ndarray) -> List[int]:
    """
    Constructive heuristic for the Quadratic Assignment Problem (QAP).

    Args:
        flow_matrix (np.ndarray): shape (n, n)
        distance_matrix (np.ndarray): shape (n, n)

    Returns:
        assignment (List[int]): length-n permutation of {0, ..., n-1}
    """
    n = flow_matrix.shape[0]
    assignment = list(range(n))
    return assignment
'''

task_description = '''
The task is to assign a set of facilities to a set of locations in such a way that
the total cost of interactions between facilities is minimized.
'''

Configuration Parameters

Parameter	Description	Default
timeout_seconds	Maximum evaluation time	60
n_facilities	Number of facilities	20
n_instance	Number of problem instances	8

Example Usage

from llm4ad.task.optimization.qap_construct import QAPEvaluation

evaluator = QAPEvaluation()

def select_next_assignment(flow_matrix, distance_matrix):
    n = flow_matrix.shape[0]
    # Simple greedy assignment
    assignment = list(range(n))
    return assignment

result = evaluator.evaluate_program('', select_next_assignment)