Premium
Improved dynamic programming and approximation results for the knapsack problem with setups
Author(s) -
Pferschy Ulrich,
Scatamacchia Rosario
Publication year - 2018
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12381
Subject(s) - knapsack problem , solver , continuous knapsack problem , change making problem , mathematical optimization , integer programming , dynamic programming , computer science , polynomial time approximation scheme , approximation algorithm , cutting stock problem , linear programming , mathematics , optimization problem
In this paper, we consider the 0–1 knapsack problem with setups. Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm that performs much better than a previous dynamic program and turns out to be also a valid alternative to an exact approach based on the use of an Integer Linear Programming (ILP) solver. Then we present a general inapproximability result. Furthermore, we investigate several relevant special cases that still permit fully polynomial‐time approximation schemes and others where the problem remains hard to approximate.