HackerPapers

arXiv:2002.00352cs.DC

Solving Billion-Scale Knapsack Problems

Xingwen Zhang, Feng Qi, Zhigang Hua, Shuang Yang

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

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.

arXiv comments
Journal reference
DOI
Subjects
cs.DCDistributed, Parallel, and Cluster Computing cs.AIArtificial Intelligence cs.DSData Structures and Algorithms

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Oct 2023 to Oct 2023. Found in 1 HN submission from Feb 2020 to Feb 2020. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Reconciliation is a knapsack problem 1 comment

    • lol at ai for solving deterministic knapsacks. Just get yourself a solver. And if you wanna solve billion item sized problems hire an OR scientist to write a decomposed algo. Literally after 2 minutes of search: https://arxiv.org/pdf/2002.00352.pdf

      whatever1View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.