Solving Billion-Scale Knapsack Problems
This addresses a critical bottleneck for industries like finance, enabling practical deployment at unprecedented scales, though it is incremental as it builds on existing distributed computing frameworks.
The paper tackles solving large-scale knapsack problems, which are NP-hard and traditionally limited in scale, by proposing a distributed algorithm that achieves near-optimal solutions efficiently, such as solving problems with 1 billion variables and constraints within an hour.
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.