A strong integer linear optimization model to the compartmentalized knapsack problem

The compartmentalized knapsack problem (CKP) is a relatively new type of problem with a wide application 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...

Full description

Saved in:
Bibliographic Details
Published in:International transactions in operational research 2019-09, Vol.26 (5), p.1633-1654
Main Authors: Quiroga‐Orozco, John J., Valério de Carvalho, J.M., V. Hoto, Robinson S.
Format: Article
Language:English
Subjects:
Algorithms
Coils
Combinatorial analysis
compartmentalized knapsack problem
discrete optimization
Enumeration
Formulations
Heuristic
Industrial applications
Integer programming
Knapsack problem
Linear programming
linear strong model optimization
Mathematical analysis
Metallurgy
Operations research
Optimization models
Polynomials
Solution strengthening
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The compartmentalized knapsack problem (CKP) is a relatively new type of problem with a wide application 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 built for 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 pk strong capacities. Computational experiments 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 seven times faster, and the new heuristic is more efficient, presenting a good balance in the terms of effectiveness.
ISSN:0969-6016
1475-3995
DOI:10.1111/itor.12639