『约瑟夫·拉格朗日』如何在高精度下求解亿级变量背包问题？
本文插图
本文插图
导读：国际顶级会议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%） ， 在超大规模问题上可以忽略不计 。
推荐阅读
- 淘宝|如何在淘宝网上开网店？在淘宝网上开店有什么要求？
- Odaily星球日报|教程：如何在Polkadot CC1中映射并认领DOT
- CSDN|如何在容器内高效编程？
- 右手网|教程：如何在 MacOS Catalina 系统中安装新的免费字体
- 诺基亚|诺基亚将“三连发”，不过，这三款手机竞争力何在？
- pdf|如何在iPhone上将PDF转换为Excel
- eWisetech|E分析：消费者追求的那些高屏占比,是如何在手机中实现的
- 【】初创企业如何在“危”中找“机”？听听红杉资本等创投机构怎么说
- 迅捷CAD如何在CAD中插入Excel表格？一分钟教你学会两种方式
- 0769-如何在Kerberos环境下用Ranger完成对Hive的行过滤及列脱敏