Premium
An integer linear optimization model to the compartmentalized knapsack problem
Author(s) -
Inarejos Osvaldo,
Hoto Robinson,
Maculan Nelson
Publication year - 2019
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12490
Subject(s) - knapsack problem , mathematical optimization , continuous knapsack problem , cutting stock problem , heuristics , heuristic , integer programming , computer science , nonlinear system , generalized assignment problem , optimization problem , equivalence (formal languages) , decomposition , integer (computer science) , mathematics , discrete mathematics , biology , programming language , ecology , physics , quantum mechanics
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.