Sensitivity analysis of the setup knapsack problem to perturbation of arbitrary profits or weights

• Author: Mhand Hifi,Hedi Mhalla,Ferhan Al‐Maliky
• Date: 01 March 2018
• DOI: http://doi.org/10.1111/itor.12373
• Published date: 01 March 2018

Intl. Trans. in Op. Res. 25 (2018) 637–666

DOI: 10.1111/itor.12373

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Sensitivity analysis of the setup knapsack problem to

perturbation of arbitrary profits or weights

Ferhan Al-Malikya, Mhand Hifiaand Hedi Mhallab

aLaboratoire EPROAD – EA 4669, UFR des Sciences, Universit´

e de Picardie Jules Verne, Amiens, France

bDepartment of Mathematics and Statistics, American University of the Middle East, Eqaila, Kuwait

E-mail: ferhan.al.maliky@u-picardie.fr [Al-Maliky]; hifi@u-picardie.fr[Hifi]; hedi.mhalla@aum.edu.kw [Mhalla]

Received 10 October 2015; receivedin revised form 12 September 2016; accepted 14 October 2016

Abstract

The setup knapsack problem can be viewed as a more complexversion of the well-known classical knapsack

problem. An instance of such a problem may be defined by a set Nof nitems that is divided into mdifferent

classes Fi,1≤i≤m.For each class, only one item is considered as a setup item. The aim of the problem is

to pack a subset of items in a knapsack of a predefined capacity that maximizes an objective function. In this

paper, we analyze the sensitivity of an optimal solution depending on the variation of the profits or weights

of arbitrary items. The optimality of the solution at hand is guaranteedby establishing the sensitivity interval

that is characterized by both lower and upper values (called limits). First, two cases are distinguished when

varying the profits: perturbation of the profit of an item (either ordinary or setup item) and, variation of the

profits of a couple of items containing both setup and ordinary items belonging to the same class. Second,

two cases are studied, where the perturbation concerns the weights: the variation is relied on the weight of

an item and, the case of the variation of the weights of a subset of items. The established results are first

illustrated throughout a didactic example, where both approximate and exact methods are used for analyzing

the quality of the proposed results. Finally, an extended experimental part is proposed in order to evaluate

the effectiveness of the proposed limits.

Keywords:approximation; knapsack; optimality; optimization; sensitivity analysis

1. Introduction

Most problems assume that the parameters are deterministic constants, whereas in many real-

world applications, these parameters are generally unknown. Their declared values are very

coarse approximations and in such cases, finding an optimal solution to the problem at hand

becomes insufficient. Moreover, solving the optimization problems is computationally very expen-

sive and avoiding its resolution whenever a viable alternative is available becomes interesting; in

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.

638 F. Al-Maliky et al. / Intl. Trans. in Op. Res. 25 (2018) 637–666

particular, when only some parameters of the problem at hand change. Sensitivity analysis can

provide such an alternative by using the solution of the original instance to solve the perturbed

problem.

Several approacheshave been proposed in the literature todeal with optimization problems under

uncertainty and when the problem parameters are subject to perturbations. These approaches may

be categorized as follows: stochastic optimization,robust optimization, and sensitivity analysis.The

stochastic optimization assumes that uncertain input parameters have probabilisticdescriptions (cf.,

Dantzig, 1955; Birge and Louveaux, 1997; Pr´

ekopa, 1995). In practice,the nondeter ministic param-

eters’ distributions are usually not availableand so robust optimization and sensitivity analysis seem

to be more adequate for tackling certain problems. In robust optimization, different configurations

can be considered and the decision maker tries to reach a solution with a certain quality (generally,

such a quality is based on a specific measure of quality), irrespective of the considered solution or

any realization of the uncertain parameters in a givenset (cf., Bertsimas and Sim, 2003; Ben-Tal and

Nemirovski, 2002). In other words, in robustoptimization, one tries to optimize the worst case. The

sensitivity analysis can be viewed as a complementary approach that tries to propose the limits of

variability of one or more parameters of the problem without altering the optimal solution at hand

(the optimal solution remains unchanged). On the one hand, such an approach may be useful when

some parameters have an unpredictable behavior. On the other hand, a comparative study between

the confidence intervals and sensitivity intervals of parameters can lead to the stabilization of the

optimal solution, in particular when the distribution of each parameter is well known.

This paper deals with the sensitivity analysis of an optimal solution of the “setup knapsack

problem,” namely, SKP (cf., McLay and Jacobson, 2007a), to perturbation of arbitrary profit

or weight coefficients of items. The sensitivity interval can be viewed as the interval, charac-

terized by lower and upper limits, that guarantees the stability of an optimal solution at hand

to perturbations of the profit or weight of given items. In other words, it represents the inter-

val guarantying that the structure of the optimal solution remains unchanged in the perturbed

problem.

SKP, also called bounded setup knapsack problem in McLay and Jacobson (2007a), can be

viewed as a variant of the well-known classical knapsack problem (cf., Kellerer et al., 2004). An

instance of SKP consists of packing a subset of mitem types in a knapsack of capacity c,where

each item type has a profit pi,aweightwi, and a (demand) bound ni≥1, for i=1,...,m.Each

item type iis associated to a setup item and is characterized by its value uiand weight si.Avariety

of practical applications can be modeled as SKP, where setup’s profit values may be real numbers

that can be negative (cf., Yang and Bulfin, 2009) or nonnegative (cf., McLay and Jacobson, 2007a).

It means that the profit can be added to or subtracted from the objective function, which is based

on the nature of the problem being studied. On the one hand, in cases where the objective function

represents the profitability of a workers team, the setup item profit (which can be considered as the

profitability brought by the team leader) can be added to the team profitability. On the other hand,

if the objective function represents the benefit generated by delivering orders, then cost related to

the delivery truck should be subtracted. Herein, we consider the case where the setup valueis added

to the objective function if any copies of that item type are included in the knapsack. The integer

decision variables xipoints out how many items of type iare included in the knapsack, and the

binary decision variable zipoints out if anycopies of item type iis added to the knapsack. Formally,

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies