1.2.2

下载 Notebook 下载完整案例

社交高尔夫问题¶

类别： 排程

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

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

问题描述¶

在 社交高尔夫问题 中，我们考虑一个拥有 32 名会员的高尔夫俱乐部。每位会员每周打一次高尔夫，总是 4 人一组。该问题的目标是构建一个为期 10 周的高尔夫会员日程表，使社交最大化，即尽可能减少重复的同组。更一般地，问题是对 m 组 n 名高尔夫爱好者在 p 周内进行调度，以最大化社交。关于更多细节，请参阅 CSPLib 或 MathPuzzle。

学习要点¶

• 使用 OptAgent 的 bool 决策变量建模每周分组
• 使用 and_、sum 和 max 计算每对球员的重复同组次数
• 区分分组决策变量与相遇次数等中间表达式

数据¶

我们提供的 社交高尔夫问题 实例文件包含三个数字：

• 组数
• 每组的大小
• 周数

我们在示例中使用的实例已知存在无重复同组的解。

建模思路¶

社交高尔夫问题的 OptAgent 模型使用布尔变量分配球员。对于每周 w、每组 gr 和每位球员 gf，x[w][gr][gf] 等于 1 表示球员 gf 在第 w 周被分到组 gr，否则为 0。使用 sum 约束每位球员每周恰好属于一个组，并确保每组人数正确。

使用 and_ 计算每周每组中两位球员是否相遇，再对所有周和组求和得到每对球员的相遇总次数。每对球员超过首次相遇的次数通过 max(meetings - 1, 0) 计算，目标是最小化所有球员对重复相遇次数的总和。

Python 实现¶

from pathlib import Path

from optagent import OptModel, solve


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


def read_instance(instance_file):
    nb_groups, group_size, nb_weeks = read_integers(instance_file)
    return nb_groups, group_size, nb_weeks


def main(input_file, output_file=None, time_limit=10):
    nb_groups, group_size, nb_weeks = read_instance(input_file)
    nb_golfers = nb_groups * group_size

    model = OptModel()

    # x[w][gr][gf] is true when golfer gf joins group gr in week w.
    x = [[[model.bool() for _ in range(nb_golfers)] for _ in range(nb_groups)] for _ in range(nb_weeks)]

    # Each golfer is assigned to exactly one group every week.
    for w in range(nb_weeks):
        for gf in range(nb_golfers):
            model.constraint(
                model.sum(x[w][gr][gf] for gr in range(nb_groups)) == 1,
            )

    # Every group contains exactly group_size golfers.
    for w in range(nb_weeks):
        for gr in range(nb_groups):
            model.constraint(
                model.sum(x[w][gr][gf] for gf in range(nb_golfers)) == group_size,
            )

    # Count meetings beyond the first for every pair of golfers.
    redundant_meetings = []
    for gf0 in range(nb_golfers):
        for gf1 in range(gf0 + 1, nb_golfers):
            nb_meetings = model.sum(
                model.and_(x[w][gr][gf0], x[w][gr][gf1]) for w in range(nb_weeks) for gr in range(nb_groups)
            )
            redundant_meetings.append(model.max(nb_meetings - 1, 0))

    objective = model.sum(redundant_meetings)
    model.minimize(objective)

    solution = solve(model, time_limit_s=float(time_limit))
    if not solution.feasible:
        print(f"No feasible schedule found; Status = {solution.status}")
        return solution

    display_lines = [
        f"Groups = {nb_groups}; Group size = {group_size}; Weeks = {nb_weeks}; "
        f"Redundant meetings = {objective.value}; Status = {solution.status}"
    ]
    output_lines = [str(objective.value)]
    for w in range(nb_weeks):
        display_lines.append(f"Week {w + 1}")
        for gr in range(nb_groups):
            golfers = [gf for gf in range(nb_golfers) if x[w][gr][gf].value]
            golfer_text = " ".join(str(gf) for gf in golfers)
            display_lines.append(f"  Group {gr + 1}: {golfer_text}")
            output_lines.append(golfer_text)
        output_lines.append("")

    result_text = "\n".join(display_lines)
    print(result_text)
    if output_file is not None:
        Path(output_file).write_text(
            "\n".join(output_lines) + "\n",
            encoding="utf-8",
        )
    return solution

本地运行¶

Notebook 直接调用 main 并显式传入实例路径。以下代码格相互独立，可以按需要单独运行；较大实例可能需要更长的 time_limit。

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

solution_c4_3_3 = main(
    INSTANCE_DIR / "c_4_3_3.in",
    time_limit=1,
)

solution_c7_5_5 = main(
    INSTANCE_DIR / "c_7_5_5.in",
    time_limit=1,
)

solution_c10_10_3 = main(
    INSTANCE_DIR / "c_10_10_3.in",
    time_limit=1,
)