摘要
单阶段神经组合优化求解器在各种小规模组合优化(CO)问题上取得了接近最优的结果,无需专家知识。然而,这些求解器在应用于大规模CO问题时表现出明显的性能下降。最近,采用分治策略的两阶段神经方法在解决大规模CO问题方面展现出效率。然而,这些方法的性能高度依赖于分治过程中的特定问题启发式方法,这限制了它们对一般CO问题的适用性。此外,这些方法采用单独的训练方案,忽略了分治策略之间的相互依赖关系,这往往会导致次优解。为了解决这些缺点,本文开发了一个统一的神经分治框架(UDC)来解决一般的大规模CO问题。UDC提供了一种分治重组(DCR)训练方法,以消除次优分治策略的负面影响。通过采用高效的图神经网络(GNN)进行全局实例分治,以及采用固定长度子路径求解器来解决分治后的子问题,所提出的UDC框架展现出广泛的适用性,在10个代表性的大规模CO问题中取得了优异的性能。代码可在https://github.com/CIAM-Group/NCO_code/tree/main/single_objective/UDC-Large-scale-CO-master获取。