精读笔记

Problem Setting

这篇论文实际处理的是院系级 class timetabling 的一个窄而真实的版本：所有课程必须被放入离散时间槽和物理教室，并同时满足教师、学生群组、房间类型、容量、不可用时段、午休、连续课块、并行授课等硬约束。关键矛盾是：排课系统必须尊重大量本地规则，但行政上真正关心的不是单纯可行，而是有限教室资源是否被合理使用，尤其是小班课占用大教室导致的分布式空座浪费。

真正困难点不是 NP-hard 这个常识性标签，而是约束颗粒度很杂：有些约束绑定 course-room-time，有些绑定 instructor-time，有些绑定 cohort-time，还有些绑定课程块起点和连续性。若直接按学生建模，冲突约束会随学生数和选课组合爆炸；若过度抽象，又会丢掉真实排课中最容易导致人工返工的规则。以前方法的问题在这里不是“不能排课”，而是通用 timetabling 框架经常无法低成本表达这些 institution-specific constraints，或者需要启发式调参和人工后处理。

Motivation

作者的核心观察是，实际院系排课的主要低效来自两件事：一是人工流程通常以可行为先，资源利用只是局部经验判断；二是学生冲突并不一定需要逐学生处理，因为许多学生在排课约束意义上是等价的。于是问题的缺口不是缺一个新的 metaheuristic，而是缺一个能把院系规则直接编码进数学模型、并在真实数据规模上仍可精确求解的 formulation。

另一个动机是目标函数的选择。简单最小化总空座数并不能惩罚“把大量浪费集中到少数大房间”的情况，也不能充分表达小班课不该占用大教室的偏好。作者因此选择平方容量差作为 assignment cost，本质上是在目标中加入 convex-like 的容量匹配偏置，尽管模型本身仍保持线性。

Core Idea

论文的核心思想不是发明新的优化算法，而是重写排课问题的建模重心：把真实排课规则全部压成 BLP 可行域，把资源利用偏好压成 room-course assignment 的静态代价，并通过 cohort equivalence 把学生维度压缩掉。这样一来，求解器面对的不是一个含大量个体学生冲突的原始行政问题，而是一个结构更清晰的 course-room-time assignment problem。

这个建模引入的 inductive bias 很明确：课程应该被分配到容量刚好足够、类型匹配、时间连续且不冲突的空间中。平方空座惩罚使“大教室给小课”的代价增长更快，因此它会系统性地把小班课推向小教室，把大班课留给大教室。和许多 prior work 相比，本质区别不在求解技术，而在于它把“空座分布”从事后统计指标变成了一阶优化目标，并把学生冲突从 individual representation 改成 cohort representation。

Method

方法中最关键的是 x/y 双变量设计。x_{ijk} 表示课程 i 在房间 j、时段 k 占用资源，负责表达冲突、容量、房间类型和不可用约束；y_{ijk} 表示课程块起点，负责表达课程只开始一次、连续 H_i 小时、不能跨天、不能覆盖午休以及疲劳间隔。这个拆分的价值是把本来容易变成非线性或条件逻辑的课程块结构线性化。

第二个关键机制是容量匹配目标。目标不是最小化使用房间数，也不是总空座线性和，而是对每个被选中的课程-房间组合赋予 (C_j - S_i)^2 成本。因为平方项只出现在常数系数中，BLP 仍然线性；但优化偏好变成了对容量 mismatch 的强惩罚。这解决的是资源分配质量，而不是 feasibility。

第三个机制是 cohort compression。作者把学生-课程二部图中行完全相同的学生合并为同一 cohort，再用 cohort-course 集合施加冲突约束。它解决的是维度爆炸问题，核心变化是把学生冲突从 O(|students|) 的个体层面转成 O(|distinct enrollment patterns|) 的等价类层面。这个技巧在该数据上很有效，但依赖选课模式有足够重复。

第四个机制是把本地行政规则硬编码为线性约束，包括 lecture/lab type matching、教师和 cohort unavailable slots、教室预占用、parallel sessions、resting hour 等。这些机制的贡献不在数学新颖性，而在于把真实部署中最容易导致人工修表的规则提前纳入可行域。

Key Insight / Why It Works

这篇最值得保留的 insight 是：在很多院系排课问题中，提升质量并不需要复杂搜索策略，首先需要把真实约束和正确的资源利用偏好建模进去。若可行域刻画得足够贴近行政规则，商业级 MILP/BLP solver 的 presolve、branch-and-bound 和 cutting machinery 已经足以处理中等规模实例。换言之，方法有效的主要来源是 better formulation + solver engineering，而不是新的 optimization algorithm。

平方空座目标的作用是一个明确的 inductive bias。线性空座在某些设置下会对空座分布不敏感，而平方惩罚会更强地反对极端 mismatch。这相当于把 room assignment 从“满足容量即可”变成“容量越贴近越好”。不过文中对平方目标的独立贡献没有 ablation，增益来源不清。38.75% 的空座减少可能来自整体 BLP 自动优化，也可能来自 room capacity objective，也可能只是人工课表没有显式优化空座。

