运筹优化常用模型、算法及案例实战——Python+Java实现

 1. 为什么要写这本书
近年来，国内从事运筹优化学术研究的科研人员和工业界的运筹优化算法工程师日益增多，运筹优化逐渐得到国内各行各业的重视，这也是为广大运筹从业者所喜闻乐见的。物流、交通、供应链、电商、零售业、制造业、航空、金融、能源、定价与收益管理等各个领域，都有大量运筹优化的应用场景，同时，也有不少复杂的实际问题亟待解决。这对于国内从事运筹学研究的学者和算法工程师而言，无疑是巨大的挑战和机遇，对于该领域的在校博士研究生、硕士研究生，甚至本科生而言，亦是如此。
“问渠那得清如许？为有源头活水来。”一个行业要想长期欣欣向荣，就需要源源不断地涌入优质的行业人才，而行业人才最重要的来源，就是在校博士研究生、硕士研究生和本科生。拥有高水平的运筹优化领域的研究生、本科生教育，是培养出优质行业人才的重要条件。打造丰富多样的优质教材是提高一个领域的教育水平的重要举措。我在硕士研究生阶段，一直留心调研国内运筹优化教材的现状，发现到目前为止，市面上面向本科生教育的优质教材比较多，这些教材在基础理论的讲解上做得非常到位。但是，国内市面上面向研究生，甚至是已经从业的运筹优化算法工程师的优质教材并不多见，至于聚焦在有针对性地、详细地介绍运筹优化常用算法及其编程实战的教材，更是屈指可数。目前国内运筹优化领域的研究生教育所采用的高级运筹学教材，也大多使用国外的课本，这些课本虽然在基本理论讲解方面详尽透彻，但往往在实战方面却少有涉及。大部分现有的教材都聚焦在讲解基本概念、基本理论、公式推导等方面，而不涉及具体代码实现层面的细节和技巧。国内的很多教材，也都聚焦在一些晦涩的理论推导及证明上，这让很多初学者望而却步。作为一名已经掌握了一些本科生阶段运筹优化知识的学生或从业者而言，要找到一本合适的进阶版中文教材，以满足科研或者工作的需要，是非常困难的。本书就是一本同时能满足本科生课外拓展、研究生科研需要和从业人员实战需要的教材。
“纸上得来终觉浅，绝知此事要躬行。”算法是一个非常讲究实战的领域，仅仅了解理论，而不能动手将其实现，很多时候并不能真正地掌握算法的精髓，达到融会贯通的境界。对于从事科研工作的硕士研究生和博士研究生，以及业界算法工程师而言，不能编程实现算法，意味着科研工作或者企业项目不能被推进。因此，我认为编写一本既能简洁清楚地讲解基本理论，又能提供非常详细的案例和配套代码的运筹优化算法教材，是非常有必要的。我在硕士研究生阶段的初期，研究课题为车辆路径规划（VRP）。为了推进这个研究，我阅读了大量的文献和教材，找到了论文的创新点，然后自以为可以较快地推进研究。但是，真正着手做研究的时候，发现还需要掌握多方面的知识和技能，包括：第一，熟练掌握至少一种编程语言，这是为了能实现涉及的算法；第二，懂得并且熟练使用整数规划的各种高级建模技巧；第三，掌握一些常用的精确算法或者启发式算法；第四，掌握至少一个优化求解器的使用方法；第五，将所选算法应用到自己课题的模型中去，并将其完整地实现。这还只是完整地复现一遍，不包括模型创新和算法创新的部分。
整个过程听起来似乎并不很困难，但是执行起来让我倍觉吃力。阅读文献、理解论文主旨和其中的算法原理，这部分比较轻松。可是到了算法实现方面，我遇到了一系列的困难，包括算法细节、数据结构、编程语言等，尤其是后两部分，让我不知所措。虽然我在本科阶段也学过一些编程，但是由于学习并不深入，缺乏针对性的练习，编程能力非常薄弱。正因为如此，我在独立实现这些算法的过程中困难重重。于是我去 github 等平台到处搜集资料，希望能得到一些非常对口的代码或文档，但是在 2016 年和 2017 年，平台上并没有非常相关的高质量参考资料，同类平台上也是类似的情况，资料零零散散，逐个筛选非常费时费力。
一个偶然的机会，我在朋友圈看到了一个微信公众号发布的技术科普文章，名为《分支定界法解带时间窗的车辆路径规划问题》，我滑到文章顶部一看，这个公众号叫“数据魔术师”。令我兴奋的是，该文章提供了完整的代码（源代码作者为华中科技大学黄楠博士）。我兴高采烈地下载了这篇文章的详细代码，如获至宝。之后我仔细研读，反复学习，最终找到了常见的精确算法实现的窍门。
随后的一段时间，我就接连开始攻关分支定界算法、分支定价算法等精确算法，并在课题组组会上展示和交流。我读硕士研究生阶段的导师，清华大学深圳国际研究生院物流与交通学部副教授戚铭尧老师也非常高兴，非常支持我钻研这些算法，在理论和实践层面都给予了我很多指导。尤其是关于算法的一些细节方面，老师跟我有多次深入的讨论，很多困惑也是在这个过程中得到解决的。另外，戚老师课题组内研究物流网络规划、车辆路径规划、智能仓储系统等方向的师兄师姐发表的论文中，也在频繁地使用分支界定算法、分支定价算法和列生成算法等精确算法。总之，经过长时间的认真钻研，我终于大致掌握了上述算法。
后来，在研究 Dantzig-Wolfe 分解和拉格朗日松弛时，我已经快要硕士毕业了。当时我照例去 github 寻找参考资料，并且发现了一段非常高质量的代码。非常幸运，我联系到了这个代码的作者，他叫伍健，是西安交通大学毕业的硕士，现在是杉树科技的算法工程师。在这个高质量代码的帮助下，我很快按照自己的理解完成了上述两个算法的实现。另外，在实现的过程中，他也解答了我在算法细节方面的诸多问题。由于他的代码框架远胜于我的代码框架，所以这部分的代码我就参照他原来代码的大框架重新写了一版，放在本书相应章节。不久前我开始撰写这两章，联系他阐明此事，他欣然同意，并且非常支持我，这让我非常感动。在这里，我也代表本书的作者们以及将来的读者们向伍健表示感谢！
在整个算法的学习过程中，我和同课题组的熊望祺（也是本书的作者之一）经常探讨，从零开始学习这些算法，然后一一实现它们，难度究竟如何？我们的观点非常一致：实属不易，参考资料很少很杂，质量不高！我们不止一次地感叹，为什么没有一本能解决我们大部分疑惑的资料呢？当我们学习理论时，可以很轻松地找到好的参考资料，但是在尝试去实现这些算法时，却难以获取详细的资料。要么就只能钻研数百页的较为复杂的用户手册，自己慢慢筛选有用信息。要么就只能找到一些零散的代码资料和文档，大部分时候这些代码甚至没有任何注释，就连代码实现的具体模型、具体算法都没有做解释说明，更不用说细节方面的解释了。通常的情况是，读者看懂了 A 模型的算法，经过筛选大量资料，却搜集到了 B 模型的代码，而 B 模型的代码对应的算法、注释很不齐全，每个函数的具体功能也没有提供有用的文档。如果读者要硬着头皮研读，可能会花费大量时间，并且很有可能做无用功。相信经常编程的同行都了解，阅读别人的代码是多么痛苦的事，更何况是没有伪代码、没有注释、没有 README 的代码。
在读博以后，我和本书的另外两名作者（臧永森和段宏达）在闲聊时，常常聊到运筹优化方向参考资料匮乏这件事。慢慢地，我萌生了把这些资料整理成书出版，供想要入门和进阶的博士生、硕士生、本科生或者业界的算法工程师学习、查阅的想法。我也将这个想法告诉了熊望祺，他非常赞成，并表示愿意一起合作将这本书整理出版，于是他将平时完成的部分精确算法的代码提供给了我，并将这些内容整合在本书相应章节中。之后，我也向臧永森和段宏达表达了合作意愿，他们也都认为这是一件有价值的事。不久后，他们也正式加入了编写团队，为本书做出了非常重要的贡献。
读博期间写书需要花费大量时间，个别时候会耽误一点科研进度，因此我非常担心导师不同意我做这件事。但是当我向导师清华-伯克利深圳学院副院长陈伟坚老师表明了我写书的计划以后，陈老师非常支持，并鼓励我多做调研，明确本书的受众，构思好书的脉络，要坚持做完整，不要半途而废。然后多次和我讨论如何设计本书的框架，如何编排各个章节，一些细节相关的内容如何取舍，以及针对不同受众如何侧重，还对本书未来的拓展方向、需要改进完善的资源提出了很多非常有帮助的建设性意见。这些意见对本书的顺利完成起到了不可或缺的作用。
目前正在攻读博士的我，虽然对运筹优化有极大的热情，但是回想起过去两三年前的“小白”阶段的学习过程，仍觉得比较痛苦。很多次，我都心力交瘁，濒临放弃的边缘。我个人觉得，像我一样有同样困惑的同行，兴许有不少吧。我不希望每个像我一样的运筹优化爱好者（初学者），都去经历那样的过程，把大量时间浪费在甄别杂乱、不系统的资料中。我认为，国内应当有一些完整的、系统的资料，帮助运筹优化爱好者们突破入门，走上进阶，把主要精力放在探索更新的理论中，或者将这些理论应用于解决新的问题上，真正创造价值。这也是我们花了大量时间和精力，将一些常用技巧、模型、算法原理、算法的伪代码以及算法的完整代码实现通过系统的整理，以通俗易懂的语言串联在一起，最后编成这本书的初衷。
“不积跬步，无以至千里；不积小流，无以成江海。”我从硕士一年级就开始慢慢探索积累，直到博士三年级，终于完成了全书的撰写。如今这本书得以面世，心中又喜又忧。喜自不必说，忧在怕自己只是一个博士在读生，见解浅薄，功夫远不到家，并且书中一定存在一些自己还没发现的错误，不够完美，影响读者阅读……总之，走过整个过程，才越来越深入理解厚积薄发的含义。回想过去几年，真是感慨万千。我曾一次次在实验室 debug到凌晨，直到逮到 bug，代码调通，紧锁的眉头顿时舒展。然后我潇洒地将笔记本合上，慢悠悠插上耳机，听着自己喜欢的歌，撒着欢儿，披着学术长廊的灯光，傍着我的影子就溜达回宿舍了。那种成就感和幸福感，着实是一种享受。虽然那段时间我经常宿舍、食堂、实验室三点一线，听起来这种生活似乎毫无亮点，枯燥乏味，但是我每天都在快速进步，我很喜欢这样的状态。这种状态很像陶渊明先生在《五柳先生传》中的描述：“好读书，不求甚解；每有会意，便欣然忘食”。不求甚解在这里不必纠结其具体观点，单就欣然忘食这种喜悦感，我认为是相通的。当自己真正有收获时，内心的快乐是油然而生的。也正由于那段时间的积累，才有了现在这本书。博观约取，厚积薄发，希望低年级的同学们坚持积累，不断提升，最终达到梦想的顶峰！
2. 本书内容安排
为了能够让读者系统地学习运筹优化算法，我们将本书分成以下 3 部分：运筹优化常用模型及建模技巧、常用优化求解器 API 详解及应用案例、运筹优化常用算法及实战。
运筹优化常用模型及建模技巧部分不需要读者有任何的编程基础，只需要掌握本科的运筹学线性规划相关理论和基本的对偶理论以及整数规划基础知识即可顺利读懂。本部分分为 4 章。第 1 章介绍了一些数学规划模型的分类和后面章节的精确算法会涉及的一些凸优化领域的概念，包括凸集、凸包等。由于本书的重点不在于此，因此本章介绍得比较简略。第 2 章介绍了一些非常常见的运筹学问题，如指派问题、旅行商问题、车辆路径规划问题和多商品网络流问题。这些问题非常经典，并且具有代表性，当下很多实际问题都可以转化为这些问题的变种和拓展。第 3 章讲解了整数规划中常用的建模技巧，包括逻辑约束的用法、非线性项的线性化方法等，这些技巧频繁地出现在业内顶级期刊发表的论文中，因此本书专门设置了一章介绍这些内容。第 4 章讲解了运筹优化中一个非常重要的理论——对偶理论。不同于其他教材，本书中这一章主要聚焦如何写出大规模线性规划的对偶问题，是作者通过自己探索总结出的方法，目前国内外的各种教材和网站，鲜有看到类似的方法介绍。
第 I 部分旨在为后续的算法部分做铺垫，之后章节中会多次用到这部分介绍的概念和模型。
常用优化求解器 API 详解及应用案例部分分为 3 章，主要是介绍常用优化求解器（CPLEX 和 Gurobi）及其应用案例。这部分将为之后的算法实战做好技术铺垫，本书第III 部分的章节，都需要用到这一部分的内容。要顺利读懂这一部分，需要读者有一定的编程基础，至少需要掌握 Java 或者 Python 中的一门语言。第 5 章详细地介绍了 CPLEX 的Java 接口的用法。这一章的主要内容是根据 CPLEX 提供的用户手册整理而来，包括基本的类、callback 以及例子库中部分例子代码的解读。该章能够帮助读者快速地掌握 CPLEX的 Java 接口的使用，读者无须去研读厚厚的英文版用户手册。第 6 章系统地介绍了 Gurobi的算法框架及其 Python 接口的用法。包括常用类、Python 调用 Gurobi 的完整建模过程、日志信息、callback 等内容。最后还附以简单的案例帮助读者理解。第 7 章提供了带时间窗的车辆路径规划（VRPTW）的代码实现。详细地给出了如何调用求解器建立 VRPTW的模型并求解。这个案例略微复杂，掌握了这个案例，其余更高难度的案例也就迎刃而解。本章的案例都是直接调用求解器得到模型的解，并没有涉及自己实现精确算法的内容。
运筹优化常用算法及实战部分是本书最为重要、干货最多的部分。该部分全面、系统地将运筹优化中常用的精确算法以通俗易懂的方式讲解给读者，尽量避免晦涩的解读。为了方便读者自己实现算法，我们为每一个算法都提供了详细完整的伪代码，这些伪代码可以帮助读者从 0 到 1 动手实现相应的算法。在第 8 章，我们简要回顾了单纯形法，并给出了伪代码和 Python 代码实现。在第 9 章，我们介绍了求解最短路问题的 Dijkstra 算法及其实现。Dijkstra 算法也是一个非常常用的基础算法。第 10～17 章，我们以理论 详细小案例 伪代码 复杂大案例 完整代码实现的方式，为读者介绍了分支界定算法、分支切割算法、列生成算法、动态规划算法、分支定价算法、Dantzig-Wolfe 分解算法、Benders分解算法、拉格朗日松弛 8 个经典且常用的精确算法。这些算法经常出现在运筹学领域各个期刊的文章中以及工业界的具体项目之中。为了便于读者理解，我们尽量避免复杂的数学推导，着重讲解基本原理和算法迭代步骤，真正意义上帮助读者从理论到实践，一步到位，无须到处寻找零散资料，做重复性的整合工作。
相信认真研读这本教材的读者，一定会大有收获。尤其是刚入门的硕士生和博士生，可以凭借这本教材，系统地了解本领域的精确算法，更好地胜任自己的科研工作。对于已经从业的运筹优化算法工程师，本书也可以作为一本非常详尽的学习工具书。
这里需要做一点特别说明，本书不同章节代码的继承性不大，大部分章节的代码都是针对该章节独立编写的。这种做法是为了方便初学者较快地理解每一章的代码，更好地消化每个单独的算法。但是这种编排也有一些弊端，即不利于拓展和改进。实际上，大部分精确算法之间都是有联系的，科研过程中也经常将它们组合使用，如果将所有章节的代码做成一个集成的算法包，既方便管理，又便于拓展。但是，集成性较好的代码，其结构一般都很复杂，初学者面对这样的代码，往往不知所措。复杂的函数调用关系，众多的类和属性，难免会让初学者望而生畏。基于此，本书各个章节的代码还是保持了较高的独立性，今后如果有机会，我会考虑提供两个版本的代码，即独立版本和集成版本，前者主要面向初学者，后者主要面向较为熟练的读者。
为了方便读者更容易地对照本领域内的英文文献，本书对涉及的专业名词（概念、问题名称和算法名称等）给出了中英文对照表。
由于作者水平和时间有限，书稿在编写的过程中，难免有疏漏和错误，一些源自网络的参考资料也由于时间久远不能找到出处，希望涉及的原作者看到以后，及时与作者联系。再版之际，我们将会做出修改。也希望广大热心读者为本书提出宝贵的改进意见。
3. 本书内容的先修课
运筹优化常用模型及建模技巧部分：先修课程为“运筹学”。另外，最好修过“凸优化”这门课（没有选修这门课也不影响阅读学习）。
常用优化求解器API详解及应用案例部分：先修课程为“Java编程基础”或者“Python编程基础”。
运筹优化常用算法及实战部分：修过以上两部分先修课程的同学，可以无障碍阅读学习。如果还修过“高级运筹学”或者“整数规划”，学习会更加轻松。如果没有修过上述课程，也不影响学习，我们的教材内容非常通俗易懂。
4. 致谢
非常感谢我读博士研究生阶段的指导老师，即清华大学清华-伯克利深圳学院陈伟坚教授。陈老师对本书整体框架、章节安排等方面提出了诸多建设性意见，也参与了本书的校对、完善等工作。而且，陈老师从读者角度出发，对全书内容的精炼等方面提出了若干宝贵修改意见，有效地提升了本书的可读性和可拓展性。另外，陈老师对本书后续的完善以及图书习题部分的补充也给出了明确方向。
感谢我读硕士研究生阶段的指导老师，即清华大学深圳国际研究生院物流与交通学部戚铭尧副教授。戚老师对本书算法理论介绍部分以及内容完整性方面提出了诸多宝贵的修改意见。
感谢清华大学深圳国际研究生院物流与交通学部张灿荣教授。张教授是我读硕士研究生阶段的高级运筹学老师，他妙趣横生的讲解激发了我对运筹优化浓厚的学习兴趣。
感谢运筹优化领域微信公众号“数据魔术师”给予我的莫大帮助。该公众号发布的优化算法介绍文章以及完整代码资料为我实现精确算法提供了非常有用的参考。特别地，在Branch and Bound 的实现过程中，我参考了该公众号分享的部分代码。由衷感谢该公众号的运营者：华中科技大学管理学院秦虎教授以及他的团队。秦虎老师的团队发布的算法科普文章以及举办的精确算法系列讲座，犹如雪中送炭，为很多运筹优化领域的初学者提供了巨大帮助。同时非常感谢华中科技大学的黄楠博士，他提供的源代码帮助笔者克服了诸多困难。
感谢 Mschyns 在 github 上开源的 Branch and Price 求解 VRPTW 的代码，以及华中科技大学邓发珩同学做的修改。该版本的 Java 代码可以为读者自行实现 Branch and Price算法提供重要参考。
感谢伍健在 DW-分解算法、拉格朗日松弛算法方面提供的资源。非常感激在算法实现过程中，伍健对我诸多疑惑的耐心解答。也非常感谢伍健对这本书出版的大力支持。
此外，我还很荣幸地邀请到了我的老师、师兄、师姐、师弟、师妹们参与了本书后期的读稿和校对工作。他（她）们是陈名华（香港城市大学教授，我的老师）、张莹、黄一潇、陈锐、王祖健、游锦涛、何彦东、王美芹、王梦彤、段淇耀、贺静、张文修、周鹏翔、王丹、夏旸、李怡、郝欣茹、朱泉、修宇璇、王涵民、张祎、梁伯田、陈琰钰、王基光、徐璐、左齐茹仪、张婷、李良涛、赖克凡、曹可欣、金广、席好宁、俞佳莉、陈梦玄。非常感谢他（她）们宝贵的意见和建议。
感谢运筹优化领域公众号“运筹 OR 帷幄”。该公众号发布的高质量的理论介绍文章、讲座预告等给予了我大量的信息，在拓宽视野、了解运筹领域交叉学科的发展现状等方面给了我莫大的帮助。
感谢本书所有参考文献的作者，是你们的研究成果让我学到了许多新的知识，获得了不少新的启发。本书部分内容参考或者翻译自这些文献，在此向这些研究者们致以崇高的敬意。
感谢清华大学出版社对本书出版给予的支持，以及参与本书编校工作的编辑们的辛勤付出。
最后，感谢我的父亲和母亲对我的鼓励和培养，以及对我完成学业的无条件支持和理解。
希望本书能得到广大读者的喜爱，为大家提供有效的帮助。

