如何用混合整数规划（MILP）优化游泳队阵容分配

本文介绍如何将游泳队阵容分配问题建模为混合整数线性规划（milp）问题，使用 gekko 求解器在满足每人最多参赛 m 项、每项最多派 n 名队员等约束下，最大化团队平均能力评分（rating），显著优于贪心排序法。

游泳队阵容优化本质上是一个带多重资源约束的分配问题：既要为每个比赛项目（如 50 米自由泳、100 米混合泳）分配最合适的运动员，又要确保每位运动员参赛总数不超过上限（MaxEntriesPerSwimmer = M），且每项赛事派出人数不超配额（MaxSwimmersPerTeam = N）。简单按评分降序“贪心填充”的策略容易陷入局部最优——正如示例中，优先选 Swimmer1 的 Event1（900 分）会阻塞其更优的 Event2 参赛机会，反而导致整体平均分下降（825 vs 理论最优 845）。要获得全局最优解，需采用精确数学规划方法。

推荐使用 Mixed Integer Linear Programming（MILP） 建模，其核心思想是引入二元决策变量 x_{s,e} 表示“是否安排 Swimmer s 参加 Event e”，再通过线性约束编码业务规则，目标函数直接最大化总评分（或平均评分，因事件数固定，等价于最大化总分）。

以下是一个可运行的 Gekko 实现示例（已适配您的数据结构）：

from gekko import GEKKO

# 初始化模型（local 求解，无需远程服务器）
model = GEKKO(remote=False)

# 定义实体：运动员与项目（请替换为真实 ID 列表）
swimmers = ['S1', 'S2', 'S3']  # 如 [1, 2, 3]
events   = ['E1', 'E2']  
      # 如 [1, 2]

# 构建评分字典：(swimmer_id, event_id) -> rating（从原始数据中提取）
# 注意：仅包含该运动员实际游过的项目，缺失项不定义即可
rating = {
    ('S1', 'E1'): 900.0,  # Swimmer1 在 Event1 的评分
    ('S1', 'E2'): 800.0,  # Swimmer1 在 Event2 的评分
    ('S2', 'E1'): 890.0,  # Swimmer2 在 Event1 的评分
    ('S2', 'E2'): 750.0,  # Swimmer2 在 Event2 的评分
}

# 决策变量：x[s,e] ∈ {0,1}，1 表示分配，0 表示不分配
x = {}
for s in swimmers:
    for e in events:
        x[(s, e)] = model.Var(lb=0, ub=1, integer=True)

# 目标函数：最大化总评分（等价于最大化平均分）
total_score = sum(rating.get((s, e), 0) * x.get((s, e), 0) for s in swimmers for e in events)
model.Maximize(total_score)

# 约束1：每人最多参加 M 项（例如 M = 1）
M = 1
for s in swimmers:
    model.Equation(model.sum([x[(s, e)] for e in events]) <= M)

# 约束2：每项最多派 N 名队员（例如 N = 1）
N = 1
for e in events:
    model.Equation(model.sum([x[(s, e)] for s in swimmers]) == N)  # 或 <= N，视规则而定

# 求解（自动选择 APOPT 求解器）
model.options.SOLVER = 1  # APOPT for MINLP
model.solve(disp=True)

# 输出结果
print("\n=== 最优阵容分配 ===")
for s in swimmers:
    for e in events:
        if x[(s, e)].value[0] > 0.5:  # 判定为 1
            print(f"✓ {s} → {e} (rating: {rating.get((s, e), '?')})")

✅ 关键优势：

• 全局最优保证：MILP 求解器（如 APOPT）能严格证明所得解为数学最优，彻底规避贪心法的次优陷阱；
• 灵活约束支持：轻松扩展约束，如增加接力项目绑定（同一组队员必须同时入选）、禁止冲突项目（如 100m 自由泳与 100m 蛙泳时间重叠）、设置最低参赛人数等；
• 评分标准化友好：rating 字段天然适配跨项目比较，无需额外归一化处理。

⚠️ 注意事项：

• 数据预处理：确保 rating 字典只包含有效 (swimmer_id, event_id) 对；缺失组合自动视为不可选（评分为 0 或不参与求和）；
• 规模限制：Gekko 在百级变量内高效，若队伍/项目规模极大（>1000 变量），建议切换至 Pyomo + CBC/GLPK 或商业求解器（Gurobi/Cplex）；
• 初始化提速：可先用贪心解作为 warm-start（x.varvalue = greedy_value），加速收敛；
• 整数性容差：检查 x.value[0] 时建议用 > 0.5 而非 == 1.0，避免浮点误差。

总结而言，将阵容分配转化为 MILP 是兼顾准确性、可解释性与工程落地性的最佳路径。它把教练的经验直觉（约束）与数据驱动的客观评分（目标）统一于严谨数学框架，让每一次排兵布阵都经得起逻辑推敲——这正是智能体育决策的核心所在。