An integer linear optimization model to the compartmentalized knapsack problem

• Author: Nelson Maculan,Robinson Hoto,Osvaldo Inarejos
• Date: 01 September 2019
• DOI: http://doi.org/10.1111/itor.12490
• Published date: 01 September 2019

Intl. Trans. in Op. Res. 26 (2019) 1698–1717

DOI: 10.1111/itor.12490

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

An integer linear optimization model to the compartmentalized

knapsack problem

Osvaldo Inarejosa, Robinson Hotoaand Nelson Maculanb

aDepartamento de Matem´

atica, Universidade Estadual de Londrina, Rodovia Celso GarciaCid, Km 380, Londrina, Brazil

bDepartamento de Matem´

atica, Universidade Federaldo Rio de Janeiro, Av. Pedro Calmon, 550, Rio de Janeiro,Brazil

E-mail: inarejos@uel.br [Inarejos]; hoto@uel.br [Hoto]; maculan@cos.ufrj.br [Maculan]

Received 22 June2016; received in revised form 1 October 2017; accepted 26 October 2017

Abstract

The compartmentalized knapsack problem arose from two-phased cutting stock problems, especially with

steel roll cutting. In its original formulation, it refers to an integer nonlinear optimization model, which,

up to now, has been solved through decomposition heuristics. The objective of this article is to show that

the constrained compartmentalized knapsack problem has a linear optimization model. Therefore, we have

considered the original nonlinear model and propose a linear model for the problem, demonstrating their

equivalence. We also propose a new decomposition heuristic and perform numerical tests to verify the limits

of the proposed model and the quality of the heuristic solutions.

Keywords:compartmentaliz ed knapsackproblem; discrete optimization; linear optimization

1. Introduction

Knapsack problems are generally simple to be understood and of greater applicability, but not

always of easy resolution. In general, these problems involve choosing items to be placed inside one

or more knapsacks in an attempt to maximize a utility function (Martello and Toth, 1990; Kellerer

et al., 2013).

The first reference to the knapsack problem was probably made by Dantzig (1957), who gave the

following example: a person plans to go camping but wants to travel light, carrying no more than

70 lb of different items such as bed linen, cans of food, etc. Each item has a weight and a utility.

The objective of the person is to take with him/her items in a knapsack that are “the most useful

possible” (linear sum of the selected item utilities). Obviously, if the set of item weighs less than 70

lb, the choice is trivial.

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies

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

USA.

O. Inarejos et al. / Intl. Trans. in Op. Res. 26 (2019) 1698–1717 1699

One of the most well-known examples of a knapsack problem application is the Simplex Method

with columns generation to solve the unidimensional cutting stock problem (Gilmoreand Gomory,

1961).

There are variations of the classic knapsack problem, and some of them can be seen in Martello

and Toth (1990) and Kellerer et al. (2013). In this article, we will deal with a variation in which

it is necessary to construct compartments inside a knapsack. Knapsack compartmentalization

(Hoto and Arenales, 1996) occurs when the items must be grouped inside a knapsack according

to affinities. For instance, when we do not want to mix drugs, tools, and food inside a knapsack,

requiring the construction of distinct compartments, where items of the same nature will be

allocated. This particularity induces a mathematical partition in the set of items (classes of

related items). The motivation behind this knapsack version, whose original mathematical model

(Hoto, 2001) is nonlinear, came around from the need to model “cutting patterns” in two phases

(Haessler, 1979; Ferreira et al., 1990; Carvalho and Rodrigues, 1994; Zak, 2002; Correia et al.,

2004).

Possibly, the most similar problem to the compartmentalized knapsack found in the literature

is the nested knapsack problem (Johnston and Khan, 1995) applied to the production of optical

fiber cables. In this problem, the “nest” has constant capacity, unlike compartmentalized knapsack

problem where the capacity of compartments are variable.

Hoto (2001) described the 0–1 compartmentalized knapsack problem, for which he calcu-

lated bounds and determined pruning criteria, thus proposing a branch-and-bound algorithm

to solve it. Marques and Arenales (2002) introduced three new heuristics, with emphasis on

the “Z” best compartment heuristic. Hoto et al. (2007) presented, in addition to a concise

formulation of the compartmentalized knapsack problem, an exact compartmentalization

algorithm (for small instances) and some heuristic procedures. Marques and Arenales (2007)

presented the “W” capacity heuristic and reported on its best performance over the “Z” best

compartment heuristic. In the same work, a linear relaxation for the compartmentalized knapsack

problem is found, whose solution brought an upper bound. Hoto et al. (2010) propose new

strategies for resolving the constrained compartmentalized knapsack problem with column

generation.

In Le˜

ao et al. (2011), the upper bound given by the Marques and Arenales relaxation to

verify the optimality of the solution by some heuristics is adopted. Another upper bound

discussed by Le˜

ao et al. (2011) uses the column generation method to solve the knapsack

compartmentalization problem, where, at each simplex interaction, some subproblems (one

for each class) are calculated. In terms of computational time, this heuristics was a bit faster

than the problem relaxation made by Marques and Arenales (2007); however, the upper bound

was a little higher than that for most tested instances. A hybrid heuristic is also presented

by Le ˜

ao et al. (2011), exploring the ideas of the “Z” best compartment and “W” capacity

heuristics.

In Cruz (2010), tests based on the idea of eliminating the nonlinearity of the original knapsack

compartmentalization model are presented and, in Le˜

ao et al. (2011) these ideas are used to compare

heuristics results. These simulations led us to conduct the present research, since neither of the two

works came to prove that a compartmentalized knapsack has, in fact, an integer linear model,

and the present uncertainty about the equivalence of the models discourages the resolution of this

problem through a linear model.

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies