New reduction strategy in the biobjective knapsack problem

• Author: Malika Daoud,Djamal Chaabane
• Date: 01 November 2018
• Published date: 01 November 2018
• DOI: http://doi.org/10.1111/itor.12285

Intl. Trans. in Op. Res. 25 (2018) 1739–1762

DOI: 10.1111/itor.12285

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

New reduction strategy in the biobjective knapsack problem

Malika Daoudaand Djamal Chaabaneb

aFaculty of Mathematics, Department of Operations Research, USTHB, Bab-Ezzouar,

BP32 El-Alia, 16311 Algiers, Algeria

bLaboratory AMCD-RO

E-mail: mlk_daoud@yahoo.fr [Daoud]; chaabane_dj@yahoo.fr [Chaabane]

Received 26 January 2015; received in revised form 7 December 2015; accepted 3 March2016

Abstract

In this paper, the admissible region of a biobjective knapsack problem is our main interest. Although

the reduction of feasible region has been studied by some authors, yet more investigation has to be done

in order to deeply explore the domain before solving the problem. We propose, however, a new tech-

nique based on extreme supported efficient solutions combined with the dominance relationship between

items’ efficiency. An illustration of the algorithm by a didactic example is given and some experiments

are presented, showing the efficiency of the procedure compared to the previous techniques found in the

literature.

Keywords:efficient solution; knapsack problem; regular variable; multiple objective

1. Introduction

The biobjective knapsack problem (BOKP), is an NP-hard combinatorial optimization problem

(cf. Martello and Toth, 1990; Kellerer et al., 2004). An instance of BOKP is characterized by a

set of nitems and a knapsack capacity ω, where each item i,i=1,...,n,has a weight wiand a

distinguished profit ck

iaccording to the objective functions k=1,2. Unlike the classical knapsack

problem (KP) that optimizes one objective function, BOKP disposes of two objective functions

to be optimized simultaneously. In this case, the goal of BOKP is to determine a set of objects to

put in a bag, each object having a weight and a profit, the objects should be selected to maximize

two functions without exceeding the capacity ω. Numerous algorithms have been designed to

solve such problem, either based on implicit enumeration methods, such as dynamic programming,

branch and bound, or apply heuristic procedures, especially metaheuristics, to approximate the

set of efficient solutions that its size can grow exponentially with the number of items in the

knapsack.

C

2016 The Authors.

International Transactionsin Operational Research C

2016 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.

1740 M. Daoud and D. Chaabane / Intl. Trans.in Op. Res. 25 (2018) 1739–1762

This latter is a motivation for exploring the information in the admissible region and finding a

simple technique that reduces as much as possible the admissible domain.

Mathematically, BOKP can be stated as follows:

(BOKP)

⎧

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎩

max(Zk)=

n



i=1

ck

ixi,k=1,2

n



i=1

wixi≤ω

xi∈{0,1},i=1,...,n,

(1)

where xiis a decision variable, equals to 1 if the item iis in the knapsack and 0 otherwise. For the

rest of the paper and without loss of generality, we assume that

1. All input data ω, ci,andwi,fori=1,...,n, are nonnegative integers.

2. n

i=1wi>ω, in order to avoid trivial solutions.

2. Related works

BOKP belongs to the well-known knapsack family(cf. Kellerer et al., 2004) that represents a natural

combinatorial optimization problems. BOKP is a more complex variant of the classical NP-hard

single object KP and has a wide range of applications such as capital budgeting (cf. Dyer et al.,

1992) and media selection (cf. Rosenblatt and Sinuany-Stern, 1989).

As far as we know, many papers addressing the BOKP are available, as well as the meth-

ods devoted to the classical single-objective knapsack. Among existing papers tackling the

BOKP, a two-phase resolution search was proposed in Vis´

ee et al. (1998). The first phase pro-

vides the set of supported efficient solutions by solving a weighted sum objective functions

and the second phase, with its several versions, is used to find the nonsupported efficient solu-

tions.

Przybylski (2006) generalized the previous method with three objectives using the ranking

method for searching for the efficient solutions in the second phase. In a such method, the sec-

ond phase is very important since the nonsupported efficient solutions are to be found. The

reason why many researchers have spent considerable time to find methods to solve in rea-

sonable CPU-time. Dichotomy, ranking, implicit enumeration, and other techniques are often

used.

The presence of more than one objective makes it more difficult. Moreover, large-scale optimiza-

tion problems are time consuming, therefore reducing their size is necessary.

Dantzig (1957) showed that an optimal solution for the continuous {0,1}-KP could be ob-

tained as follows: the items are sorted according to their nonincreasing profit to weight ratios,

and these items are included one by one without exceeding the knapsack capacity. In the end,

only one item cannot be completely included in the KP; it is called the break item (critical

item).

C

2016 The Authors.

International Transactionsin Operational Research C

2016 International Federation of OperationalResearch Societies