cohort compression 可能是实际可解性的核心贡献。它不是理论上新颖的图等价类思想，但在排课场景中非常实用：学生冲突约束只关心同一时段是否有两门必修课冲突，而不关心学生身份本身。只要多个学生有完全相同的课程需求，保留一个 cohort 就不损失冲突信息。这是典型的 latent structure compression，而不是 scaling by hardware。

其他部分，如 type matching、unavailability、lunch break、resting constraints，更像必要的工程建模。它们提高部署可信度，但不构成方法上的核心创新。parallel-session 约束有一定现实价值，但论文没有展示它在真实案例中对目标或可行性的实际影响，可能只是为了覆盖特定业务规则。

Relation To Prior Work

这篇工作属于 operations research / educational timetabling 中的 exact integer programming 路线，而不是 metaheuristic 路线。它和 Burke、Lewis 等综述中讨论的大学排课问题共享基本 assignment formulation，也和近年的 MILP timetabling、teacher preference、room stability、hybrid teaching、多目标排课等工作在问题谱系上接近。

真正不同点在两个地方。第一，它把分布式空座最小化作为主目标，且用平方容量差塑造 room-course matching，而不是把座位利用率作为事后指标。第二，它明确使用学生选课等价类来压缩 cohort 维度，使真实数据能进入精确求解框架。

看似新的部分中，BLP formulation、容量约束、教室唯一占用、教师/学生冲突、不可用时段、连续课块都不是新思想，更多是标准 timetabling 建模的重组。实质创新较弱但实用性较强的是：把这些约束组合到一个具体院系可运行的数据管线里，并证明在这个规模上 exact solver 可以替代人工排课。

Dataset / Evaluation

evaluation 覆盖了一个 toy example 和一个 KMUTT 数学系真实排课实例。真实案例有实际行政数据、真实教室和教师约束，并在普通笔记本上用 Gurobi 求得最优，这足以支持“该院系场景可自动化、可精确求解、可减少空座”的局部 claim。

但 evaluation 不足以验证更强的泛化 claim。没有跨院系、跨学期、跨学校实例；没有和启发式、CP-SAT、标准 MILP baseline 或不同目标函数比较；也没有 ablation 来区分平方惩罚、cohort compression、Gurobi presolve、硬约束集合分别贡献了多少。与人工课表的比较有实际意义，但不完全干净，因为人工排课可能同时优化了模型未纳入的软目标，例如教师偏好、课程时间习惯、行政便利、学生日程紧凑性等。

因此，实验更像 deployment case study，而不是算法性 benchmark。它证明了这个 formulation 在一个真实部门上有用，但没有证明它是 timetabling 问题的一般最优建模方式。

Limitation

最大限制是成立前提很强：所有重要规则必须能被明确离散化、线性化，并作为硬约束或静态 assignment cost 输入。真实排课中很多偏好并非硬约束，例如教师喜欢某天、学生不希望课程过于分散、课程之间有 pedagogical ordering、某些教室虽然类型匹配但体验不同。这些若不建模，所谓 optimal 只是在简化目标下 optimal。

scalability 上限没有被充分说明。当前实例的可解性很大程度依赖 cohort 数远小于学生数、时段和课程数量适中、约束结构规则、Gurobi presolve 强。若进入全校级排课，课程更多、选课组合更稀疏、跨院系共享教室更多、软约束更多，BLP 规模可能迅速失控。文中未充分说明在更大、更异质实例上的退化行为。

目标函数也有隐含偏见。平方空座惩罚会强烈偏好容量贴合，但它不一定等价于真实资源效率。例如把课程放到稍远但容量合适的房间、或者牺牲教师/学生日程紧凑度来减少空座，是否真的更好，文中没有讨论。若其他软目标没有纳入，优化器可能只是把问题从“空座浪费”转移到“时间表体验”上。

增益归因不清。相对人工减少空座不能说明平方目标是关键，也不能说明 cohort compression 改善了最优解质量。它可能主要来自 scaling / data：将人工无法全局搜索的组合空间交给 solver 后，自然会找到更好的容量匹配。核心能力不是新的推理或规划，而是精确枚举加剪枝在中等规模实例上的胜利。

Takeaway

• 第一，真实 timetabling 的价值通常不在更花哨的 heuristic，而在把本地规则、目标和数据压成一个 solver 能吃的精确模型。
• formulation quality 比算法 novelty 更重要。
• 第二，cohort equivalence 是可迁移的 insight。
• 凡是学生身份只通过需求集合影响约束的排课、考试安排、资源预约问题，都可以先做等价类压缩，避免把个体维度直接暴露给整数规划。

一句话总结

这篇论文是一个面向真实院系排课的 BLP deployment note，真正贡献在于用 cohort 压缩和平方容量匹配把人工排课问题转成可精确求解的资源分配模型，而不是提出新的 timetabling 算法。