TY - JOUR

T1 - Integer knapsack problems with set-up weights

AU - McLay, Laura A.

AU - Jacobson, Sheldon H.

N1 - Funding Information:
Acknowledgements This research has been supported in part by the National Science Foundation (DMI-0114499) and the Air Force Office of Scientific Research (FA9550-04-1-0110). The first author was also supported in part by the program in Arms Control, Disarmament, and International Security (ACDIS) at the University of Illinois. The authors wish to thank the Associate Editor and two anonymous referees for their thorough review and feedback on an earlier version of the paper. The authors would also like to thank Professor Edward C. Sewell of Southern Illinois University, Edwardsville for his insight on the dynamic programming models for IKPSW, and Professor Diego Klabjan of the University of Illinois at Urbana-Champaign for his comments and suggestions on an earlier version of this manuscript.
Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2007/5

Y1 - 2007/5

N2 - The Integer Knapsack Problem with Set-up Weights (IKPSW) is a generalization of the classical Integer Knapsack Problem (IKP), where each item type has a set-up weight that is added to the knapsack if any copies of the item type are in the knapsack solution. The k-item IKPSW (kIKPSW) is also considered, where a cardinality constraint imposes a value k on the total number of items in the knapsack solution. IKPSW and kIKPSW have applications in the area of aviation security. This paper provides dynamic programming algorithms for each problem that produce optimal solutions in pseudo-polynomial time. Moreover, four heuristics are presented that provide approximate solutions to IKPSW and kIKPSW. For each problem, a Greedy heuristic is presented that produces solutions within a factor of 1/2 of the optimal solution value, and a fully polynomial time approximation scheme (FPTAS) is presented that produces solutions within a factor of ε of the optimal solution value. The FPTAS for IKPSW has time and space requirements of O(nlog∈n+n/ε 2+1/ε 3) and O(1/ε 2), respectively, and the FPTAS for kIKPSW has time and space requirements of O(kn 2/ε 3) and O(k/ε 2), respectively.

AB - The Integer Knapsack Problem with Set-up Weights (IKPSW) is a generalization of the classical Integer Knapsack Problem (IKP), where each item type has a set-up weight that is added to the knapsack if any copies of the item type are in the knapsack solution. The k-item IKPSW (kIKPSW) is also considered, where a cardinality constraint imposes a value k on the total number of items in the knapsack solution. IKPSW and kIKPSW have applications in the area of aviation security. This paper provides dynamic programming algorithms for each problem that produce optimal solutions in pseudo-polynomial time. Moreover, four heuristics are presented that provide approximate solutions to IKPSW and kIKPSW. For each problem, a Greedy heuristic is presented that produces solutions within a factor of 1/2 of the optimal solution value, and a fully polynomial time approximation scheme (FPTAS) is presented that produces solutions within a factor of ε of the optimal solution value. The FPTAS for IKPSW has time and space requirements of O(nlog∈n+n/ε 2+1/ε 3) and O(1/ε 2), respectively, and the FPTAS for kIKPSW has time and space requirements of O(kn 2/ε 3) and O(k/ε 2), respectively.

KW - Fully polynomial-time approximation schemes

KW - Heuristics

KW - Knapsack problem

UR - http://www.scopus.com/inward/record.url?scp=34047179030&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34047179030&partnerID=8YFLogxK

U2 - 10.1007/s10589-007-9020-5

DO - 10.1007/s10589-007-9020-5

M3 - Article

AN - SCOPUS:34047179030

VL - 37

SP - 35

EP - 47

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

SN - 0926-6003

IS - 1

ER -