E11
高中排课问题的混合整数规划求解：以 XHSTT 国际基准最优性差距与本校真实约束为双重判据
1 · 研究问题
用免费开源求解器构建的混合整数规划（Mixed-Integer Programming, MIP）排课模型，在 XHSTT 国际标准测试集上能把最优性差距（optimality gap）压到多小？把同一模型迁移到本校真实排课约束后，相对现行人工课表能在硬约束零违反的前提下把软约束罚分降低多少？
2 · 研究背景与空白
排课（timetabling）是运筹学的经典 NP-难问题。XHSTT 是国际排课竞赛（ITC-2011）确立的统一 XML 格式，收录 11 国 38 个真实高中算例，每个算例带公开的已知最优解或最好解与下界，是极少数"中学生就能拿到、且答案可核对"的组合优化基准。
已有工作：Kristiansen、Sørensen 与 Stidsen（Journal of Scheduling, 2015）给出首个覆盖任意 XHSTT 算例的两阶段 MIP 精确方法，用商业求解器证明了 4 个已知解的最优性并刷新 9 个最好解；ITC-2011 优胜方法以元启发式为主，此后 MaxSAT 与约束规划也被证明有效。这些工作都用商业求解器或专用代码。
空白在时间与工具维度：开源求解器（HiGHS、CBC、OR-Tools CP-SAT）近三年性能大幅提升，但"纯开源工具链 + 个人笔记本在 XHSTT 上能达到什么 gap"没有系统的公开报告；且把基准模型落到一所中国高中的真实约束（走班、合班、教师跨年级）并与人工课表定量对照的公开案例几乎没有。技术门槛清晰、答案可核对、结论正负都成立，适合一年期课题。
3 · 可检验假设
- H1：在 ≥10 个 XHSTT 中小规模算例上，笔记本 + 开源求解器在单例 ≤2 小时限时内可将平均最优性差距压到 ≤15%，其中至少 3 例达到已知最优。
- H2：迁移到本校约束后，模型解在硬约束零违反前提下，软约束罚分比现行人工课表低 ≥20%；若人工课表已近最优（差距 <5%），该"人工已近优"结论同样成立并可量化。
4 · 量化验收标准
- 方法学校验（硬门槛）：用自建管线重跑 XHSTT 至少 3 个带已证最优解的小算例（如 Kristiansen et al. 2015 表中已证最优的实例），复现其最优目标值，偏差 = 0（整数目标值须完全一致）；另在一个可手工枚举的 4 班×5 课玩具算例上与穷举解对照。此步不过关，后续全部结论无效。
- 报告口径预先写死：每个算例报
(可行解罚分, 已知下界, gap%)三元组；gap 相对官方公布下界计算，不得只报罚分。 - 求解器对照用双成本口径：等墙钟时间（2 小时）与等迭代预算两种都报；至少对照 HiGHS 与 CP-SAT 两个求解器。
- 本校算例须给出完整约束清单（硬/软分列、权重表预先写死并说明依据），人工课表罚分用同一评分脚本计算。
- 随机重启类算法报 ≥10 种子的均值 ± 标准差与 95% 置信区间。
- 全部模型代码、XHSTT 解析器与评分脚本开源，第三方可一键重跑。
5 · 数据与工具
| 用途 | 来源 / 工具 |
|---|---|
| 国际基准算例 | XHSTT archive（GitHub/官方站点公开 XML，38 个真实算例，含最好解与下界；仅用于校验与对比，不计入本项目数据贡献） |
| 官方评分核对 | HSEval 在线评估器（对 XHSTT 解评分；可用性需核实，不可用则按官方规范自写评分器并以公开解校验） |
| 求解器 | HiGHS（MIT 许可）、Google OR-Tools CP-SAT、CBC；全部纯 CPU、pip 安装 |
| 建模 | Python + PuLP / OR-Tools 原生 API |
| 本校数据 | 教务处现行课表与约束（班级、教师、场地；须匿名化教师姓名，经学校同意） |
规模上限：中等 XHSTT 算例约 10^5 二元变量，笔记本 16GB 内存内单次求解 ≤2 小时；超大算例（如巴西全国实例）标注超出范围。降规模版本：只做单年级（≈10^4 变量，分钟级）。
6 · 方法路径
- 装环境，写 XHSTT XML 解析与评分脚本，用官方公开解通过校验（第 1 条验收）。
- 实现基础 MIP 模型（分配变量 + 冲突约束 + 软约束罚分线性化），在玩具算例上与穷举对照。
- 在 ≥10 个算例上跑双求解器、双成本口径对照，记录 gap 曲线。
- 核实 HSEval 可用性与本校约束的可形式化边界（哪些"潜规则"无法写成约束须明示舍弃）。
- 采集本校约束建模求解，与人工课表同口径评分对照。
- 做求解时间-规模敏感性扫描（算例规模按变量数分档），给出"笔记本可解规模"经验边界。
- 独立交叉校验：对最好的 2 个解用另一求解器验证可行性与目标值。
7 · 新颖性边界
本课题不声称提出新算法，不声称刷新 XHSTT 任何最好解（若碰巧刷新是意外收获须另行核实）。已有工作：Kristiansen et al.（2015）已给出通用 MIP 精确方法与商业求解器结果；ITC-2011 各决赛方法已发表。本项目贡献是（i）纯开源工具链 + 消费级 CPU 在 XHSTT 上的系统 gap 报告——这是可复现性维度的贡献；（ii）一个中国高中真实算例的完整形式化与定量对照——样本维度的独立检验。丘奖历届获奖中运筹类有 2020 优胜"武汉疫情资源最优配置的非线性规划"与 2023 优胜"O2O 零售宅配成本最小化"，均为物流/应急场景，无排课与基准对照工作，差异清晰。"人工课表已近最优"与"可显著改进"两种结果都是有效结论，但须给出 gap 误差棒证明有能力分辨。
8 · 决策门槛（go / no-go）
- 第 3 周末：XHSTT 解析器 + 评分脚本对公开解校验通过。未通过→继续调试至第 5 周，仍未通过则降级 A：放弃 XHSTT 通用格式，改用文献中定义清晰的单一算例格式（如 ITC-2007 大学排课三赛道之一，格式简单一个数量级），保留"开源求解器 gap 报告 + 本校算例"主结论框架。
- 第 10 周末：至少 5 个算例拿到 gap ≤30% 的可行解。达不到→降级 B：缩小到小规模算例子集 + 单年级本校算例，主结论从"gap 报告"收窄为"笔记本可解规模边界研究"，框架不变。
- 第 20 周末：本校约束数据到手（须第 4 周先向教务处口头确认可行性，不要边做边发现）。拿不到→用 XHSTT 中最接近中国走班制的算例替代，本校部分降为附录讨论。
- 已知困难：软约束权重的设定有主观性——把"权重敏感性扫描（拉丁超立方 ≥50 组权重）下结论是否翻转"写成研究内容而非障碍。
- 预算裁剪顺序：先砍求解器对照（保 HiGHS 单求解器），再砍算例数量（保 5 个），最后砍本校算例；主结论（开源工具链 gap 定量报告）在全部裁剪下仍成立。