Improved dynamic programming and approximation results for the knapsack problem with setups

• Author: Rosario Scatamacchia,Ulrich Pferschy
• Published date: 01 March 2018
• DOI: http://doi.org/10.1111/itor.12381
• Date: 01 March 2018

Intl. Trans. in Op. Res. 25 (2018) 667–682

DOI: 10.1111/itor.12381

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Improved dynamic programming and approximation results

for the knapsack problem with setups

Ulrich Pferschyaand Rosario Scatamacchiab

aDepartment of Statistics and Operations Research, University of Graz, Universitaetsstrasse 15, 8010, Graz, Austria

bDipartimento di Automatica e Informatica, Politecnicodi Torino, Corso Duca degli Abruzzi 24, 10129, Torino, Italy

E-mail: pferschy@uni-graz.at [Pferschy]; rosario.scatamacchia@polito.it [Scatamacchia]

Received 13 July2016; received in revised form 31 October 2016; accepted 13 November 2016

Abstract

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 wellas a setup resource consumption. Weintroduce a

new dynamic programmingalgorithm 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 wepresent 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.

Keywords:0–1 knapsack problem with setups; approximation scheme; dynamic programming

1. Introduction

The 0–1 knapsack problem with setups (KPS) is a generalization of the standard 0–1 knapsack

problem (KP) where items belong to disjoint families and can be selected only if the corresponding

family is activated. The activation of a family induces setup costs and a consumption of resource.

Thus, including items of any family requires the activation of the family, which decreases the

objective function and also reduces the available knapsack capacity.

KPS has applications of interest for resource-allocation problems characterized by classes of

elements, for example in make-to-order production contexts or concerning the management of

different product categories (see, e.g., Chebil and Khemakhem, 2015). KPS was introduced in

Chajakis and Guignard (1994) where the case with either positive or negative setup costs and profits

of items is considered. The authors propose a pseudo-polynomial time dynamic programming

approach and a two-phaseenumerative scheme. Considering the pseudo-polynomialtime algorithm

of Chajakis and Guignard (1994) and the fact that KP is a special case of KPS, namely, in the case

where there is only one family, we can statethat KPS is weakly NP-hard. In Yang and Bulfin (2009),

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

668 U. Pferschy and R. Scatamacchia / Intl. Trans. in Op. Res.25 (2018) 667–682

a branch-and-bound algorithm is proposed for KPS. The algorithm turns out to solve instances

with up to 10,000 variables. Nonetheless, the approach does not solve several large instances due to

memory overflow.In Chebil and Khemakhem (2015), an improved dynamic programmingalgorithm

is proposed. The algorithm outperforms the solver CPLEX 12.5 applied to the integer linear

programming model of KPS and handles instances with up to 10,000 items. These instances turn

out to be more challenging than the ones proposed in Yang and Bulfin (2009).

The current state-of-the-art approach for KPS is an exact method proposed in Della Croce

et al. (2017). The approach relies on an effective exploration of the solution space by exploiting

the presence of two levels of variables. It manages to solve to optimality all instances with up to

100,000 variables with limited computational effort.

Also, a number of problems closely related to KPS were treated in the literature. In Caserta

et al. (2008), a metaheuristic-based algorithm (cross entropy) is proposedin order to deal with KPS

with more than one copy per item (cf. the bounded KP). In Altay et al. (2008), a variant of KPS

with fractional items is considered and the authors present both heuristic methods and an exact

algorithm based on cross decomposition techniques. In Akinc (2004), the special case of KPS with

no setup capacity consumptions but only setup costs is considered. For this so-called fixed-charge

KP, the author proposes both heuristic procedures and an exact branch-and-bound algorithm. A

valuable overview of the literature of various KPS variantsis provided in Michel et al. (2009), which

also devises a branch-and-bound scheme.

The contribution of this paper is twofold: First we introduce a new improved dynamic program-

ming algorithm motivated by the connection of KPS to a KP with precedence constraints. This

pseudo-polynomial algorithm can be stated with less involved notation and turns out to outper-

form the recent dynamic programming approach by Chebil and Khemakhem (2015). Moreover, it

performs comparablyto the exact approach proposed in Della Croce et al. (2017) but avoids the use

of an Integer Linear Programming (ILP) solver.

Second, we provide further insights into the problem and derive a number of approximation

results. More precisely, we show that no polynomial approximation algorithm can exist for the

problem in the general case unless P=NP and we investigate several conditions for deriving fully

polynomial-time approximation schemes (FPTASs). Thus, we make progress in characterizing the

borderline between nonapproximability and existence of approximation schemes.

The paper is organized as follows. In Section 2, the linear programming formulation of the

problem is introduced. The new dynamic programming algorithm is introduced and computational

results are presented in Section 3. Approximation results are discussed in Section 4. Section 5 draws

some conclusions.

2. Notation and problem formulation

In KPS, a set of Nfamilies of items is given together with a knapsack with capacity b. Each family

i∈{1,...,N}has niitems, a nonnegative setup cost represented by an integer fiand a nonnegative

setup capacity consumption denoted by an integer di. The total number of items is denoted by

n:=N

i=1ni.Eachitem j∈{1,...,ni}of a family ihas a nonnegative integer profit pij and a

nonnegative integer capacity consumption wij. The problem calls for maximizing the total profit

of the selected items minus the fixed costs of the selected families without exceeding the knapsack

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies