An integer linear optimization model to the compartmentalized knapsack problem

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 articl...

Full description

Saved in:
Bibliographic Details
Published in:International transactions in operational research 2019-09, Vol.26 (5), p.1698-1717
Main Authors: Inarejos, Osvaldo, Hoto, Robinson, Maculan, Nelson
Format: Article
Language:English
Subjects:
compartmentalized knapsack problem
Cutting
Decomposition
Discounts
discrete optimization
Heuristic
Knapsack problem
linear optimization
Mathematical models
Operations research
Optimization
Optimization models
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 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.
ISSN:0969-6016
1475-3995
DOI:10.1111/itor.12490