More Web Proxy on the site http://driver.im/

research-article

Revisiting Sparse Dynamic Programming for the 0/1 Knapsack Problem

Authors:

Tarequl Islam Sifat,

Nirmal Prajapati,

Sanjay RajopadhyeAuthors Info & Claims

ICPP '20: Proceedings of the 49th International Conference on Parallel Processing

Article No.: 46, Pages 1 - 10

https://doi.org/10.1145/3404397.3404462

Published: 17 August 2020 Publication History

Abstract

The 0/1-Knapsack Problem is a classic NP-hard problem. There are two common approaches to obtain the exact solution: branch-and-bound (BB) and dynamic programming (DP). A so-called, “sparse” DP algorithm (SKPDP) that performs fewer operations than the standard algorithm (KPDP) is well known. To the best of our knowledge, there has been no quantitative analysis of the benefits of sparsity. We provide a careful empirical evaluation of SKPDP and observe that for a “large enough” capacity, C, the number of operations performed by SKPDP is invariant with respect to C for many problem instances. This leads to the possibility of an exponential improvement over the conventional KPDP. We experimentally explore SKPDP over a large range of knapsack problem instances and provide a detailed study of the attributes that impact the performance.

DP algorithms have a nice regular structure and are amenable to highly parallel implementations. However, due to the dependence structure, parallelizing SKPDP is challenging. We propose two parallelization strategies (fine-grain and coarse-grain) for SKPDP on modern multi-core processors and demonstrate a scalable improvement in the performance. We also compare SKPDP with Branch-and-Bound algorithm.

References

[1]

R. Andonov and S. Rajopadhye. 1997. Knapsack on VLSI: from Algorithm to Optimal Circuit. IEEE Transactions on Parallel and Distributed Systems 8, 6 (June 1997), 545–561.

Digital Library

[2]

R. Andonov and S. V. Rajopadhye. 1994. A Sparse Knapsack Algo-tech-cuit and its Synthesis. In International Conference on Application-Specific Array Processors (ASAP-94). IEEE, San Francisco, 302–313.

[3]

Victor C.B. Camargo, Leandro Mattiolli, and Franklina M.B. Toledo. 2012. A knapsack problem as a tool to solve the production planning problem in small foundries. Computers and Operations Research 39, 1 (2012), 86–92. https://doi.org/10.1016/j.cor.2010.10.023 Special Issue on Knapsack Problems and Applications.

Digital Library

[4]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition(3rd ed.). The MIT Press.

Digital Library

[5]

Leonardo Dagum and Ramesh Menon. 1998. OpenMP: An Industry-Standard API for Shared-Memory Programming. IEEE Comput. Sci. Eng. 5, 1 (Jan. 1998), 46–55. https://doi.org/10.1109/99.660313

Digital Library

[6]

F. de Dinechin, D. Wilde, S. Rajopadhye, and R. Andonov. 1996. A Regular VLSI Array for an Irregular Algorithm. In Irregular 96: Third International Workshop on Parallel Algorithms for Irregularly Structured Problems. Springer Verlag, Santa Barbara, CA, 195–200.

[7]

D. S. Hirschberg. 1975. A Linear Space Algorithm for Computing Maximal Common Subsequences. Commun. ACM 18, 6 (June 1975), 341–343. https://doi.org/10.1145/360825.360861

Digital Library

[8]

Ellis Horowitz and Sartaj Sahni. 1974. Computing Partitions with Applications to the Knapsack Problem. J. ACM 21, 2 (April 1974), 277–292. https://doi.org/10.1145/321812.321823

Digital Library

[9]

T. C. Hu. 1969. Integer Programming and Network Flows. Addison Wesley.

[10]

Fariborz Jolai, M.J. Rezaee, M. Rabbani, J. Razmi, and Pariviz Fattahi. 2007. Exact algorithm for bi-objective 0-1 knapsack problem. Appl. Math. Comput. 194, 2 (2007), 544–551. https://doi.org/10.1016/j.amc.2007.04.062

[11]

H. Kellerer, U. Pferschy, and D. Pisinger. 2004. Knapsack Problems. Springer, Berlin, Heidelberg.

[12]

S. Y. Kung. 1988. VLSI Array Processors. Prentice Hall.

[13]

S. Y. Kung, K. S. Arun, R. J. Gal-Ezer, and D. V. B. Rao. 1982. Wavefront Array Processor: Language, Architecture and Applications. IEEE Trans. Comput. C-31(1982), 1054–1066.

[14]

Saeed Maleki, Madanlal Musuvathi, and Todd Mytkowicz. 2016. Efficient Parallelization Using Rank Convergence in Dynamic Programming Algorithms. Commun. ACM 59, 10 (Sept. 2016), 85–92. https://doi.org/10.1145/2983553

