Deep Symbolic Optimization for Combinatorial Optimization: Accelerating Node Selection by Discovering Potential Heuristics

组合优化（CO）是实际应用中最基本的数学模型之一。传统的CO求解器，例如分支定界（B＆B）求解器，严重依赖专家设计的启发式算法，这些启发式算法虽然可靠，但需要大量手动调整。最近的研究利用深度学习（DL）模型作为一种替代方法，以捕获丰富的特征模式，以在GPU机器上提高性能。然而，高训练和推理成本以及有限的可解释性的缺点严重阻碍了DL方法在实际应用中的采用。为了解决这些挑战，我们提出了一种新颖的深度符号优化学习框架，结合了它们的优点。具体而言，我们专注于B＆B求解器中的节点选择模块，即节点选择的深度符号优化（Dso4NS）。通过数据驱动方法，Dso4NS引导在高维离散符号空间内搜索数学表达式，然后将最高性能的数学表达式合并到求解器中。数据驱动模型捕捉输入数据中的丰富特征信息并生成符号表达式，而在求解器中部署的表达式可以实现高可解释性的快速推理。实验表明，Dso4NS在学习高质量表达式方面具有很好的效果，在CPU机器上优于现有方法。令人鼓舞的是，学习的基于CPU的策略始终实现与最先进的基于GPU的方法相当的性能。

论文旨在解决传统组合优化算法在实际应用中需要手动调整启发式算法的问题，提出一种结合深度学习和符号优化的框架来学习高效的节点选择策略。

论文提出了一种基于深度符号优化的节点选择模块（Dso4NS）来指导搜索高维离散符号空间中的数学表达式，并将表现最佳的数学表达式应用于求解器中。该方法结合了深度学习模型的数据驱动优势和符号优化模型的高效推理和可解释性。

实验表明，Dso4NS可以学习高质量的表达式，在CPU机器上优于现有方法。研究还提供了数据集和开源代码。该方法可以为组合优化问题提供一种可行的解决方案。

最近的相关研究包括基于深度学习的组合优化求解器和符号回归模型。