Xingwen Zhang
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.
- Deepak Agarwal, Bee-Chung Chen, Pradheep Elango, and Xuanhui Wang. 2012. Personalized Click Shaping through Lagrangian Duality for Online Recommendation. In Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval, August 12 - 16, 2012. Portland, OR, USA, 485 – 494.Google Scholar
Digital Library
- Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press, Cambridge, UK.Google ScholarDigital Library
- P. C. Chu and John E. Beasley. 1998. A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics 4(1998), 63–86.Google ScholarDigital Library
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms(3rd ed.). The MIT Press, Cambridge, Massachusetts, USA.Google ScholarDigital Library
- CPlex. [n.d.]. www.cplex.com.Google Scholar
- George B. Dantzig. 1957. Discrete-Variable Extremum Problems. Operations Research 5, 2 (April 1957), 266–277.Google ScholarDigital Library
- Jeffrey Dean and Sanjay Ghemawat. 2008. MapReduce: Simplified Data Processing on Large Clusters. Commun. ACM 51(2008), 107–113.Google ScholarDigital Library
- Fred Glover. 1989. Tabu Search - Part I. ORSA Journal on Computing 1 (1989), 135–206.Google ScholarCross Ref
- Rupesh Gupta, Guanfeng Liang, and Rómer Rosales. 2017. Optimizing Email Volume For Sitewide Engagement. In Proceedings of the 26th ACM CIKM International Conference on Information and Knowledge Management, November 6 - 10, 2017. Singapore, 1947 – 1955.Google ScholarDigital Library
- Rupesh Gupta, Guanfeng Liang, Hsiao-Ping Tseng, Ravi Kiran Holur Vijay, Xiaoyu Chen, and Rómer Rosales. 2016. Email Volume Optimization at LinkedIn. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 13 - 17, 2016. San Francisco, CA, USA, 97 – 106.Google ScholarDigital Library
- Gurobi. [n.d.]. www.gurobi.com.Google Scholar
- Skander Htiouech and Sadok Bouamama. 2013. OSC: Solving the Multidimensional Multi-choice Knapsack Problem with Tight Strategic Oscillation using Surrogate Constraints. International Journal of Computer Applications 73 (2013), 1–22.Google ScholarCross Ref
- Hans Kellerer, Ulrich Pferschy, and David Pisinger. 2004. Knapsack Problems. Springer, Berlin.Google Scholar
- Shahadatullah Khan. 1998. Quality Adaptation in a Multisession Multimedia System: Model, Algorithms and Architecture. Ph.D. Dissertation. Department of Electrical and Computer Engineering, University of Victoria, Canada.Google Scholar
- S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by Simulated Annealing. Science 220(1983), 671–680.Google ScholarCross Ref
- Soukaina Laabadi, Mohamed Naimi, Hassan E. Amri, and Boujemâa Achchab. 2018. The 0/1 Multidimensional Knapsack Problem and Its Variants: A Survey of Practical Models and Heuristic Approaches. American Journal of Operations Research 8 (2018), 395–439.Google ScholarCross Ref
- Silvano Martello and Paolo Toth. 1990. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Chichester.Google ScholarDigital Library
- Laurent Perron and Vincent Furnon. [n.d.]. Google OR-Tools, https://developers.google.com/optimization.Google Scholar
- Jeremy F. Shapiro. 1979. A survey of Lagrangean techniques for discrete optimization. Annals of Discrete Mathematics 5 (1979), 113–138.Google ScholarCross Ref
- Stephen J. Wright. 2015. Coordinate Descent Algorithms. Mathematical Programming, Series B 151 (2015), 3–34.Google ScholarDigital Library
- Bo Zhao, Koichiro Narita, Burkay Orten, and John Egan. 2018. Notification Volume Control and Optimization System at Pinterest. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 19 - 23, 2018. London, United Kingdom, 1012 – 1020.Google ScholarDigital Library
Index Terms
- Solving Billion-Scale Knapsack Problems
Recommendations
Exact approaches for the knapsack problem with setups
We study a generalization of the knapsack problem in which items are partitioned into classes, known as knapsack problem with setups (KPS).We study three alternative Integer Linear Programming formulations for KPS.We design efficient algorithms to ...
On the solution of concave knapsack problems
We consider a version of the knapsack problem which gives rise to a separable concave minimization problem subject to bounds on the variables and one equality constraint. We characterize strict local miniimizers of concave minimization problems subject ...
A Practical Distributed ADMM Solver for Billion-Scale Generalized Assignment Problems
CIKM '22: Proceedings of the 31st ACM International Conference on Information & Knowledge ManagementAssigning items to owners is a common problem found in various real-world applications, for example, audience-channel matching in marketing campaigns, borrower-lender matching in loan management, and shopper-merchant matching in e-commerce. Given an ...
Comments