刘兴禄
2020 年 12 月于清华大学深圳国际研究生院

《运筹优化常用模型、算法及案例实战》主要讲述运筹优化领域常用的数学模型、精确算法以及相应的代码实现。首先简要介绍基本理 
论，然后用丰富的配套案例讲解多个经典的精确算法框架，最后结合常用的优化求解器（CPLEX 和 
Gurobi）说明如何用 Python 和 Java 语言实现书中提到的所有精确算法。 
全书共分 3 部分。第 I 部分（第 1~4 章）为运筹优化常用模型及建模技巧。该部分着重介绍整数规 
划的建模技巧和常见的经典模型。第 II 部分（第 5~7 章）为常用优化求解器 API 详解及应用案例。该 
部分主要介绍两款常用的商业求解器（CPLEX 和 Gurobi）的使用方法，包括 Python 和 Java 的 API 详 
解、简单案例以及复杂案例。第 III 部分（第 8~17 章）为运筹优化常用算法及实战。该部分详细介绍几 
个经典的精确算法的理论、相关案例、伪代码以及相应的代码实现。 
本书适合作为高等院校工业工程、管理科学与工程、信息管理与信息系统、数学与应用数学、物流 
工程、物流管理、控制科学与工程等开设运筹学相关课程的高年级本科生、研究生教材，同时也可供在 
物流与供应链、交通、互联网、制造业、医疗、金融、能源等领域从事有关运筹优化的开发人员以及广 
大科技工作者和研究人员参考。

