導讀：國際頂級會議WWW2020將於4月20日至24日舉行。始於1994年的WWW會議，主要討論有關Web的發展，其相關技術的標準化以及這些技術對社會和文化的影響，每年有大批的學者、研究人員、技術專家、政策制定者等參與。以下是螞蟻金服的技術專家對入選論文《Solving Billion-Scale Knapsack Problems》做出的解讀。
作者 | 齊馮
出品 | AI科技大本營（ID:rgznai100）
揹包問題 (knapsack problem) 是經典的整數規劃問題，求解如何從多個物品中選取一個子集放入揹包，在容量限制下最大化子集的效用。互聯網場景下很多問題可以看成超大規模的揹包問題或者它的變種問題，比如紅包營銷，用戶流量分配等，都有某種總資源的限制，需要在大量的用戶粒度的決策中選取一個子集來最大化業務收益。
由於揹包問題是 NP-hard，求解複雜度高，所以精確算法無法做較大規模的求解。而近似類算法對問題的形式化有具體要求，實際業務的需求一般不會嚴格符合揹包問題的定義，所以需要求解算法有更強的泛化性和通用性。因此，如何在高精度下求解超大規模揹包問題及其變種問題仍然是一個挑戰。
簡介
據我們所知，我們的工作是最早做到對億級變量的揹包問題求解工作之一。我們的問題形式化涵蓋了互聯網海量數據場景下的泛化揹包問題。它的“物品”有兩個維度：用戶和選項，即“為每位用戶選擇哪些選項”。它的“揹包容量”擴展到了多個維度，即每個用戶的每個選項可以消耗多個不同的資源。同時我們還支持對每個用戶的選項做任意整數規劃的約束。整個形式化的數學表達如下：
上式中的 (2) 為資源約束，我們稱之為“全局約束”，一般不超過幾十個或上百個，（3）為每個用戶的選則規則，我們稱之為“局部約束”，數量可以上億。為了求解這個超大規模的泛化揹包問題，我們採用拉格朗日鬆弛求解整數規劃（Lagrangian relaxation for integer programming）的框架，將全局約束（2）乘以拉格朗日乘子後合併到目標函數（1）中。給定拉格朗日乘數，鬆弛過的問題可以拆解為每個用戶獨立的整數規劃問題，這些問題數量可能上億，可以並行化求解。
當這些整數規劃的約束（3）符合特定的層級化形式時，我們提出了可以求得最優解的多項式複雜度算法，而更復雜的約束形式則可以通過通用整數規劃求解器求解。為了求得拉格朗日乘數的最優解，我們採用同步座標梯度下降（Synchronous Coordinate Descent）法在當前拉格朗日乘數的基礎上對每個乘數做獨立並行優化。整個算法交替進行拉格朗日乘數更新和獨立並行整數規劃這兩個步驟，直到收斂。解決方案的實現在 Apache Spark 上通過 MapReduce 接口完成。
解讀
拉格朗日鬆弛求解整數規劃的框架只提供最優解的驗證條件，我們仍需要對具體的算法驗證解的正確性和求解流程的速度。為驗證正確性，我們對比了我們的算法的解和單純形法 (Simplex) 求解線性鬆弛後問題的解，還評價了我們解的對偶間隙 (duality gap)，發現我們求得的目標函數值距離理論上界差距極其微小（~1%），在超大規模問題上可以忽略不計。
速度方面，我們的 MapReduce 實現求解億級變量十級資源約束的問題可以在一小時內收斂，佔用 200 個 Spark executors (1600 個CPU)。此外，我們對比了同一框架下常用的對偶梯度下降（Dual Descent）和我們設計的SCD這兩種方法。後者不僅在需要的迭代輪數上少於前者，在約束的遵守上也遠比前者嚴格。我們設計的 SCD 利用拆解後的子問題的具體形式預判重要的拉格朗日乘數值，用高精度掃描最優解附近的乘數值，從而達到快速準確的收斂。
前景
我們泛化後的揹包問題形式覆蓋了很多互聯網場景下的用戶顆粒度的多資源分配問題，同時我們的實現以及業務落地經驗證明了我們求解方法在超大規模優化問題上的可操作性和實際效果。因此這個解決方案應該對互聯網行業有較強的參考價值。
今日福利
遇見陸奇
同樣作為“百萬人學 AI”的重要組成部分，2020 AIProCon 開發者萬人大會將於 7 月 3 日至 4 日通過線上直播形式，讓開發者們一站式學習瞭解當下 AI 的前沿技術研究、核心技術與應用以及企業案例的實踐經驗，同時還可以在線參加精彩多樣的開發者沙龍與編程項目。參與前瞻系列活動、在線直播互動，不僅可以與上萬名開發者們一起交流，還有機會贏取直播專屬好禮，與技術大咖連麥。
