高季尧：定制化优化算法的应用与威力

随着大数据与人工智能领域技术的发展和应用的普及，算法越发繁多复杂，需要处理的数据量也越发庞大，高性能计算能力就显得尤为重要。

本篇选自高季尧先生近期于清华大数据“技术·前沿”系列讲座上所做的题为《定制化优化算法的应用与威力》的主题演讲。

本篇主要通过三个方面进行分享:

1. 何为运筹优化

2. 为什么需要定制化算法

3. 定制化算法案例分享

作者介绍：

高季尧，本科毕业于清华大学化学工程系，博士就读于美国康奈尔大学，并从事能源系统供应链的数学建模与运筹优化研究。博士期间以第一作者的身份在行业顶级期刊发表数十篇论文，并多次在国际会议上做学术报告。Google Scholar引用次数达300多次，并担任多个国际期刊的审稿人。曾参与中国石化公司的多项生产优化项目，加入杉数后为多家标杆企业提供技术服务。

一、何为运筹优化

数学家欧拉曾提出：从古至今，“优化”一直是生产生活中的重要的部分。在二战期间，现代运筹学曾在战场上发挥巨大作用；直至二战结束后，世界经济开始复苏，运筹学也被广泛的运用到金融、生产等领域，其分支也得到相应发展。到20世纪90年代，计算机科学高速发展，人们要解决的问题规模不断增大，运筹学的应用范围也取得革命性的突破。21世纪，大数据时代来临，给运筹学带来更大的舞台，如何将大数据转化为现代商业生产环境下的最优决策，成为运筹学的重点课题。

优化的定义：寻找在满足约束的条件下能够最大化或者最小化某一目标的最优决策。

在优化过程中，建模和求解是两个关键步骤。建模，将想要优化解决的问题，通过准确有效的数学模型或数学形式来表达出来。第二个是有一个很好的数学模型之后，怎样通过高效的方法，将这个模型进行高效地求解。优化问题的数学形式往往是有这样一个形式：一个优化目标，可以是最大化也可以是最小化，同时有一个决策变量用x表示，为了优化x可以遵循一定的约束条件，可以是不等式，也可以是等式。

举个现实生活中的有趣案例，如果小明同学想吃火锅，那就会出现两种情况：

以最大化的饱腹感为目标，而条件是花费要小于预算以及对食材的选择和冲突。

以最小化花费为目标，条件是饱腹感要超过底线以及对地点和食材的选择。

如何建模？以不同食材的选择为条件，引入Index函数：Index

i表示食物的集合，yi表示关于食物选择的决策;1表示选择食材，0表示不选食材。

这样就有了公式：

食材： Index i ∈ I 决策： yi ∈ binary variable

还有一些其他方面的输入：预算上限、吃饱底线、食材价格及食材带来的饱腹感。第一个Case目标函数为si乘以yi的加和，表示选中的所有食物带来的饱腹感的加和能够最大化。约束条件：首先花费要小于等于预算，其次必点的菜则i固定的等于1，当菜系发生冲突，点了某一种菜，另一种菜一定不点，这就用两个点跟i相对应。另外一个集合当选了i的时候，不选的一个集合，让这两个y相加等于1，就意味着最多只有一个1，最后要定义y是原因变量，只能取0或者1。

那么第二个Case想要省钱应该如何建模呢？其他条件不变，只是把约束条件和目标函数调换一下，即现在的目标函数是最小化花费，约束条件是选取所有食材饱腹感大于底线。

优化问题可以按照变量类型和约束条件类型被分成四种类型。LP所有的变量都是连续变量，约束都是线性约束。在它的基础上，如果能够既涉及到了离散变量，同时也有连续变量就是MIP；基于LP，如果说有非线性的约束，就是NLP；MINLP是最复杂的一种类型，包含了另外三种情况的总和。

在高性能算法中，大致分为两类：严格优化算法和Metaheuristic算法。严格优化算法更好进行说明，在数学上更容易证明，所以在学术界更受欢迎；而Metaheuristic算法在应用上更有优势。求解器相当于包装很多算法的“盒子”，像MILP这样的混合整数线性优化问题，只要满足通用形式，按照标准输入“盒子”就可以快速求解。在上述的求解器中，GUROBI和CPLEX是最有名的求解器。这两个求解器都跟IBM有关，IBM旗下CPLEX的创始人之一后来出走，和另外几个人一起创建了GUROBI。目前，这两家占据了通用商业求解器的绝大部分市场份额。杉数也研发了自己的一个求解器，是中国首个由华人开发的数学规划求解器及机器学习算法套件，打破了西方在这方面的技术垄断，具有很重要的历史意义。

