A strong integer linear optimization model to the compartmentalized knapsack problem

• Date: 01 September 2019
• Author: J.M. Valério de Carvalho,John J. Quiroga‐Orozco,Robinson S. V. Hoto
• Published date: 01 September 2019
• DOI: http://doi.org/10.1111/itor.12639

Intl. Trans. in Op. Res. 26 (2019) 1633–1654

DOI: 10.1111/itor.12639

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A strong integer linear optimization model to the

compartmentalized knapsack problem

John J. Quiroga-Orozcoa,J.M.Val

´

erio de Carvalhoband Robinson S. V. Hotoa

aDepartamento de Matem´

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

bDepartamento de Produc¸˜

ao e Sistemas, Universidade do Minho, Campus Gualtar, Braga4710-057, Portugal

E-mail: jjqojj@outlook.com [Quiroga-Orozco]; vc@dps.uminho.pt[Val´

erio de Carvalho]; hoto@uel.br [V. Hoto]

Received 22 February2018; received in revised form 23 January 2019; accepted 24 January2019

Abstract

The compartmentalized knapsack problem (CKP) is a relatively new type of problem with a wide appli-

cation in industrial processes, arising, for instance, in the case of cutting steel coils in two phases in the

metallurgical industry.

In the literature, there are two mathematical formulations for the CKP: a classical formulation, which is a

nonlinear integer programming (IP) model, and a recent (linear) IP formulation, obtained by discretizing the

compartments that can be builtfor each class of items; the latter is an important contribution, because it makes

the problem amenable to solution by mixed-integer linear programming tools. Combinatorial enumeration

algorithms and several pseudo-polynomial decomposition heuristics were also developed for the CKP.

This paper presents a new model for the exact solution of the CKP, denoted as the strong integer linear

model, derived from the (linear) IP formulation by strengthening data, reducing symmetry, and lifting, and

also a new pseudo-polynomial heuristic, the heuristic of the pkstrong capacities. Computationalexperiments

are presented with a large set of instances that show the advantage of the new approaches. The strong model

solves the CKP exactly more than seventimes faster, and the new heuristic is more efficient, presenting a good

balance in the terms of effectiveness.

Keywords: compartmentalized knapsack problem; linear strong model optimization; discrete optimization; linear pro-

gramming

1. Introduction

Consider a knapsack with capacity Land set of items of ntypes,indexed by iin a set N={1,...,n}.

Each item of type i∈Nhasaweight(pi) and a utility (ui). The classic knapsack problem consists

of determining which items and how many (depending on the demand for each item) should fill the

knapsack, in order to obtain the maximum utility, respecting the capacity of the knapsack. Now

define a variation in this classic problem: classify the items under some criterion and divide them

C

2019 The Authors.

International Transactionsin Operational Research C

2019 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.

1634 J.J. Quiroga-Orozco et al. / Intl. Trans.in Op. Res. 26 (2019) 1633–1654

into qdisjoint classes, that is, make a partition of the set Nin N=q

k=1Nkwith q

k=1Nk=∅,and

consider that filling the knapsack with items i,j∈Nis subject to a condition: items of different

classes cannot be mixed in the knapsack, that is, items i∈Nsand j∈Ngcannot be inserted

“together” into the knapsack unless s=g, with s,g∈C={1,2,...,q},whereCis the set of classes,

or they are inserted into different compartments. In fact, in order to be able to insert items from

differentclasses into the knapsack, we need to construct, inside the knapsack, different compartments,

each grouping items of the same class.

These compartments are not predetermined, they are defined by the items to insert into the

knapsack. Now, we can present an informal definition of the problem of the compartmentalized

knapsack in its unrestricted version. The compartmentalized knapsack problem (CKP) consists of

finding the capacities of the compartments created foreach class k=1,...,q(which are determined

by the items inside them) aiming at obtaining the maximum possible utility.

This problem arises in industrial metallurgical practice when planning cutting patterns for the

two-stage process of cutting steel coils. Here, the items correspond to the ribbon coils that are

grouped by their thickness, thus defining the classes of the items. These ribbons are obtained (after

two stages) by cutting the steel coils available in stock, which correspond to the knapsack to be

filled. The steel coils are slit in a first cutting process, producing subcoils with the same thickness as

the original coil. Then, in a process called “cold rolling,” each subcoil thickness is reduced in order

to match the desired thickness for the type ofitems that will be producedlater. These subcoils can be

seen as the compartments of the knapsack. Finally, the subcoils are submitted to a second cutting

process to obtain the steel ribbons with the final size. A representation of the process is shown in

Fig. 1.

The CKP study is relatively new. In the following, some theoretical advances and the current state

of the art are presented. CKP was treated implicitly in its restricted case in works such as Haessler

(1979), Ferreira et al. (1990), Pereira (1993), and Val´

erio de Carvalho and Rodrigues (1994, 1995).

The first mathematical elements in the approach and the definition of the CKP are found in Hoto

(1996), who later formulated an integer nonlinear optimization model for the unrestricted version

of the problem, in his PhD thesis, Hoto (2001), which, in addition to presenting the CKP model,

makes a detailed study of the application of the CKP to the steel coil cutting problem (SCCP)

with solution approaches such as the exact compartmentalization algorithm called COMPEX

and a compartmentalization heuristic named COMPMT, in which bounds from Martello and

Toth (1990) are used. It also defines the 0 −1 CKP and describes a branch-and-bound solution

method.

Marques and Arenales (2002) studied in depth the compartmentalized knapsack problem in the

restricted case (CKPR), presenting a model and heuristics, such as the decomposition heuristic, the

best compartment heuristics, and the “z” best compartments heuristic. In Marques and Arenales

(2007), the heuristic of “W” capacities shows better computational results when compared to

the heuristics presented in Marques and Arenales (2002). In addition, in the same work, a linear

relaxation of the CKP was derived, providing upper bounds for the problem.

In Hoto et al. (2003), an application of the CKP to problems of cuts of coils of steel (PCCS) is

presented, and in Hoto et al. (2007) the CKP is solved by cutting steel rolls in two unidimensional

phases.

A first approach to the CKP as a linear problem was exposed in Cruz (2010), with a new

formulation of the objective function and its constraints, along with the presentation of retro feed

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies