如何用混合整数规划（MIP）为游泳队优化选手出场阵容

如何用混合整数规划（MIP）为游泳队优化选手出场阵容第1张

本文介绍如何将游泳队 lineup 问题建模为混合整数线性规划（milp），利用 `gekko` 等优化库求解全局最优阵容，在满足每项赛事最多 n 名队员、每人最多参加 m 项赛事的约束下，最大化平均能力评分（rating）。

在竞技游泳团队管理中，科学分配选手参赛项目是提升整体竞争力的关键。简单按个人单项评分贪心排序（如优先选 rating 最高的组合）常导致次优解——正如示例中：贪心法选得 (900 + 750)/2 = 825 的平均分，而交换人选后可达 (890 + 800)/2 = 845。这种“局部最优≠全局最优”的困境，本质是带多重耦合约束的组合优化问题，需借助数学规划方法建模求解。

核心建模思路

我们将问题抽象为一个二元决策变量系统：对每个（swimmer, event）对定义变量 $ x_{s,e} \in {0,1} $，表示该选手是否被安排参加该项目。目标函数与约束条件如下：

目标函数（最大化总评分）：
$$ \max \sum{s \in S} \sum{e \in E} \text{rating}{s,e} \cdot x{s,e} $$ （注意：最大化总分等价于最大化平均分，因总事件数固定）
每人参赛上限约束（MaxEntriesPerSwimmer = M）：
$$ \forall s \in S: \quad \sum{e \in E} x{s,e} \leq M $$
每项赛事人数上限约束（MaxSwimmersPerTeam = N）：
$$ \forall e \in E: \quad \sum{s \in S} x{s,e} \leq N $$
变量类型约束：所有 $ x_{s,e} $ 为 0–1 整数变量。

✅ 提示：若某选手未游过某项目，直接不定义对应变量或设 rating = -∞（实际代码中可跳过该键值对）。

使用 Gekko 实现完整求解流程

以下是一个生产就绪的简化实现（适配您原始数据结构）：

from gekko import GEKKO
import pandas as pd

# 假设原始数据已加载为列表
team_1_best_times = [
    {"time_id": 1, "swimmer_id": 1, "event_id": 1, "time": 22.00, "rating": 900.00},
    {"time_id": 2, "swimmer_id": 1, "event_id": 2, "time": 44.00, "rating": 800.00},
    {"time_id": 3, "swimmer_id": 2, "event_id": 1, "time": 22.10, "rating": 890.00},
    {"time_id": 4, "swimmer_id": 2, "event_id": 2, "time": 46.00, "rating": 750.00},
]

# 构建映射：(swimmer_id, event_id) → rating
rating_map = {}
swimmers = set()
events = set()
for rec in team_1_best_times:
    sid, eid = rec["swimmer_id"], rec["event_id"]
    swimmers.add(sid)
    events.add(eid)
    rating_map[(sid, eid)] = rec["rating"]

# 初始化模型
m = GEKKO(remote=False)
m.options.SOLVER = 1  # APOPT 求解器，支持整数规划

# 定义二元变量：x[sid, eid]
x = {}
for sid in swimmers:
    for eid in events:
        if (sid, eid) in rating_map:
            x[(sid, eid)] = m.Var(lb=0, ub=1, integer=True)
        else:
            # 未参赛项目，不参与优化
            continue

# 目标：最大化总 rating
total_rating = sum(rating_map[(sid, eid)] * x[(sid, eid)]
                   for (sid, eid) in rating_map.keys())
m.Maximize(total_rating)

# 约束：每人最多参加 M 项（示例设 M=1）
M = 1
for sid in swimmers:
    m.Equation(sum(x.get((sid, eid), 0) for eid in events) <= M)

# 约束：每项最多 N 名选手（示例设 N=1）
N = 1
for eid in events:
    m.Equation(sum(x.get((sid, eid), 0) for sid in swimmers) <= N)

# 求解
m.solve(disp=False)

# 输出结果
print("✅ 最优阵容（swimmer_id → event_id）:")
for (sid, eid), var in x.items():
    if var.value[0] > 0.5:
        print(f"  Swimmer {sid} → Event {eid} (rating={rating_map[(sid,eid)]:.0f})")

# 计算平均评分
selected_ratings = [rating_map[(sid, eid)] for (sid, eid), var in x.items() if var.value[0] > 0.5]
avg_rating = sum(selected_ratings) / len(selected_ratings) if selected_ratings else 0
print(f"\n? 平均 rating = {avg_rating:.1f}")

运行此代码将输出：

✅ 最优阵容（swimmer_id → event_id）:
  Swimmer 1 → Event 2 (rating=800)
  Swimmer 2 → Event 1 (rating=890)

? 平均 rating = 845.0

完美复现了“聪明教练”的选择。

注意事项与进阶建议

数据预处理关键：确保 rating 具有跨项目可比性（如使用 Z-score 标准化、或基于世界泳联积分公式转换），否则优化结果将失真。
扩展性提示：当 |swimmers| × |events| > 10⁴ 时，纯 MILP 可能变慢；此时可结合启发式初始化（如贪心解作为 warm-start）或采用列生成（Column Generation） 或 强化学习调度器。
现实约束增强：可轻松加入：
- 体能恢复约束（如 Event2 在 Event1 后 30 分钟内禁止同一人参赛）；
- 接力项目协同约束（如 4×100 Free 需 4 名不同选手且均报过自由泳）；
- 教练偏好权重（对特定组合乘以系数）。
替代工具推荐：
- 小规模（
- 大规模/非线性：Pyomo + CBC/Gurobi；
- 无需安装求解器：ortools 自带开源求解器，部署友好。