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

《运筹优化常用模型、算法及案例实战》主要讲述运筹优化领域常用的数学模型、精确算法以及相应的代码实现。

《运筹优化常用模型、算法及案例实战》主要讲述运筹优化领域常用的数学模型、精确算法以及相应的代码实现。首先简要介绍基本理 
论，然后用丰富的配套案例讲解多个经典的精确算法框架，后结合常用的优化求解器（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  短路问题的对偶  73
4.4.1  借助Excel和具体小算例写出大规模SPP的对偶  74
4.4.2  SPP中存在负环的特例  76
4.5  多商品网络流问题的对偶  81
4.5.1  借助Excel和具体小算例写出大规模MCNF的对偶  81
4.5.2  将Excel中的对偶问题表转化成公式形式  83
4.5.3  Python调用Gurobi求解MCNF  83
第II部分  常用优化求解器API详解及应用案例
第5章  CPLEX的Java API详解及简单案例  93
5.1  基于Eclipse的CPLEX Java API的安装与配置：适用于macOS  93
5.2  基于Eclipse的CPLEX Java API的安装与配置：适用于Windows  97
5.2.1  基本环境配置  97
5.2.2  环境设置中java.library.path的问题  98
5.2.3  Javadoc的设置  100
5.3  CPLEX建模  102
5.3.1  类与接口  102
5.3.2  变量   102
5.3.3  表达式   102
5.3.4  范围约束   104
5.3.5  目标函数   104
5.3.6  建模方式  105
5.3.7  模型求解  108
5.3.8  获取解的信息  108
5.3.9  模型导出与模型导入  109
5.3.10  参数  109
5.3.11  其他  114
5.4  传统回调  114
5.4.1  参考回调  115
5.4.2  查询或诊断回调  116
5.4.3  控制回调  117
5.4.4  回调的终止  118
5.4.5  传统回调示例  119
5.5  通用回调  121
5.5.1  简介  121
5.5.2  功能  121
5.5.3  通用回调的上下文  121
5.5.4  通用回调示例  123
5.6  Java调用CPLEX求解整数规划的小例子  124
5.6.1  书架生产问题  124
5.6.2  包装盒选择问题  128
第6章  Gurobi的Python API详解及简单案例  132
6.1  Python调用Gurobi环境配置  132
6.1.1  完整步骤  132
6.1.2  相关问题  132
6.2  Gurobi算法框架介绍  138
6.2.1  Gurobi MIP Algorithms  138
6.2.2  Presolving  140
6.2.3  Node Selection  141
6.2.4  Cutting Planes  142
6.2.5  Heuristics  143
6.2.6  设置启发式的参数  144
6.2.7  Branching  144
6.3  Gurobi能够求解的模型类别  145
6.3.1  线性规划  145
6.3.2  混合整数规划  147
6.3.3  二次规划  148
6.3.4  二次约束二次规划  150
6.3.5  二阶锥规划  152
6.4  Python 调用Gurobi总体流程  154
6.5  Gurobi求解MIP输出的日志信息解释  156
6.5.1  MIP日志示例  156
6.5.2  预求解部分  157
6.5.3  求解进程部分  158
6.5.4  汇总部分  160
6.6  Python接口概述  161
6.6.1  模型概述  161
6.6.2  求解模型  162
6.6.3  多个解、目标函数和场景  162
6.6.4  不可行的模型  162
6.6.5  查询和修改模型属性  163
6.6.6  其他修改模型信息的方法  163
6.6.7  惰性更新  164
6.6.8  参数管理  164
6.6.9  管理求解进程：日志和回调  165
6.6.10  修改求解器的行为：回调  165
6.7  Python调用Gurobi常用类和函数  165
6.7.1  全局函数  165
6.7.2  Model类  166
6.7.3  Var类和MVar类  169
6.7.4  Column类  170
6.7.5  目标函数  170
6.7.6  表达式  171
6.7.7  约束类  172
6.7.8  求解  175
6.7.9  解的输出  176
6.8  Python接口中的GRB类  176
6.8.1  GRB类中的常量  176
6.8.2  GRB类中的属性：GRB.Attr 180
6.8.3  GRB类中的参数：GRB.Param 185
6.9  Gurobi的回调函数  190
6.9.1  什么是Gurobi的回调函数  190
6.9.2  Gurobi回调函数的用法  192
6.10  Python 调用Gurobi的参数调优  193
6.11  Python调用Gurobi求解整数规划的简单例子  194
第7章  调用CPLEX和Gurobi求解MIP的复杂案例：VRPTW和TSP  197
7.1  调用CPLEX和Gurobi求解VRPTW  197
7.1.1  VRPTW的一般模型  197
7.1.2  Java调用CPLEX求解VRPTW  198
7.1.3  Java调用Gurobi求解VRPTW  213
7.1.4  Python调用Gurobi求解VRPTW  221
7.2  Python调用Gurobi求解TSP  232
7.2.1  TSP的MTZ建模及调用Gurobi求解  235
7.2.2  TSP：Python调用Gurobi实现callback添加消除子环路约束  237
第III部分  运筹优化常用算法及实战
第8章  单纯形法  249
8.1  线性规划问题的标准形式  249
8.2  单纯形法流程图及详细案例  251
8.3  大$M$法和两阶段法  257
8.4  单纯形法伪代码  259
8.5  Python实现单纯形法  260
第9章  Dijkstra算法  265
9.1  Dijkstra算法求解短路问题详解  265
9.2  Dijkstra算法步骤及伪代码  269
9.3  Python实现Dijkstra算法  271
9.3.1  网络数据准备  271
9.3.2  Dijkstra算法实现  272
9.3.3  算例测试  273
9.4  拓展  274
第10章  分支定界算法  275
10.1  整数规划和混合整数规划  275
10.2  分支定界算法求解混合整数规划  276
10.3  分支定界算法的一般步骤和伪代码  286
10.4  分支定界算法执行过程的直观展示  290
10.5  分支定界算法的分支策略  291
10.6  分支定界算法的搜索策略  292
10.7  分支定界算法的剪枝策略  292
10.8  Python调用Gurobi实现分支定界算法的简单案例  293
10.9  Python调用Gurobi实现分支定界算法求解TSP  300
10.10  Python调用Gurobi实现分支定界算法求解VRPTW  301
第11章  分支切割算法  303
11.1  什么是分支切割算法  303
11.2  有效不等式  306
11.3  割平面算法  308
11.3.1  Gomory’s分数割平面算法  309
11.3.2  其他割平面算法  313
11.4  分支切割算法: 分支定界 割平面  314
11.4.1  分支切割算法伪代码  314
11.4.2  分支切割算法: 一个详细的例子  317
11.5  Java调用CPLEX实现分支切割算法求解VRPTW  319
11.5.1  分支定界  319
11.5.2  割平面  320
11.6  Python调用Gurobi实现分支切割算法求解VRPTW完整代码  321
11.7  Java 调用 CPLEX 实现分支切割算法求解CVRP: 回调函数添加割平面  322
11.7.1  CVRP的基本模型  322
11.7.2  割平面  323
第12章  拉格朗日松弛  326
12.1  性和松弛  326
12.1.1  原始边界  327
12.1.2  对偶边界  328
12.2  对偶  328
12.3  拉格朗日松弛  329
12.3.1  拉格朗日松弛介绍  329
12.3.2  拉格朗日对偶问题  330
12.3.3  拉格朗日松弛应用案例：无容量限制的设施选址问题  331
12.4  拉格朗日对偶的加强  333
12.5  求解拉格朗日对偶  335
12.5.1  次梯度算法求解拉格朗日对偶  335
12.5.2  应用案例：拉格朗日松弛求解TSP  338
12.6  如何选择拉格朗日松弛  340
12.7  Python调用Gurobi实现拉格朗日松弛求解选址–运输问题  342
12.7.1  拉格朗日松弛应用案例：选址–运输问题  342
12.7.2  Python代码实现  345
第13章  列生成算法  347
13.1  为什么用列生成算法  347
13.2  下料问题  349
13.2.1  引例  349
13.2.2  列生成求解下料问题的一般模型及其伪代码  352
13.2.3  列生成性的几个小问题  355
13.3  列生成求解下料问题的实现  356
13.3.1  Python调用Gurobi实现列生成求解下料问题示例算例：版本1  357
13.3.2  Python调用Gurobi实现列生成求解下料问题示例算例：版本2
（以人工变量为初始列的方式）  360
13.3.3  Python调用Gurobi实现列生成求解下料问题 : 版本3  362
13.4  列生成求解TSP  365
13.4.1  TSP的1-tree建模及列生成求解  365
13.4.2  主问题  366
13.4.3  子问题  367
13.5  列生成求解VRPTW  369
13.5.1  主问题  370
13.5.2  子问题  372
13.5.3  详细案例演示  373
第14章  动态规划  393
14.1  动态规划  393
14.1.1  动态规划求解短路问题  394
14.1.2  问题建模和求解  394
14.1.3  一个较大规模的例子  396
14.2  动态规划的实现  397
14.2.1  伪代码  397
14.2.2  Java代码  398
14.3  动态规划求解TSP  403
14.3.1  一个简单的TSP算例  403
14.3.2  伪代码  408
14.3.3  Python实现：示例算例  409
14.3.4  Python实现：中大规模算例  412
14.4  标签算法求解带资源约束的短路问题  419
14.4.1  带资源约束的短路问题  419
14.4.2  标签算法  424
14.4.3  标签算法的伪代码   425
14.4.4  标签设定算法和标签校正算法  426
14.4.5  优超准则和优超算法  426
14.4.6  Python实现标签算法求解SPPRC  427
14.5  Python实现标签算法结合列生成求解VRPTW  435
14.5.1  初始化RMP  435
14.5.2  标签算法求解子问题  437
第15章  分支定价算法  438
15.1  分支定价算法基本原理概述  438
15.2  分支定价算法求解VRPTW  440
15.2.1  VRPTW的通用列生成建模方法  440
15.2.2  分支定价算法完整流程及伪代码  442
15.2.3  分支策略  445
15.2.4  界限更新  449
第16章  Dantzig-Wolfe分解算法  450
16.1  引例  450
16.2  块角模型与Dantzig-Wolfe分解  454
16.2.1  块角模型  454
16.2.2  Minkowski表示定理  455
16.2.3  模型分解  455
16.2.4  两阶段法  458
16.3  详细案例  459
16.4  Dantzig-Wolfe分解求解大规模混合整数规划  464
16.4.1  两阶段法实现Dantzig-Wolfe分解算法介绍  465
16.4.2  第1阶段  465
16.4.3  第2阶段  471
16.5  Python调用Gurobi实现Dantzig-Wolfe分解求解多商品流运输问题  482
16.5.1  多商品网络流模型的区块结构  482
16.5.2  多商品流运输问题 : Dantzig-Wolfe分解求解  483
16.5.3  Python调用Gurobi实现Dantzig-Wolfe分解求解多商品流运输问题  487
16.5.4  完整代码  487
16.5.5  算例格式说明  497
16.5.6  算例运行结果  498
16.6  Dantzig-Wolfe分解求解VRPTW  500
第17章  Benders分解算法  504
17.1  分解方法  504
17.1.1  Benders分解的原理  504
17.1.2  Benders分解的全过程  509
17.1.3  算法框架图  510
17.1.4  算法伪代码  511
17.2  详细案例  512
17.2.1  问题描述和模型转换  512
17.2.2  第1次迭代  513
17.2.3  第2次迭代  515
17.2.4  第3次迭代  516
17.2.5  第4次迭代  517
17.3  Benders分解应用案例  518
17.3.1  固定费用运输问题  518
17.3.2  设施选址问题  520
参考文献  523

    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 月于清华大学深圳国际研究生院