论文标题
解决十亿个尺寸的背包问题
Solving Billion-Scale Knapsack Problems
论文作者
论文摘要
背包问题（KPS）在行业中很常见，但是解决KPS是NP-HARD的，并且仅在相对较小的规模上才能进行处理。本文以略有概括的形式研究了KP，并表明它们可以通过分布式算法在大小上几乎最佳地求解。通过现成的分布式计算框架（例如MPI，Hadoop，Spark），可以轻松实现所提出的方法。例如，我们的实施导致迄今为止已知的最有效的KP求解器之一 - 能够以前所未有的规模求解KP（例如，可以在1小时内解决具有10亿个决策变量和10亿个约束的KPS）。该系统已被部署到生产中，并每天召集，从而对Ant Financial产生了重大业务影响。
Knapsack problems (KPs) are common in industry, but solving KPs is known to be NP-hard and has been tractable only at a relatively small scale. This paper examines KPs in a slightly generalized form and shows that they can be solved nearly optimally at scale via distributed algorithms. The proposed approach can be implemented fairly easily with off-the-shelf distributed computing frameworks (e.g. MPI, Hadoop, Spark). As an example, our implementation leads to one of the most efficient KP solvers known to date -- capable to solve KPs at an unprecedented scale (e.g., KPs with 1 billion decision variables and 1 billion constraints can be solved within 1 hour). The system has been deployed to production and called on a daily basis, yielding significant business impacts at Ant Financial.
