组合优化在航空航天、交通规划以及经济学等众多学科领域中有广泛应用，其目标是在有限集中寻找最优解。然而状态空间过大的问题让目前组合优化变得棘手。在过去的几年中，使用深度强化学习（deep reinforcement learning，DRL）解决组合优化问题受到广泛关注。然而，现有的方法有两大缺点：

大部分工作主要集中在标准的TSP问题上，推广到其他问题并不容易。只能提供一个近似最优解或者满意解，没有一个系统的方法来提升解的质量或者证明其最优性。

另一方面，约束规划（constraint programming，CP）是一种用于解决组合优化问题的有效方法，基于完全搜索的策略，如果时间足够，总可以找到最优解。分支决策是CP的关键选择，用于指导如何探索剩余的搜索空间。

本篇论文 [1] 的工作提出了一种基于DRL和CP的通用方法来解决组合优化问题。方法的核心是将动态规划作为连接两种方法的桥梁，首先通将组合优化问题建模成动态规划形式，再使用深度强化学习方法学习分支搜索方法，将学习到的agent用于CP的分支选取中，从而进一步提升CP的搜索效率提升算法性能。具体的结构如图1所示。

整体结构分为三个阶段，统一表示阶段是指将组合优化问题描述为动态规划模型，该动态规划模型既可以进一步描述为深度强化学习的训练形式用于训练agent，也可以进一步描述为CP模型并根据分支选择策略进行搜索求解。学习阶段主要通过随机生成的方法生成很多约束规划问题的样本，并根据样本进行求解训练。求解阶段将需要求解的问题实例通过动态规划描述为CP模型，并根据学习到的agent进行分支选择求解。图1中的蓝色模块为已有的成熟算法，绿色模块为本文的工作。

图1 本篇论文总体方法架构

总的来说，本文结合了search-based和learning-based两种方法。基于搜索的方法可以保证最优解，但是往往不能从历史数据中得到经验，并且搜索过程有很大的提升空间。基于学习的方法可以利用历史经验，但是不能保证最优并且没有行之有效的提升手段。本文的方法结合了两者的优点，既可以保证最优解，又可以利用历史经验，同时还可以提升搜索效率。

将组合优化写为动态规划（DP）模型

动态规划是一种结合数学建模和编程的方法，通常用于解决复杂的优化问题。动态规划主要通过将问题分解为多阶段子问题，并通过状态转移方程将不同状态联系起来。通过最终的状态反向递推求解每个阶段的解。

但是通常动态规划问题面临维数灾挑战，通常的操作是对支配动作进行剪枝，如果满足以下两个条件之一，该动作会被剪枝：

•根据递推公式，严格地比另一个动作差​

•无法产生一个可行的状态转移​

但是在实际问题中，虽然剪枝策略可以有效的减少搜索空间，但是由于这两个条件是problem-dependent，因此识别这两个条件开销比较大。此外，有的问题即使进行了剪枝，动作集的维数仍然很大。

RL EncodingStateActionTransitionRewardNetwork Architecture and Learning Algorithm

无论是应用DQN还是PPO训练架构，本文均首先随机生成一系列训练样本，并使得训练样本的分布与我们试图解决问题的分布一致，这也是目前绝大多数应用机器学习求解NP-hard优化问题的研究的做法。

CP Encoding

约束规划（constraint programming，CP）是一种泛用性比较好的算法框架，在实际应用中常用于处理复杂的组合问题。因为应用场景和算法框架的相似，但却不像后者应用范围如此之广，所以人们常常将CP与整数规划（LP）进行比较，来更好的理解CP的特点与优势，如下图所示，虽然两种算法的框架都是系统性的搜索，但是在搜索中，CP不需要同时保证所有约束成立，而是对约束逐一分析，即约束传播（constraint propagation），再对变量的值域进行过滤，这使得CP在更复杂的组合问题（可行域连续性较差）中经常有超过LP的表现。

Search Strategy

从前文中，我们已经将同一个DP模型同时转换为RL模型和CP模型，这使得我们可以将RL中训练得出的agent用于CP求解的搜索过程中，针对于不同的应用场景和不同的RL模型，本文提供了三种不同的CP搜索策略，深度优先分枝定界depth-first-branch-and-bound search (BaB),有限差异束搜索iterative limited discrepancy search (ILDS) 基于数值优化进行搜索，更适合于DQN训练出的Agent，而重启搜索restart based search需要一定的策略随机性，更适合policy-based的强化学习训练模型。

实验结果

为了评估算法的性能，本文在两个应用场景上分别测试了三种基于RL的CP搜索策略的算法，RL和CP不结合各自单独求解的算法以及一些工业求解器的算法，其中第一个测试场景为the travelling salesman problem with time windows (TSPTW)，是包含非线性约束的常见组合优化问题，另一个测试场景为4-moments portfolio optimization problem (PORT)，则是目标为非线性函数的经典组合优化问题。为确保公平性，训练时常都限制再48小时之内，内存占用在1Gb之内，都使用同一台GPU (Tesla V100-SXM2-32GB)执行所有算法。

TSPTW 实验结果

Table1中，我们可以看在城市的数量增长后 OR-Tools、CP-model 和 DQN 的结果明显差于各种RL和CP的混合方法。在混合方法中，基于 DQN 的搜索在寻找解决方案和证明最优性方面都给出了最好的结果。同时使用cache能够明显的提升混合算法的效率。这是因为RL训练得到模型调用次数极多，使用缓存会节约大量的搜索时间。

Table 1 主要实验结果1

Table 1 各算法在100个算例上的运行结果，Success代表找到可行解，Opt代表找到的是最优解，⋆代表使用了cache

PORT实验结果

Table 2 主要实验结果2

Table 2 各算法在100个算例上的运行结果，其中高亮的是表现最好的算法，Sol代表算法给出的最优平均收益，Opt代表达到最优解的算例个数。

总结

约束规划算法在组合优化中应用广泛且在复杂组合优化中表现出色，但性能受限于变量的搜索策略，本文通过动态规划作为桥梁联通强化学习和约束规划，将DQN和PPO等强化学习策略和BaB、RBS等搜索策略相结合，使得强化学习训练得到的经验能够帮助更好的进行CP搜索，同时在TSPTW和PORT两个普通组合优化算法表现不佳的非线性应用场景中进行了测试，展现了混合算法的显著提升。

参考文献

[1] Cappart, Q., Moisan, T., Rousseau, L. M., Prémont-Schwarz, I., & Cire, A. A. (2021, May). Combining reinforcement learning and constraint programming for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 5, pp. 3677-3687).

[2] Burak Gökgür, Brahim Hnich & Selin Özpeynirci (2018) Parallel machine scheduling with tool loading: a constraint programming approach, International Journal of Production Research, 56:16, 5541-5557, DOI: 10.1080/00207543.2017.1421781

[3] Kanet, John J.; Ahire, Sanjay L.; and Gorman, Michael F., "Constraint Programming for Scheduling" (2004). MIS/OM/DS Faculty Publications. Paper 1.