精读笔记

Problem Setting

论文真正处理的是整数规划建模中的变量选择问题，而不是 Sudoku 求解本身。Sudoku 在这里只是一个足够小、足够熟悉、但约束结构足够典型的载体：表面上最自然的是每个格子一个整数变量，但真正的约束不是求和，而是 row/column/block 内的 all-different。困难点在于 all-different 与线性整数规划之间存在表示鸿沟；如果坚持 cell-value 变量，就必须把全局互异关系拆成 pairwise disjunction，再用 big-M 和辅助 binary 变量线性化。以前的课堂材料多展示 binary formulation 可以工作，但没有把“为什么自然变量反而差”作为主线。关键矛盾是 semantic naturalness 与 formulation effectiveness 的冲突。

Motivation

已有路线不够的地方在于它们容易让学生误以为建模只是把题目规则翻译成变量和约束。作者的核心观察是：变量选择先于约束表达，并且会决定后续模型是否线性、紧凑、稳定、可扩展。Sudoku 的 cell-value formulation 正好暴露这个缺口，因为它在语义上最直接，却在 ILP 表达上最别扭。论文想强调的不是 binary assignment 多么新，而是为什么一个不那么“自然”的 lifted representation 可以让约束结构变简单。这个方向的合理性来自一个更普遍的 OR/MIP 经验：effective formulation 往往通过扩展变量空间，把难表达的逻辑关系变成简单的线性守恒或 assignment 关系。

Core Idea

核心思想是把 Sudoku 的“格子值”表示重编码为“digit 是否被放入 cell”的 incidence 表示。这个表示改变了信息组织方式：原来一个变量承载 1..9 的值，现在变成 9 个互斥的 binary choices；原来 all-different 是跨变量的全局关系，现在变成每个 digit 在每个 row/column/block 中 exactly once。换句话说，论文展示的是一种典型 extended formulation 思路：增加变量维度，以换取约束的线性、局部和重复结构。

和 prior 的本质区别不在公式本身，而在论证焦点。已有工作把 assignment formulation 当作求解 Sudoku 的自然 IP 模型；本文把它放在 natural variable formulation 的对照面前，强调“自然对象变量”与“计算友好变量”不是同一件事。它引入的 inductive bias 是 one-hot assignment bias：模型直接表达离散选择和排他性，而不是把数值变量之间的不等关系交给 big-M 逻辑来处理。这个 bias 对 Sudoku 这类 permutation/assignment 结构尤其合适。

Method

方法可以压缩为几个机制层面的选择。第一，三索引 binary assignment 变量解决的是 all-different 难以线性表达的问题；它通过把每个 cell 的取值拆成 digit-level assignment，使 row、column、block 和 cell constraints 都成为 exact-one equality。必要性在于 Sudoku 的本质不是数值大小关系，而是符号排列关系；assignment 变量把符号排列显式化。

第二，natural cell-value formulation 用来构造反例：81 个整数变量虽然少，但 row/column/block 的 sum=45 只是必要不充分，真正约束必须是 all-different。为了在纯 ILP 中保留该变量形式，需要对每对 cell 加 disequality，并用 big-M binary switch 表示两种顺序。这个机制的作用不是提供推荐模型，而是暴露自然变量带来的隐性建模债务。

第三，uniqueness certification 利用 binary solution 的 Hamming-distance 结构。对一个已知解，通过重新优化与该解的差异度，可以判断是否存在另一个 feasible completion。这里 assignment formulation 的优势是解由 81 个取值为 1 的 assignment variables 描述，排除/寻找另一个解非常直接。

第四，Killer Sudoku cage constraints 展示 assignment 变量的可组合性：cell value 可以由 digit-weighted sum 恢复，因此 cage sum 和 no-repeat 都能直接写在线性形式中。它说明好的 formulation 不只是解决当前约束，还应给变体留下扩展接口。

第五，AMPL alldiff 展示高层建模语言与底层 formulation 的区别。alldiff 让 natural model 在代码层面优雅，但这不意味着 solver 接收到同样简洁的模型；复杂度只是被建模系统隐藏或自动 reformulate。

Key Insight / Why It Works

最重要的 insight 是：在 MIP 中，变量的“自然性”应按约束可表达性来评价，而不是按它是否像原始问题对象。Sudoku 的格子值变量看似信息压缩，但它没有对 permutation structure 建模；assignment 变量看似冗余，却把符号互斥、覆盖和唯一性全部变成了线性等式。这是典型的 better inductive bias，而不是 scaling 或 engineering。

真正有效的部分是 representation shift：从 numeric cell values 转向 categorical incidence variables。它把一个全局 all-different relation 分解为多个低阶 assignment constraints，使 solver 面对的是结构化 0-1 polytope，而不是 big-M disjunction forest。big-M formulation 的问题不只是变量和约束更多，还包括 relaxation 弱、数值尺度依赖、branching 语义差；论文虽然没有深入分析这些 solver 行为，但方向判断是对的。

