A dynamic programming algorithm for the Knapsack Problem with Setup

Khalil Chebil; Mahdi Khemakhem

doi:10.1016/j.cor.2015.05.005

A dynamic programming algorithm for the Knapsack Problem with Setup

Khalil Chebil, Mahdi Khemakhem

University of Sfax

Research output: Contribution to journal › Article › peer-review

38 Scopus citations

Abstract

The Knapsack Problem with Setup (KPS) is a generalization of the classical Knapsack problem (KP), where items are divided into families. An individual item can be selected only if a setup is incurred for the family to which it belongs. This paper provides a dynamic programming (DP) algorithm for the KPS that produces optimal solutions in pseudo-polynomial time. In order to reduce the storage requirements of the algorithm, we adopt a new technique that consists in converting a KPS solution to an integer index. Computational experiments on randomly generated test problems show the efficiency of the DP algorithm compared to the ILOG's commercial product CPLEX 12.5.

Original language	English
Pages (from-to)	40-50
Number of pages	11
Journal	Computers and Operations Research
Volume	64
DOIs	https://doi.org/10.1016/j.cor.2015.05.005
State	Published - 8 Jun 2015
Externally published	Yes

Keywords

Combination
Dynamic programming
Knapsack problems
Production planning
Setup

Access to Document

10.1016/j.cor.2015.05.005

Cite this

@article{a8634b50bb994ea092f3b34183381eb6,

title = "A dynamic programming algorithm for the Knapsack Problem with Setup",

abstract = "The Knapsack Problem with Setup (KPS) is a generalization of the classical Knapsack problem (KP), where items are divided into families. An individual item can be selected only if a setup is incurred for the family to which it belongs. This paper provides a dynamic programming (DP) algorithm for the KPS that produces optimal solutions in pseudo-polynomial time. In order to reduce the storage requirements of the algorithm, we adopt a new technique that consists in converting a KPS solution to an integer index. Computational experiments on randomly generated test problems show the efficiency of the DP algorithm compared to the ILOG's commercial product CPLEX 12.5.",

keywords = "Combination, Dynamic programming, Knapsack problems, Production planning, Setup",

author = "Khalil Chebil and Mahdi Khemakhem",

year = "2015",

month = jun,

day = "8",

doi = "10.1016/j.cor.2015.05.005",

language = "English",

volume = "64",

pages = "40--50",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

}

TY - JOUR

T1 - A dynamic programming algorithm for the Knapsack Problem with Setup

AU - Chebil, Khalil

AU - Khemakhem, Mahdi

PY - 2015/6/8

Y1 - 2015/6/8

N2 - The Knapsack Problem with Setup (KPS) is a generalization of the classical Knapsack problem (KP), where items are divided into families. An individual item can be selected only if a setup is incurred for the family to which it belongs. This paper provides a dynamic programming (DP) algorithm for the KPS that produces optimal solutions in pseudo-polynomial time. In order to reduce the storage requirements of the algorithm, we adopt a new technique that consists in converting a KPS solution to an integer index. Computational experiments on randomly generated test problems show the efficiency of the DP algorithm compared to the ILOG's commercial product CPLEX 12.5.

AB - The Knapsack Problem with Setup (KPS) is a generalization of the classical Knapsack problem (KP), where items are divided into families. An individual item can be selected only if a setup is incurred for the family to which it belongs. This paper provides a dynamic programming (DP) algorithm for the KPS that produces optimal solutions in pseudo-polynomial time. In order to reduce the storage requirements of the algorithm, we adopt a new technique that consists in converting a KPS solution to an integer index. Computational experiments on randomly generated test problems show the efficiency of the DP algorithm compared to the ILOG's commercial product CPLEX 12.5.

KW - Combination

KW - Dynamic programming

KW - Knapsack problems

KW - Production planning

KW - Setup

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

U2 - 10.1016/j.cor.2015.05.005

DO - 10.1016/j.cor.2015.05.005

M3 - Article

AN - SCOPUS:84930635336

SN - 0305-0548

VL - 64

SP - 40

EP - 50

JO - Computers and Operations Research

JF - Computers and Operations Research

ER -

A dynamic programming algorithm for the Knapsack Problem with Setup

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this