Digital Library

[15]

S. Martello and P. Toth. 1990. Knapsack Problems: Algorithms and Computer Implementation. John Wiley and Sons.

Digital Library

[16]

K. Nibbelink, S. Rajopadhye, and R. McConnell. 2007. 0/1 Knapsack on Hardware: A Complete Solution. In ASAP 2007: 18th IEEE International Conference on Application-specific Systems, Architectures and Processors. Montréal, Québec, Canada.

[17]

David Pisinger. 1995. An expanding-core algorithm for the exact 0–1 knapsack problem. European Journal of Operational Research 87, 1 (1995), 175 – 187. https://doi.org/10.1016/0377-2217(94)00013-3

[18]

David Pisinger. 2005. Where Are the Hard Knapsack Problems?Comput. Oper. Res. 32, 9 (Sept. 2005), 2271–2284. https://doi.org/10.1016/j.cor.2004.03.002

Digital Library

[19]

P. Quinton, S. V. Rajopadhye, and T. Risset. 1996. Extension of the Alpha language to recurrences on sparse periodic domains. In IEEE Conference on Application-specific Systems, Architectures and Processors. Chicago, IL.

[20]

Hammad Rashid, Clara Novoa, and Apan Qasem. 2010. An Evaluation of Parallel Knapsack Algorithms on Multicore Architectures. In CSC.

[21]

Robert P. Rooderkerk and Harald J. van Heerde. 2016. Robust optimization of the 0-1 knapsack problem: Balancing risk and return in assortment optimization. European Journal of Operational Research 250, 3 (2016), 842–854. https://doi.org/10.1016/j.ejor.2015.10.014

Cited By

Mohammed ZAl-Neama M(2023)PFKP: A fast algorithm to solve knapsack problem on multi-core systemPHYSICAL MESOMECHANICS OF CONDENSED MATTER: Physical Principles of Multiscale Structure Formation and the Mechanisms of Nonlinear Behavior: MESO202210.1063/5.0157048(050042)Online publication date: 2023
https://doi.org/10.1063/5.0157048
Mohammed ZAl-Neama M(2022)An improvement of dynamic programming to solve knapsack problem using multi-core systemPROCEEDING OF THE 1ST INTERNATIONAL CONFERENCE ON ADVANCED RESEARCH IN PURE AND APPLIED SCIENCE (ICARPAS2021): Third Annual Conference of Al-Muthanna University/College of Science10.1063/5.0093571(050007)Online publication date: 2022
https://doi.org/10.1063/5.0093571

Recommendations

An alternative dynamic programming solution for the 0/1 knapsack

The 0/1 knapsack (or knapsack without repetition) has a dynamic programming solution driven by a table in which each item is consecutively considered. The problem can also be approached by generating a table in which the optimal knapsack for each ...
Dynamic-Programming-Based Inequalities for the Unbounded Integer Knapsack Problem

We propose a new hybrid approach to solve the unbounded integer knapsack problem (UKP), where valid inequalities are generated based on intermediate solutions of an equivalent forward dynamic programming formulation. These inequalities help tighten the ...
Using a Mixed Integer Programming Tool for Solving the 0-1 Quadratic Knapsack Problem

In this paper we will consider the 0-1 quadratic knapsack problem (QKP). Our purpose is to show that using a linear reformulation of this problem and a standard mixed integer programming tool, it is possible to solve the QKP efficiently in terms of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICPP '20: Proceedings of the 49th International Conference on Parallel Processing

August 2020

844 pages

ISBN:9781450388160

DOI:10.1145/3404397

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 August 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

ICPP '20

ICPP '20: 49th International Conference on Parallel Processing

August 17 - 20, 2020

AB, Edmonton, Canada

Acceptance Rates

Overall Acceptance Rate 91 of 313 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
121
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mohammed ZAl-Neama M(2023)PFKP: A fast algorithm to solve knapsack problem on multi-core systemPHYSICAL MESOMECHANICS OF CONDENSED MATTER: Physical Principles of Multiscale Structure Formation and the Mechanisms of Nonlinear Behavior: MESO202210.1063/5.0157048(050042)Online publication date: 2023
https://doi.org/10.1063/5.0157048
Mohammed ZAl-Neama M(2022)An improvement of dynamic programming to solve knapsack problem using multi-core systemPROCEEDING OF THE 1ST INTERNATIONAL CONFERENCE ON ADVANCED RESEARCH IN PURE AND APPLIED SCIENCE (ICARPAS2021): Third Annual Conference of Al-Muthanna University/College of Science10.1063/5.0093571(050007)Online publication date: 2022
https://doi.org/10.1063/5.0093571

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents