机器学习 (ML) 和运筹学 (OR) 历来是两个独立的学科，从业者社区互不交叉。每个领域都有不同的重点、工具和目标。两种方法通常是相互补充的，并且将它们结合起来的潜力很大，近年来一度成为研究热点。
ML可以应用在OR中的一种特殊方式是改善算法和求解器设计过程。OR有时被称为决策科学。在优化算法内，不断做出大量决策，而这些决策本身就是困难的计算问题。这是 ML 可以探索的一个比较有前途的地方，目前已经有一些应用示例。
Strong branching（强分支）
分支定界法 (B&B) 是现代混合整数线性规划 (MILP) 求解器的强大动力。该算法中重复的决策之一是选择一个非整数变量进行分支。这是任何 B&B 算法中的关键步骤，因为分支的质量影响着 B&B 树的大小，进而影响整个算法的运行时间。许多研究工作都致力于设计出更好的选择要分支变量的方法。
始终产生最小 B&B 树的分支策略是强分支。强分支是一种前瞻策略：该算法考虑了线性规划 (LP) 松弛下每个非整数变量的不同整数选择，并选择了最有希望的一个。尽管这是一种在实践中表现良好的策略，但计算成本较为昂贵。
Gasse等人提出了使用图神经网络 (GNN) 来解决变量选择问题，以模仿强分支启发法[1]的分支决策。GNN是一种深度学习模型，专为处理和分析表示为图的结构化数据而设计，其能够捕捉图中的关系和模式。Gasse的GNN算法基于MILP的二元变量来执行，其中变量和约束是节点，如果变量出现在该约束中，则边将变量节点连接到约束节点。
他们使用模仿学习从强分支专家规则中训练模型。模仿学习是一种机器学习方法（与强化学习相似），其中代理通过观察和模仿专家的行为来学习一项任务，通常使用专家数据集来训练模型。训练过程涉及运行 B&B 算法并收集子问题及其相应的强分支决策（这些都是离线完成的）。
采用这种方法背后的原因是，通过训练模型来复制完整的强分支启发式生成模型，虽然不一定完美，但也能够可靠地识别出好的分支，并且在不同的数据集上报告了较好的结果。基于此，机器学习模型的成功部署成为了模型求解准确性与求解速度间的折中方式。当然一些别的具有竞争性的机器学习模型可以提供更高的准确性，但 GNN 在运行 B&B 的总时间上击败了它们。
基于GNN的优化算法核心是识别数据潜在的底层模式，特别是关注变量约束图的拓扑结构和系数结构，以确定适合分支的非整数变量。通过使用 GNN，无需进行手动特征工程，从而允许网络捕获这些模式。此外，GNN 使用共享参数表示，可以将其应用于不同大小的网络，该方法即使在比用于训练的更大的图形上也表现良好，因此也出现了很多进一步发展以及不断改进这些技术的研究。
Chip Placement（芯片布局）
芯片布局问题是半导体设计中的一个关键挑战，其中电子元件（宏）必须经过战略性布置在硅片上，以优化性能、最小化布线长度、减少信号拥塞并管理散热方面的考虑，同时遵守严格的设计规范。这是一项巨大的组合任务（数百万到数十亿个节点），类似于完成一块复杂的拼图，获得最佳布局对于各种电子设备中的集成电路的功能性、速度和效率至关重要。一般情况下，这项任务主要依靠人力专业知识和启发式方法，而随着芯片设计变得越来越复杂，传统方法面临的挑战也随之增加。
Mirhoseini等人提出了一个新的、基于学习的方法来解决这个问题，该方法实现了超乎人类水平的性能[2]。该论文的核心创新是围绕深度强化学习技术的利用，对元件布局做出智能决策。它采用边卷积 GNN（edge-based convolutional GNN），通过强化学习进行训练--一种让智能体通过与环境交互学习做出顺序决策的机器学习范式，以累积奖励信号最大化为目标。
在每次训练迭代中，模型按顺序放置芯片块。每次迭代结束时模型的奖励是对代理电线长度和拥塞的负加权和。这两个设计参数反映了设计的性能表现。通过重复的迭代，智能体学会做出能产生卓越芯片布局的决策。强化学习使用户能够高效地探索放置空间并发现最佳配置，最终缩短设计时间并可能提升芯片性能。
作者报告了他们的设计的芯片布局结果，要么优于、要么与人类专家芯片设计师创造的芯片布局不相上下。而性能最高的备选方案需要人类专家的参与，每个芯片的多个区块布局需要花费数周时间。
More Approaches（更多方式）
最根本的是，大量的求解器配备了一系列可微调的参数，这些参数可以在求解之前或者运行时动态微调。显然，这是一个应用机器学习的理想机会。可以训练机器学习模型，在给定问题实例或根据运行时做出的历史选择的基础上，确定最佳参数配置[3]。
算法选择是一种从算法库中为特定问题实例选择最适合算法的另一种方法。此任务可以委托给ML模型，该模型可以使用从优化问题实例中提取的工程化特征（或无特征)）深度学习模型[4]进行训练。
还有几篇有价值的综述文章涵盖了该领域各方面的内容[5-7]。
Key Takeaways（要点）
将机器学习集成到运筹学求解器中并由此自动完成优化求解器的设计，提供了很多令人惊叹的优势。首先，这降低了对大量人类领域专业知识的需求，最大程度减少劳力资源，并显著缩短了为优化问题设计新算法所需的时间，而这些相比传统的算法设计流程而言，具有很大的优势。
其次，通过充分探索算法前景，自动化设计有潜力超越人类设计水平，从而超越传统设计算法的性能。第三，这可能使运筹学工具的可用性更加广泛，将其应用范围扩展至更多专业人员，包括那些可能不具备优化理论基础的数据科学家。
第四，它为专门针对特定类型难题而设计的求解器（无论是精确求解器还是启发式求解器）的发展打开了大门。最后，可以推断，随着对大量 MILP 实例的出现，大规模训练模型可能会出现，从而能够提供普遍有效的解决方案。可以将此置于大语言模型的背景下，后者通过大量接触各种语言数据证明了非凡的能力。
References
Gasse, Maxime, Didier Chetelat, Nicola Ferroni, Laurent Charlin and Andrea Lodi, 2019, “Exact combinatorial optimization with graph convolutional neural networks,” Advances in Neural Information Processing Systems, Vol. 32 (NeurIPS 2019). Mirhoseini, Azalia, et al., 2021, “A graph placement methodology for fast chip design,” Nature, 594, No. 7862, pp. 207-212.
Stützle, Thomas and Manuel López-Ibáñez, 2019, “Automated design of metaheuristic algorithms,” Handbook of Metaheuristics, New York: Springer, pp. 541-579.
Kerschke, Pascal, Holger H. Hoos, Frank Neumann and Heike Trautmann, 2019, “Automated algorithm selection: Survey and perspectives,” Evolutionary Computation, Vol. 27, No. 1, pp 3-45.
Bengio, Yoshua, Andrea Lodi and Antoine Prouvost, 2021, “Machine learning for combinatorial optimization: A methodological tour d’horizon,” European Journal of Operational Research, Vol. 290, No. 2, pp. 405-421.
Cappart, Quentin, Didier Chetelat, Elias B. Khalil, Andrea Lodi, Christopher Morris and Peter Velickovic, 2023, “Combinatorial optimization and reasoning with graph neural networks,” Journal of Machine Learning Research, Vol. 24.
Karimi-Mamaghan, Maryam, Mehrdad Mohammadi, Patrick Meyer, Amir Mohammad Karimi-Mamaghan and El-Ghazali Talbi, 2022, “Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art,” European Journal of Operational Research, Vol. 296, No. 2, pp. 393-422.
原文连接：Data-Driven Optimization: Enhancing Combinatorial Optimization Solvers with Machine Learning | Analytics Magazine (informs.org)
