OR-Tools CP-SAT求解器中如何约束团队多轮比赛固定分组？

场景描述 #

• 实际场景：组织200余支队伍的锦标赛，划分为40+个小组，每组进行4轮比赛。队伍按年龄和实力分入对应组别，最终目标是最小化所有队伍的总驾驶距离。
• 简化测试场景：12支队伍，分为3个小组（每组4支队伍），进行2轮比赛。第一轮分组有预设可选池：

[[1,2,3,4,5],       # 第1组可从这5支队伍中选4支
 [5,6,7,8,9],        # 第2组可从这5支队伍中选4支
 [8,9,10,11,12]]     # 第3组可从这5支队伍中选4支

例如，第一轮第1组若为[1,2,3,4]，则对阵为1 vs 2、3 vs 4。

核心需求 #

需要为第二轮赛程满足以下约束：

1. 每个小组的成员在所有轮次中保持固定，仅排列顺序可变化（比如第一轮第1组是[1,2,3,4]，第二轮可以是[1,3,2,4]、[1,4,2,3]等所有可能排列，不同排列会影响驾驶距离）。
2. 每支队伍仅与另一支队伍交手一次，即第二轮的对阵组合不能与第一轮重复。

尝试过使用AddAllowedAssignments和AddElement的多种变体，但因分组是求解过程中动态确定的，而非预先定义，未能成功实现需求，寻求可行解决方案。

原始代码 #

from ortools.sat.python import cp_model
def main():

    # 体育锦标赛
    # 队伍根据实力和年龄分组
    # 制定3轮比赛计划，每组4支队伍两两交手一次
      
    GroupsList = [] # 存储允许的分组组合的列表
    GroupsTempList = []
        
    GroupTypeList = [[1,2,3,4,5],    # 第1组可从1、2、3、4、5这5支队伍中选4支
                    [5,6,7,8,9],     # 第2组可从5、6、7、8、9这5支队伍中选4支
                    [8,9,10,11,12]]  # 第3组可从8、9、10、11、12这5支队伍中选4支
            
    num_teams = max([max(i) for i in GroupTypeList])  # 队伍总数 = 12
           
    Groups = len(GroupTypeList)   # 小组数量 =3
    GroupSize = 4 # 每组4支队伍    
    rounds = 2
     
    GroupsList  = [     # 可能的组合列表
    [[2,3,4,5],[1,2,3,5],[1,2,4,5],[1,3,4,5],[1,2,3,4]],  # 第1组的可能组合
    [[5,6,7,8],[5,6,7,9],[5,6,8,9],[5,7,8,9],[6,7,8,9]],  # 第2组的可能组合
    [[8,9,10,11],[8,9,10,12],[8,10,11,12],[9,10,11,12]]   # 第3组的可能组合
    ]
    
# 模型
    model = cp_model.CpModel()
  
# 变量 NewIntVar(1-12)
    Teams = {}
    for r in range(rounds):
        for i in range(Groups):
            for j in range(GroupSize):
                Teams[(r, i, j)] = model.NewIntVar(1, num_teams, 'Teams %i %i %i' % (r, i, j))
  
# 约束条件   
# 确保队伍被分到允许的小组中，检查组合列表
    for i in range(Groups):   
        model.AddAllowedAssignments([Teams[(0,i,j)] for j in range(GroupSize)],GroupsList[i],)
                        
# 所有队伍均需被分配，且无重复分配
    for r in range(rounds):
        AllTeams = []
        for i in range(Groups):
            for j in range(GroupSize):
                AllTeams.append(Teams[r,i,j])
        model.AddAllDifferent(AllTeams)  
    
# 强制非最优解，确保队伍8被分到第3组   
    model.Add(Teams[(0,2,0)]==8) 

# 缺失的约束条件    
#1    第1组的队伍在所有3轮比赛中均留在第1组

#     （若第一轮第1组为[1,2,3,4]，则对阵为1 vs 2、3 vs 4）
#2     每支队伍仅与另一支队伍交手一次。因此第二轮第1组
# 可以是[1,3,2,4]，第三轮为[1,4,2,3]
        
# 求解                   
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

# 打印分组  
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        for r in range(rounds):
            print('Round ',r+1)    
            for i in range(Groups):
                print ('Group',i+1,end = "") 
                print([int(solver.Value(Teams[(r,i, j)])) for j in range(GroupSize)])
           

if __name__ == '__main__':
    main()

可行解决方案 #

1. 固定小组成员的约束 #

为每个小组添加约束，确保后续轮次的小组是第一轮小组的排列（成员不变，仅顺序调整）：

• 先获取第一轮每个小组的队伍变量，然后约束后续轮次的每个队伍都属于该小组，且无重复。

2. 避免重复对阵的约束 #

每组4支队伍共有6种两两对阵组合，需确保每轮的对阵组合不重复。通过将对阵对转换为无序对（如min(a,b)和max(a,b)），约束不同轮次的对阵对不相同。

调整后的完整代码 #

from ortools.sat.python import cp_model

def main():
    # 体育锦标赛
    # 队伍根据实力和年龄分组
    # 制定3轮比赛计划，每组4支队伍两两交手一次
      
    GroupsList = [] # 存储允许的分组组合的列表
    GroupsTempList = []
        
    GroupTypeList = [[1,2,3,4,5],    # 第1组可从1、2、3、4、5这5支队伍中选4支
                    [5,6,7,8,9],     # 第2组可从5、6、7、8、9这5支队伍中选4支
                    [8,9,10,11,12]]  # 第3组可从8、9、10、11、12这5支队伍中选4支
            
    num_teams = max([max(i) for i in GroupTypeList])  # 队伍总数 = 12
           
    Groups = len(GroupTypeList)   # 小组数量 =3
    GroupSize = 4 # 每组4支队伍    
    rounds = 2
     
    GroupsList  = [     # 可能的组合列表
    [[2,3,4,5],[1,2,3,5],[1,2,4,5],[1,3,4,5],[1,2,3,4]],  # 第1组的可能组合
    [[5,6,7,8],[5,6,7,9],[5,6,8,9],[5,7,8,9],[6,7,8,9]],  # 第2组的可能组合
    [[8,9,10,11],[8,9,10,12],[8,10,11,12],[9,10,11,12]]   # 第3组的可能组合
    ]
    
    # 模型
    model = cp_model.CpModel()
  
    # 变量 NewIntVar(1-12)
    Teams = {}
    for r in range(rounds):
        for i in range(Groups):
            for j in range(GroupSize):
                Teams[(r, i, j)] = model.NewIntVar(1, num_teams, 'Teams %i %i %i' % (r, i, j))
  
    # 约束条件   
    # 确保队伍被分到允许的小组中，检查组合列表
    for i in range(Groups):   
        model.AddAllowedAssignments([Teams[(0,i,j)] for j in range(GroupSize)],GroupsList[i],)
                        
    # 所有队伍均需被分配，且无重复分配
    for r in range(rounds):
        AllTeams = []
        for i in range(Groups):
            for j in range(GroupSize):
                AllTeams.append(Teams[r,i,j])
        model.AddAllDifferent(AllTeams)  
    
    # 强制非最优解，确保队伍8被分到第3组   
    model.Add(Teams[(0,2,0)]==8) 

    # 约束1：每个小组的成员在所有轮次保持一致（仅排列不同）
    for i in range(Groups):
        round0_group = [Teams[(0, i, j)] for j in range(GroupSize)]
        for r in range(1, rounds):
            roundr_group = [Teams[(r, i, j)] for j in range(GroupSize)]
            # 后续轮次的每个队伍必须属于第一轮该小组
            for team in roundr_group:
                model.Add(team.In(round0_group))
            # 后续轮次小组内无重复
            model.AddAllDifferent(roundr_group)
    
    # 约束2：每支队伍仅与另一支交手一次（处理所有小组）
    def get_match_pairs(group_teams):
        pairs = []
        # 按顺序两两配对（0&1，2&3）
        for idx in range(0, GroupSize, 2):
            a = group_teams[idx]
            b = group_teams[idx+1]
            # 生成无序对，避免(a,b)和(b,a)被视为不同
            min_pair = model.NewIntVar(1, num_teams, f'min_pair_{idx}')
            max_pair = model.NewIntVar(1, num_teams, f'max_pair_{idx}')
            model.Add(min_pair == cp_model.Min(a, b))
            model.Add(max_pair == cp_model.Max(a, b))
            pairs.append((min_pair, max_pair))
        return pairs
    
    for i in range(Groups):
        all_pairs = []
        for r in range(rounds):
            group_teams = [Teams[(r, i, j)] for j in range(GroupSize)]
            current_pairs = get_match_pairs(group_teams)
            all_pairs.extend(current_pairs)
            # 当前轮对阵对不与之前轮次重复
            for prev_idx in range(len(all_pairs) - len(current_pairs)):
                prev_min, prev_max = all_pairs[prev_idx]
                for curr_min, curr_max in current_pairs:
                    model.AddBoolOr([prev_min != curr_min, prev_max != curr_max])
    
    # 求解                   
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    # 打印分组  
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        for r in range(rounds):
            print('Round ',r+1)    
            for i in range(Groups):
                print ('Group',i+1,end = "") 
                print([int(solver.Value(Teams[(r,i, j)])) for j in range(GroupSize)])
            print()

if __name__ == '__main__':
    main()

内容的提问来源于stack exchange，提问作者Carsten Nørgård