4-3 供应链和EDA中的学习辅助大规模优化.pdf

1、LEARNING-AIDED L ARGE SCALE OPTIMIZATION IN SUPPLY CHAIN&EDA 甄慧玲 华为 主任工程师|01Industrial Optimization Problems&Practical Bottleneck02目录CONTENT|03 04Incremental Computation&Effective InitializationWhether Learning Can Help?Conclusions&Some Insights|01Industrial Optimization Problems&Practical Bottlenec

2、kConstraint Optimization&Mathematical Solver价值：Gurobi年收益1亿美金+，XPRESS 年收益11亿美金+实用性：弥补了纯启发式的不足，以数学模型为媒介，在数学模型限定的范围内可以执行更加高效的启发式搜索特点：求解器从来不排斥启发式方法，当前求解器即使是开源版本也包含上百种的启发式策略。求解器和启发式方法的最大不同在于数学模型。约束规定了最大的搜索空间，并规定了所有可能的搜索路径，在这样的路径下不同的启发式方法高效配合。约束优化的一般数学模型：数学方法数据结构+programming skills输入输入 根据目标和约束的形式，数学优化模型往往

3、分成以下几类：线性规划（Linear Programming）a)约束和目标全都是线性的b)变量是浮点数 混合整数规划（Mixed Integer Programming）a)约束和目标都是线性的b)一部分变量必须是整数 二次规划（Quadratic Programming)a)目标或约束中含有x2b)有些文献显示nonlinear programming，但人类目前可以求解的模型其实不包括通用的三次的模型（例如：约束或者目标中含有x3）随机规划（Stochastic Programming）a)目标，约束受到随机扰动，需要计算的是平均意义下的最优解 约束规划（Constraint Progr

4、amming）a)约束中含有特殊约束：集合约束：x属于或者不属于A；顺序约束：x和y之间x必须比y先到达（排队模型、调度模型）SAT(Boolean Satisfactory)a)所有的变量均是布尔变量（0-1），没有目标，一般不需要解的评估b)SAT模型可以转化成MIP。目标约束Mathematical Programming优化问题的求解空间是约束定义的 求解器：给定一个数学模型，得到模型中变量的合法的并且达到目标的赋值目标用于评估求解质量|线性问题求解SimplexSimplex方法的核心：将优化问题转化成一系列线性方程组的求解问题本质上是在凸多面体的顶点上，根据目标最优化方向在众多顶点

5、上进行迭代，直到目标无法再优化为止。Simplex现有技术核心步骤为入基选择：基于当前顶点，选择哪一个方向作为下一步移动，能够进一步优化目标函数？出基选择：确保移动步长是合法，即如何从一个“基可行解”另一个“基可行解”？最优性检验：当前解是否已是最优解？Simplex在计算中可能碰到的问题：不断迭代的线性方程组求解，带来的浮点数的计算误差入基变量选择不准确，浪费搜索次数出基变量选择不准确，影响矩阵的条件数稳定性初始解往往比最优解刚耗时 Simplex方法的可视化：总是从凸多面体的一个顶点，找下一个更合适的顶点，从而找到最优解。第一个顶点：可行解找初始可行解找最优解线性方程组求解选择变量，完成增

6、量式更新|离散问题求解Branch and Bound Branch and bound（BB）是一种通用的搜索策略，并不局限于任何顶层模型的设计和结构。Branch and bound的核心分两部分：Branch selection Conflict propagation 以Largest neighborhood search为例，说明BB策略在启发式方法中的应用。不断的分支，完成对求解空间的搜索过程。Bound:利用求解的中间信息完成对搜索空间的pruning lower bound是指搜索过程中一个partial solution（比如上图插入2后形成的3个partialsoluti