第I部分 运筹优化常用模型及建模技巧
第1章 运筹优化算法相关概念 3
1.1 几类常见的数学规划模型 3
1.1.1 线性规划 3
1.1.2 混合整数规划 3
1.1.3 二次规划 4
1.1.4 二次约束规划 4
1.1.5 二次约束二次规划 4
1.1.6 二阶锥规划 5
1.2 凸集和极点 6
1.2.1 凸集 6
1.2.2 极点 7
1.3 多面体、超平面与半平面 7
1.3.1 多面体 7
1.3.2 超平面与半平面 7
1.4 凸组合和凸包 8
1.4.1 凸组合和凸包的概念 8
1.4.2 一些结论 8
第2章 运筹优化经典问题数学模型 9
2.1 指派问题 9
2.2 最短路问题 11
2.3 最大流问题 12
2.3.1 问题描述 12
2.3.2 问题建模及最优解 13
2.3.3 最大流问题的一般模型 14
2.3.4 Ford–Fulkerson 算法求解最大流问题 15
2.3.5 Java实现Ford–Fulkerson算法求解最大流问题 18
2.4 最优整数解特性和幺模矩阵 23
2.4.1 指派问题的最优解特性验证 24
2.4.2 最短路问题的整数最优解特性验证 27
2.4.3 最优整数解特性的理解 31
2.4.4 幺模矩阵和整数最优解特性 32
2.5 多商品网络流问题 34
2.6 多商品流运输问题 37
2.7 设施选址问题 38
2.8 旅行商问题 39
2.8.1 TSP建模方法1：子环路消除约束 41
2.8.2 TSP建模方法2：MTZ约束消除子环路 42
2.8.3 TSP建模方法3：1-tree建模方法 45
2.9 车辆路径规划问题 47
2.9.1 概述 47
2.9.2 VRPTW的一般模型 48
第3章 整数规划建模技巧 51
3.1 逻辑约束 51
3.1.1 两个命题 51
3.1.2 二选一约束条件 51
3.1.3 指示约束条件 53
3.2 线性化 54
3.2.1 分段线性函数线性化 54
3.2.2 含绝对值形式的线性化 58
3.2.3 含乘积形式的线性化 60
3.2.4 含分式形式的线性化 61
3.2.5 含max/min形式的线性化 62
第4章 大规模线性规划的对偶 64
4.1 对偶理论概述 64
4.2 原问题与对偶问题之间的关系 65
4.3 对偶理论相关重要定理 66
4.4 最短路问题的对偶 7