Solving Billion-Scale Knapsack Problems
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed ComputingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Solving Large-Scale 0-1 Knapsack Problems and its Application to Point Cloud Resampling
0-1 knapsack is of fundamental importance in computer science, business, operations research, etc. In this paper, we present a deep learning technique-based method to solve large-scale 0-1 knapsack problems where the num…
Deep LearningEvaluating the impact of different types of crossover and selection methods on the convergence of 0/1 Knapsack using Genetic Algorithm
Genetic Algorithm is an evolutionary algorithm and a metaheuristic that was introduced to overcome the failure of gradient based method in solving the optimization and search problems. The purpose of this paper is to eva…
Addressing The Knapsack Challenge Through Cultural Algorithm Optimization
The "0-1 knapsack problem" stands as a classical combinatorial optimization conundrum, necessitating the selection of a subset of items from a given set. Each item possesses inherent values and weights, and the primary o…
Combinatorial OptimizationOn Strong NP-Completeness of Rational Problems
The computational complexity of the partition, 0-1 subset sum, unbounded subset sum, 0-1 knapsack and unbounded knapsack problems and their multiple variants were studied in numerous papers in the past where all the weig…
AllApproximating Solutions to the Knapsack Problem using the Lagrangian Dual Framework
The Knapsack Problem is a classic problem in combinatorial optimisation. Solving these problems may be computationally expensive. Recent years have seen a growing interest in the use of deep learning methods to approxima…
Model Selection