应用运筹学基础 ¶

课程学习内容 ¶

应用运筹学基础 (Fundamentals of Applied Operations Research)，简称 AOR ，一点都不基础。

课程主要内容为：

• 线性规划 (Linear Programming, LP)
  • 单纯形法
  • 线性规划对偶理论
  • 原始对偶方法
• 线性整数规划
  • 割平面法、分枝定界法等
  • 整数规划的动态规划框架
  • 基于 LP 松弛的近似
  • 原始对偶近似
• 算法规范理论
  • 贪心算法
  • 独立系统
  • 拟阵
  • 次模优化
• 在线算法
• 经典运筹难问题
  • 装箱 (bin packing) 问题
  • Steiner 树
  • 旅行商 (TSP)
• 博弈论

大致可以认为前半部分讲线性规划和相关近似算法，后半部分是规范理论、组合优化和各种运筹难问题的算法。

先修要求 ¶

• 线性代数
• 高级数据结构与算法分析

前半部分线性规划内容对线性代数有很高的要求，后半部分运筹算法部分对 ads 的算法基础有很高的要求。AOR 堪称 ads plus plus plus，线性代数和 ads 学习有较大困难同学慎选。

上课要求 ¶

20、21 级的上课时间均为 1-5 节，1-2 节为 pre 时间（上半学期无 pre 则 1-2 节休息），3-5 节为讲课时间。

张国川对课堂有很高的要求，具体为（以下摘录 PPT 原话）

• 100% attendance (except for emergency)
• 100% attention
• Being active

21 级张老师对 attendance 要求非常严，每节课几乎都有点名（包括第一节课），对于不到课的学生，张老师会劝他们直接退课。另外 20、21 级张国川的智云没有声音，所以上课不听可能对课后理解带来困难。课堂禁止进食、睡觉，如果你这么做他会停止讲课并发声制止你。张国川不喜欢课堂上手机和电脑的使用 , 可能会制止你。

课程教材 ¶

没有教材，只有张国川专属 PPT。关于参考书， PPT 上有一页如是说道：

• Any textbook on Operations Research or Optimization
• Any book on Combinatorial Optimization
• Any book on Algorithms
• Any book on Game Theory

并且针对组合优化、算法、博弈论三个方面给出了三本参考书 , 但非必需看：

• Recommended Combinatorial Optimization - Algorithms and Complexity, Papademitriou and Steiglitz
• Recommended Algorithm Design, Tardos and Kleinberg
• Recommended Algorithmic Game Theory, Nisan, Roughgarden, Tardos, and Vazirani

值得一提的是，老师认为使用 PPT 是一种“恶堕”，因此 21 级后基本上都是采用手写板书这种最原始但也是最纯粹的方法，不过这也一定程度上影响了讲课的进度。

分数构成 ¶

21 级上课时老师透露了分数构成，但是不保证以后会不会改变。具体分数构成如下：

• 课后作业 20%
  • 基本每次课后都有，每次作业难的可能要做一两天。
  • 可能会有 bonus，计入平时成绩。
• 论文报告 20%
  • 3 人一组，从 30+ 篇论文中选择 1 篇，按照助教安排的时间表进行 pre。20 级论文大概分为 steiner 树和次模优化两个主题；21 级的论文的主题有 AI4OR、Network Interdiction、Santa Claus、Fair Division。有的论文非常有难度，甚至会有当年 STOC/FOCS（理论计算机顶会）的 best paper。
  • 报告分为初稿和终稿，初稿截止日期较早，老师和助教会对初稿给与修改意见，最后修改后提交终稿。
• 课堂表现 10%
  • 包括点名、老师的印象。
• 期末测试 50%
  • 张国川的期望是小班教学并进行面试，但是 20 级时 50+ 的学生太多了无法面试，委婉地使用了“练习”作为期末考试的代称。尽管张国川称呼期末测试为“练习”，但是下手并不会手软，难度相当高，没有机械使用计算方法的题，几乎全部是证明题。另外完成度非常重要，一定的完成度下，一道小题的差距可能是两档甚至三档的分数差距。
  • 可以带打印的笔记或者其他资料，但是几乎没有用。
• 论文展示
  • 21 级起展示不再作为必选项，而是可选的 bonus（加分计入期末部分）。
  • pre 之前要求发布自制海报，pre 限时 45 分钟。pre 时可能会有任何人旁听，张国川和助教是必然出场的，毛宇尘是常驻嘉宾，另外他们实验室的人可能也会出现并将此当作一场组会。需要有充分的心理准备，张国川随时可能对你的 pre 发表质疑，可能令你心态爆炸并且超时。不过如果是因为他的质疑导致你超时，他会允许你超时讲完你准备的内容。
