带赛区约束的乒乓球Swiss赛制年度排程技术求助

背景与约束 #

• 年度举办8场乒乓球展示赛，每场参赛选手数量不固定（如48人、20人），部分选手会参加多场甚至全部赛事
• 选手的rank（排名）在年初即固定，全年不会变更
• 每场赛事包含3轮，每轮所有选手必须进行一场比赛，需满足以下约束：
  1. 全年内选手之间不能重复对阵
  2. 选手不能与同赛区（conference）的对手比赛
  3. 对阵需基于相近rank匹配

现有问题 #

尝试用Python实现Swiss赛制进行排程，但生成的结果不稳定，无法保证每轮所有选手都完成配对。问题源于常规Swiss赛制仅以rank为约束，而当前需要同时兼顾rank与赛区限制。

现有实现代码 #

class Player:
    def __init__(self, name, rating, area):
        self.name = name
        self.rating = rating
        self.area = area
        self.games_played = 0

def optimize_pairings(players, pairings_history, round_num):
    # 确保选手列表仅包含Player对象
    if not all(isinstance(player, Player) for player in players):
        raise ValueError("选手列表中存在无效对象。")

    # 为每对选手创建二进制变量
    pair_vars = pulp.LpVariable.dicts("Pair", ((p1, p2) for p1 in players for p2 in players if p1 != p2), cat='Binary')

    # 创建PuLP最小化问题
    prob = pulp.LpProblem("Pairing Optimization", pulp.LpMinimize)

    # 目标函数：最小化配对选手的总rank差值
    prob += pulp.lpSum(pair_vars[(p1, p2)] * abs(p1.rating - p2.rating) for p1 in players for p2 in players if p1 != p2)

    # 添加约束条件
    for p1 in players:
        prob += pulp.lpSum(pair_vars[(p1, p2)] for p2 in players if p1 != p2) == 1  # 每位选手恰好配对1名对手

    for p1 in players:
        for p2 in players:
            if p1 != p2:
                prob += pair_vars[(p1, p2)] + pair_vars[(p2, p1)] <= 1  # 避免双向重复配对计数

    for p1 in players:
        for p2 in players:
            if p1 != p2 and p1.area == p2.area:
                prob += pair_vars[(p1, p2)] == 0  # 禁止同赛区选手配对

    # 排除过往赛事已使用过的配对
    for (p1, p2) in pair_vars.keys():
        if (p1, p2) in pairings_history or (p2, p1) in pairings_history:
            prob += pair_vars[(p1, p2)] == 0

    # 求解整数线性规划问题
    prob.solve()

    # 提取配对结果
    paired_players = [(p1, p2) for (p1, p2), var in pair_vars.items() if pulp.value(var) == 1]

    # 更新配对历史记录
    pairings_history.update({(p1, p2) for (p1, p2) in paired_players})

    return paired_players

求助需求 #

寻求合适的算法、Python包建议，或更优的问题解决思路。

内容的提问来源于stack exchange，提问作者WeAreChatGPT