4-3 Learning-aided Large Scale Optimization in Supply Chain and EDA

工业优化问题与实际瓶颈

约束优化与数学求解器

• 价值：Gurobi年收益1亿美元+，Xpress年收益11亿美元+
• 实用性：弥补纯启发式方法不足，通过数学模型限定搜索范围，实现更高效的启发式搜索。
• 特点：求解器包含多种启发式策略，约束优化的一般数学模型包括线性规划、混合整数规划、二次规划等。

线性问题求解

• Simplex方法：将优化问题转化为线性方程组求解，通过顶点迭代寻找最优解。
• 现有技术：入基选择、出基选择、最优性检验等步骤，可能面临浮点数计算误差等问题。
• 可视化：从一个顶点逐步找到下一个更合适的顶点，最终找到最优解。

离散问题求解

• Branch and Bound (BB)：通过不断分支和剪枝，找到满足所有约束的解。
• MIP与SAT：MIP和SAT求解器分别应用于混合整数规划和布尔满足性问题，通过branch and bound策略实现高效求解。

增量计算与有效初始化

增量计算

• 数据结构：维护非基变量及其reduced cost值，通过堆栈结构进行排序和更新，提升大规模问题的计算性能。
• 实例效果：在大规模问题求解中，平均降低原有Simplex计算时间50%以上。

初始化解

• 增量计算：通过修正松弛模型，获得高质量初始解，缩短全流程计算时间。
• MIP任务：在华为供应链多工厂排产问题中，提高了10%以上的计算性能，且稳定输出结果。

是否学习能帮助优化

学习优化研究

• MIP求解器：利用机器学习加速启发式算法，如神经网络辅助分支选择。
• SAT求解器：通过数据驱动的方法选择更好的原始启发式方法。
• 实验结果：在不同类型的问题上，学习方法能显著提升求解效率，但在某些情况下效果有限。

总结

• 核心要点：通过数学模型和启发式方法的结合，利用机器学习优化求解过程，特别是在大规模问题和复杂约束条件下，显著提升了求解效率和稳定性。
• 关键数据：Gurobi和Xpress的年收益分别为1亿美元和11亿美元，MIP和SAT求解器在大规模问题上平均提升计算性能50%以上。