作者提出的是一个RL和Constraint Programming结合的求解组合优化问题的模型，在RL环境和约束规划模型中引入了基于动态规划模型的编码，编码后学习部分用强化学习进行，求解部分用约束规划进行。简单来说是用RL来辅助约束规划在搜索解空间时的分支决策。
为什么可以用动态规划呢？强化学习应用于组合优化问题是model-base的，既知道状态转移的情况，也知道reward函数。但是我觉得不是deterministic transition的情况下也是可以的，因为现在有很多model free的模型（AC）。
论文正文中给的例子是用RL的结果辅助分支界定法，RL的结果作为新的分支，分支界定法是会舍弃掉不可行解的，所以处理了约束问题。附录中还提到RL与另外两种搜索策略的结合。
框架：
DQN辅助分支界定法：
对于有时间窗口约束的旅行商问题，这篇文章是用GAT去编码。最后实验结果比单纯的DRL或者CP要好，与DRL做组合优化的其他文章相比也更好，而且与现行的工业组合优化求解器相比也有优势。
有时间窗口约束的旅行商问题的SOTA heuristic是A General VNS heuristic for the traveling salesman problem with time windows，前人已经用可变邻域搜索(VNS)的方法解决得很好了，能不能强化学习+VNS？
代码写得挺好的，RL和CP的主要结合点在这里，分支定界法取分支的时候，由DQN给出一系列Q值，CP选择最大的那个Q值对应的action，把domain分成采取这个action和采取其他action。
基于这种方法，有人还做了一个叫SeaPearl的CP求解器框架，用强化学习作为value-selection heuristics，用图作为输入。
https://github.com/corail-research/SeaPearl.jl
前言 现在大部分的边缘计算或者联邦学习的论文，都不免得会提出一个组合优化问题。但是我们现在做的很多组合优化问题都带有复杂的约束。
如果想直接用端到端的深度学习去做，无论是DL还是DRL，和传统的求解器相比，都是既没有办法保证能够得到可行解，也没有办法保证最优解。
提高解的可行性的一个很原始的方法是加惩罚项或者在目标函数上用拉格朗日乘数法。拉格朗日乘数法每有一个约束就要给目标函数加一项，最后一个目标函数有成千上万个项就尴尬了。又或者用更复杂的DRL网络结构（HDRL等），获得更好的性能。但是这和现在的计算机视觉任务或者自然语言处理任务刷分一样，在简单问题上你可能有100%的准确率，但是更复杂的问题又没有办法保证准确率100%，可行性和最优性也一样。
因此现在很多工作都喜欢多次采样取最优值，同时大大提高了可行性，但这也还是原始的做法，没有真正解决约束问题。
Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization (AAAI2021) 作者提出的是一个RL和Constraint Programming结合的求解组合优化问题的模型，在RL环境和约束规划模型中引入了基于动态规划模型的编码，编码后学习部分用强化学习进行，求解部分用约束规划进行。简单来说是用RL来辅助约束规划在搜索解空间时的分支决策。
为什么可以用动态规划，强化学习应用于组合优化问题是model-base的，既知道状态转移的情况，也知道reward函数。但是我觉得不是deterministic transition的情况下也是可以的，因为现在有很多model free的模型（AC）。
论文正文中给的例子是用RL的结果辅助分支界定法，RL的结果作为新的分支，分支界定法是会舍弃掉不可行解的，所以处理了约束问题。附录中还提到RL与另外两种搜索策略的结合。
和整数规划相比，约束规划可能小众一点，但不一定差，整数规划只能解线性问题和部分非线性问题，但约束规划可以解更general的问题。想讲这篇论文用的强化学习提供搜索heuristic的思路，这个思路是无关CP和MIP的，只是因为论文比较新才选的，因为新的论文，介绍和相关工作里面也能学到更多。
框架：
state: 点的特征，比如时间窗和坐标的静态特征，还有和DP相关的动态特征；边的特征，距离；
action: 对应DP的control；
transition: 也是DP的转移；
reward:
1+UB是一个严格上界，保证reward是正的，避免出现负reward导致提前结束。
DQN辅助分支界定法：
对于有时间窗口约束的旅行商问题，这篇文章是用GAT去编码。最后实验结果比单纯的DRL或者CP要好，与DRL做组合优化的其他文章相比也更好，而且与现行的工业组合优化求解器相比也有优势。
代码写得挺好的，RL和CP的主要结合点在这里，分支定界法取分支的时候，由DQN给出一系列Q值，CP选择最大的那个Q值对应的action，把domain分成采取这个action和采取其他action。
基于这种方法，有人还做了一个叫SeaPearl的CP求解器框架，用强化学习作为value-selection heuristics，用图作为输入
https://github.com/corail-research/SeaPearl.jl
A General VNS heuristic for the traveling salesman problem with time windows
这个应该是SOTA heuristic
前人已经用邻域搜索的方法解决得很好了，能不能强化学习+邻域搜索？
Solving mixed integer programs using neural networks（DeepMind和谷歌Research的团队） 提出了两个组件：Neural Diving和Neural Branching。
Neural Diving是通过深度神经网络生成一个partial assignments，然后交给solver去求解剩下的变量
Neural Branching是通过深度神经网络去模仿学习一个剪枝policy。
最先提出用二部图encode的应该是这篇文章(Exact Combinatorial Optimization with Graph Convolutional Neural Networks)。...