二、为何要对算法定制化

算法的必要性可以从其问题本身和算法两个方面进行分析。算法定制化的目的，是给优化问题选择合适的算法，而选出合适的算法主要从三个维度进行衡量：1.稳定性，即在不同的参数和场景下都能给出很好的解。优化效果能够保证，不能因改变参数而使效果降低很多；同时求解时间要相对稳定。2.保证求解达到最理想化，或距离最优解偏差越小越好。但有时要将求解时间控制在一定范围内，会牺牲求解的最优性。3.时效性，在客户需求的范围以内能够求出最优解。

案例分享：

MILFP,是一种特殊的混合整数非线性的问题。其主要目标函数是两个线性方程的比值，其他所有的约束条件都是线性的。假设分母为正，则该线性方程用大于等于符号，这个符号是相对小的数比如0.01，但不能太小，这是一个混合整数问题。该问题有非线性的目标函数，因此是一类特殊的MILFP的问题。该目标函数是一个分式形式，其特性是具有组合性质和伪凸性。其应用在工程、经济、环境科学等环境中，例如投资回报率及购买物品时所提到的性价比。

Pseudo-convexity(伪凸性），如图所示函数，只要梯度是正的，在这个方向上就一直增长。基于Cutting plane在图中所标示的黑点会加一个Cut，这就切掉了一部分可行域，这样可能无法找到全局最优解，只能找到替代的局部最优解。它是特殊的MINLP的问题，部分算法能够求解全局最优的点，也有一些算法只能保证局部最优，当然还可以用通用的MINLP solvers求解，当然最理想的情况还是采用定制化的算法。

其中提到MILFP是一类特殊的MINLP的问题，涉及到刚才提到的数学特性（组合性质和伪凸性）。

通用的求解器是基于图示文献中提到的算法，有分解算法等等。

通用性的求解是针对所有类型非线性问题，往往针对某种特定问题的时候，求解效率不会很高。定制化的算法，前两个算法列出了相应的文献。往往在解特定问题的时候，会有特别好的表现。

整个算法框架的整理：

第一步就是初始化。开始设置一些参数和建立模型。之后就是对问题的松弛，松驰之后从备选节点中选取一个，然后对子问题做对应的变形。这样每个子问题获得的是LP问题，接下来就是分支定界法中最经典的求解步骤。

首先理解子问题，第二步判断所获得的解是不是最优解，如果不是就把它丢掉，如果是最优的，就要检查是不是w等于0或者u，如果不是的话，就向分支定界法一样，在节点中加入两个新节点，一个是要固定出w等于0，一个w等于u。如果说，刚好解出来的w都是0或者u，就意味着符合了之前的约束，接下来要检查目标函数是不是比之前的好。如果没有的话，这个节点就不要了，如果好的话，就更新下界，同时把节点去掉，同时把之前求解中节点集合中所有的上界比下界还低的界点去掉，这样的迭代一直循环到节点集合中，所有的节点都被遍历过后，所得到的最优解便是全局最优解。

该算法的优点是每一个节点的子问题都被转化成LP，而且尺度明显增大，这意味着每个子问题可以非常快的求解；而缺点就是基于分支定界法，求解效率高度依赖分支迭代次数。

给定了一个MLP的标准形式，对不同大小的算力进行测试，I是连续变量的范围，最小的测试案例只有60个，最大的有3000个。整数变量最小的有15个，最大的有50个。

横轴是给定的计算时间，如果某条曲线是更靠近左上方的，可以理解为在相应的时间内，解决问题更多，就是更高效。

整体看下来，前两种定制化的算法表现是最好的。整体处在左上方，只能求到局部最优的SBB和DICOPT（求解器）。在10秒以内的计算时间内这两种算法和定制化算法差距不是很大，但是当给定的求解时间更长时，这两种求解器其实并没有解决更多的问题，折线相对平缓一些，意味着在解决小问题的时候更高效，在解决大问题的时候时间是猛增的。

最后，在给定100秒，第三种定制化算法比不过另外4种算法，但它的好处是能够保证全局最优。当给出的固定时间在100秒的时候，求解出来的问题数量已经和SBB打平手，给定1000秒的时候，其实已经能够和前两种定制化算法基本一样，甚至赶超了。而且，可以看到当在10000秒最大计算时间的时候，只有前三种定制化算法完成了所有50个问题的求解。但其他商用的求解器没有实现完成50个的全部求解。通用的MINLP求解器最终只解决了36到37个问题，他们最通用，任何MINLP问题都可以求解，但计算效率的差距非常大。

案例收获：