辅助部分包括 AMPL 代码、Killer Sudoku 和 NP-completeness discussion。它们增强教学完整性，但不是核心贡献。uniqueness certification 稍微更有实质性，因为它展示了 binary representation 的另一个好处：completed solution 可以被自然地当作 binary support set 操作。

这篇论文的贡献不是新算法，也不是性能改进，而是把一个常见 formulation lesson 用 Sudoku 讲得非常集中。若要挑剔，assignment formulation 本身是标准 one-hot encoding；所谓新意主要是 pedagogical framing，而非技术 novelty。

Relation To Prior Work

最接近的是 Chlond 的 IP classroom Sudoku、Weiss 和 Rasmussen 的 Excel-based assignment formulation，以及更一般的 MIP formulation technique 文献。和这些工作的本质差异是本文不把 Sudoku 当作“用 IP 表达 puzzle”的例子，而是把它当作“自然变量失败”的教学案例。binary assignment formulation 并不新，AMPL 也不是新工具，alldiff 更是 CP 中成熟的 global constraint；新增加的信息是把三者放在同一条 formulation spectrum 上：手写 assignment MIP、手写 big-M natural MIP、高层 alldiff natural model。

从技术谱系看，它属于 extended formulation / disjunctive linearization / algebraic modeling pedagogy 的交叉，而不是优化算法论文。看似新的部分，如 uniqueness certification，本质上是 binary feasible set 上寻找 alternative solution 的标准 Hamming-distance 思路；Killer Sudoku 扩展也是 assignment encoding 的直接线性组合。实质创新在于论证结构和教学设计：用一个 familiar puzzle 精确暴露 variable semantics 与 solver formulation 之间的错位。

Dataset / Evaluation

没有 dataset，也没有传统 evaluation。论文的验证方式是模型构造、规模计数和代码展示，而不是 benchmark。对于它的核心 claim——自然变量不一定导向有效线性模型——这种 evidence 基本足够，因为 claim 是结构性的：cell-value all-different 若显式线性化确实会引入 pairwise disjunction 和 auxiliary binaries；assignment formulation 确实把规则变成简单等式。

但如果 claim 被理解为“assignment formulation 计算上更强/更快”，文中证据不够。没有比较 root relaxation、node count、求解时间、AMPL alldiff reformulation 结果，也没有讨论 generalized Sudoku 下模型规模如何随 n 扩展。benchmark 缺失不是致命问题，因为论文定位是教学；但它限制了任何关于 computational effectiveness 的强结论。

Limitation

最大限制是它把 formulation complexity 主要用变量/约束数量和表达简洁性来说明，而没有分析 polyhedral strength。assignment model 变量更多但约束简单，并不自动意味着 LP relaxation 更强；natural big-M model 更大也不自动刻画其全部可替代线性化空间。文中未充分说明 alldiff 的其他 MIP reformulation、CP propagator、matching-based filtering 与 assignment formulation 的理论关系。

第二个限制是 generalized Sudoku 的 complexity discussion 只是桥接教学，不反哺 formulation analysis。NP-completeness 说明问题族难，但没有说明两种 formulation 在 asymptotic 上的 relaxation gap、extended formulation size 或 solver behavior。

第三，所谓“自然 formulation 不够好”依赖一个前提：目标是写显式 ILP。如果使用 CP、SMT、SAT 或支持 global constraints 的建模系统，cell-value + alldiff 可能反而是更自然且求解有效的表示。因此论文的结论应限定在 linear/integer programming formulation 教学语境中，而不是对所有离散建模范式的普遍判断。

第四，Killer Sudoku 扩展有一定选择偏差：cage sum 正好适配 assignment-derived value expression，因此强化了 assignment formulation 的优势。对其他变体，最优表示未必仍是同一个 one-hot scheme。

Takeaway

• 第一，建模时不要先问变量是否贴近对象，而要先问关键约束在该变量空间中是否变简单；这是比 Sudoku 本身更可迁移的 insight。
• 第二，one-hot / assignment lifting 的价值在于把全局互斥和覆盖结构变成线性守恒关系；这类技巧适用于 timetabling、routing with choices、matching、scheduling 和 categorical allocation 等问题。
• 第三，高层 modelling construct 不等于底层 formulation 免费。
• alldiff、indicator、logical constraints 等语法糖可以改善建模体验，但研究者仍应关心 solver 最终看到的 reformulation。

一句话总结

这篇论文不是提出新的 Sudoku 求解方法，而是用 Sudoku 精确展示了整数规划中从自然变量到有效 extended formulation 的关键转变，贡献主要是 formulation pedagogy 而非算法创新。