• 课堂练习
  • 21 级有期中考试和一次课内练习，计入平时分，具体属于哪个部分不详。

虽然上述描述给人以求是的数学地狱的感觉，但是这确实是数学地狱。课程难度很高，但是真正的强者可以获得好的回报，有人获得了满绩。张国川课程中经常说“回报不会让你失望”，但笔者的体验是比较求是，结课出分时谢谢老师的人并不多。尽管如此，这是一门富有魅力的课程，包括笔者在内有一部分“谢谢老师”的人并没有取得满意的成绩（直接写在了文案中），但还是心甘情愿地谢谢老师，因为这门课教授的东西个人认为非常实用、非常干货，张国川也是用心在教学，助教也用心在帮助同学。如果绩点对你来说没有那么重要，如果数学对你来说没有那么讨厌，那么这门课值得一选。

任课教师 ¶

只由张国川老师一人教授。张国川老师是非常有资历和实力的老师，他的一些研究堪称“里程碑”的结果（例如改进近似比），比如你可以在维基百科的 bin packing 词条中看到对他的文章的引用。如果你认为是二作分量不够，那或许一作是叶德仕——张国川的学生。看到这个页面的同学大概已经学过 ads，自然应该明白“ds, ads, yds”的分量，而张国川就是叶德仕魔王的老师。

张国川老师幽默风趣，上课时经常会讲一些无伤大雅的小段子，时常有一些深刻的社会人生寓意，但是总能以深厚的阅历、语言风格和轻描淡写地回归正题让段子成为了纯粹的问题导引，笔者深以为是能把段子讲得最风雅的老师。张国川老师不介意你随时打断他的讲课进行提问，反馈对他来说比较重要，因而他很不喜欢进行网课。张国川老师是非常有风骨的老师，认为学生应当心怀国之大者，在国家社会危难之时应当挺身而出，比如他认为疫情放开之时遣散学生是可耻懦弱的逃兵行为。

个人认为张国川老师的讲课虽然能感受到他已经尽量想让我们能听明白了，但是有的他觉得很清楚很自然的地方笔者感觉并不那么自然，往往私下要推很长一段时间才能恍然大悟（但是有人能够当场听明白）。因此能够跟上张国川老师的课堂还是存在难度的。另外从课程大纲也可以看出越到后期，课程内容愈发前沿与实用，难度也逐渐飙升，课堂真的需要全神贯注。

参考资料 ¶

!!!NOTE: 任何参考资料仅可用于帮助理解课堂内容 , 不能代替课上听讲。也不能用作开卷考试资料 ( 因为考试不会出能让你找到的题目 )。

运筹学范围极广 , 文献浩如烟海 ; 这里仅再介绍与课程相关、最为经典、对大家最有帮助的两本 : + Introduction to Linear Optimization. Dimitris BZertsimas, 论线性规划无出其右 , 无论谁读之都会认同 : 这是本条理清晰、丰富细致、值得反复阅读的优秀教材。 + The Design of Approximation Algorithms. D. P. Williamson \& D. B. Shmoys, 亦十分经典 , 张老师授课内容应该有所参考 , 例如 Karmarkar-Karp 算法、Steiner 树、无容量限制设施选址问题等部分。

20 级的金鱼马同学为此课程整理了笔记 , 并结合康奈尔大学 ORIE6300 课程等加入了大量的私货 :-) 见 https://www.zhihu.com/column/c_1676006565717573634 中 " 数学规划 " 系列文章 , 若你发现了其中舛误纰谬请联系他进行改正。

斯坦福 CS261 Optimization and Algorithmic Paradigms 亦是有帮助的课程。

学习建议 ¶

认真听课，认真做作业，认真理解 PPT。用爱去对待这一门课。

从前面的描述可以看出这门课的很多特性了。笔者个人的建议是以学到东西为目的来选这门课，而不是以绩点为目的来选。当然我明白大三绩点对诸位很重要，如果如此，那么建议大四再选这门课，因为这门课是有可能付出和绩点收获不成正比的。但是不妨把目光看得远一些吧，这门课的绩点可能让你失望，但是你从这门课上学到的——如果你认真投入了的话——绝不会让你失望。

当然，如果你对自己的数学兴趣、实力以及临场考试发挥比较有自信，那么也不必顾虑，相信你也能收获满意的成绩。