組合優化在航空航天、交通規劃以及經濟學等衆多學科領域中有廣泛應用，其目标是在有限集中尋找最優解。然而狀态空間過大的問題讓目前組合優化變得棘手。在過去的幾年中，使用深度強化學習（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 Encoding
State
Action
Transition
Reward
Network 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.