二次分配问题 (QAP)¶

类别： 选址

使用 OptAgent 的 Python 接口描述变量、约束与目标。

问题与原始示例来源：Hexaly Code Templates。

问题描述¶

在 Quadratic Assignment Problem (QAP) 中，需要将 n 个设施分配到 n 个位置。问题数据包含每对位置之间的距离以及每对设施之间的流量（或权重），即它们之间运输的物料量。问题目标是将每个设施分配到一个位置，使距离与对应流量乘积之和最小。该问题类似于指派问题（Assignment Problem），不同之处在于其目标函数由二次不等式表示，因此得名。更多细节，请参阅 QAPLIB 网页。

学习要点¶

添加列表决策变量来建模设施的排列
使用 ‘count’ operator 约束 list 中的元素数量
使用 ‘at’ operator 访问 list 中的元素以定义目标函数

数据¶

我们提供来自 QAPLIB 的实例。数据文件的格式如下：

点的数量
矩阵 A：每对位置之间的距离
矩阵 B：每对设施之间的流量

建模思路¶

Quadratic Assignment Problem (QAP) 的 OptAgent 模型仅使用一个列表决策变量。该 list 表示设施的一个排列：list 中第 i 个位置的元素表示分配到位置 i 的设施索引。

使用 count 算子，我们将 list 的大小约束为等于设施总数。从而确保所有设施都被分配到一个位置。

最后，我们计算目标函数。使用 at 算子，我们可以访问分配到位置 i 的设施（p[i]，其中 p 是 list 变量）。然后我们可以轻松地获取分配到位置 i 和 j 的设施之间的流量（B[p[i]][p[j]]）。将该数量乘以位置 i 和 j 之间的距离（A[i][j]），即可得到与这两个设施相关联的成本。

Python 实现¶

# Copyright (c) Hexaly. Permission is hereby granted to use, copy,
# and modify this code for applications developed with Hexaly.
from pathlib import Path

from optagent import OptModel, solve


def read_integers(filename):
    return [int(elem) for elem in Path(filename).read_text(encoding="utf-8").split()]


def read_instance(filename):
    file_it = iter(read_integers(filename))

    # Number of points
    n = next(file_it)

    # Distance between locations
    distances = [[next(file_it) for _ in range(n)] for _ in range(n)]
    # Flow between factories
    flows = [[next(file_it) for _ in range(n)] for _ in range(n)]
    return n, distances, flows


def main(instance_file, output_file=None, time_limit=30):
    n, distances, flows = read_instance(instance_file)
    model = OptModel()

    # Permutation such that p[i] is the facility on the location i
    permutation = model.list(n)

    # The list must be complete
    model.constraint(model.count(permutation) == n)

    # Create the flow matrix as a model array for expression-based indexing.
    flow_array = model.array(flows)

    # Minimize the sum of product distance*flow
    objective = model.sum(
        distances[i][j] * flow_array[permutation[i], permutation[j]]
        for i in range(n)
        for j in range(n)
    )
    model.minimize(objective)

    solution = solve(model, time_limit_s=float(time_limit))
    print(
        f"Facilities = {n}; Objective = {objective.value}; "
        f"Status = {solution.feasible}"
    )

    #
    # Write the solution in a file with the following format:
    #  - n objValue
    #  - permutation p
    #
    if output_file is not None:
        result_text = (
            f"{n} {objective.value}\n"
            + " ".join(str(facility) for facility in permutation.value)
            + "\n"
        )
        Path(output_file).write_text(result_text, encoding="utf-8")
    return solution

实例调用¶

下面使用仓库提供的 QAPLIB 实例运行模型。

INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)

solution_qap = main(INSTANCE_DIR / "nug30.dat", time_limit=1)
solution_qap.feasible