工业优化问题与实际瓶颈
约束优化与数学求解器
- 价值：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%以上。
