An instance of the cutting stock problem for which the rounding property does not hold
type: Item
instance of: scholarly article
title: An instance of the cutting stock problem for which the rounding property does not hold
zbMATH Open document ID: 0598.90066
DOI: 10.1016/0167-6377(86)90009-X
author: Odile Marcotte
published in: Operations Research Letters
publication date: 1986-01-01T00:00:00Z
review text: We say that an instance of the cutting stock problem has the integer rounding property if its optimal value is the least integer greater than or equal to the optimal value of its linear programming relaxation. In this note we give an instance of the cutting stock problem for which the rounding property does not hold, and show that it is NP-hard to decide whether the rounding holds or not.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90B30
zbMATH DE Number: 3965819
zbMATH Keywords: cutting stock
zbMATH Keywords: integer rounding property
zbMATH Keywords: NP-hard
MaRDI profile type: Publication
cites work: Integer Rounding for Polymatroid and Branching Optimization Problems
cites work: Q4198056
cites work: The cutting stock problem and integer rounding
full work available at URL: 0167-6377(86)90009-x
OpenAlex ID: W2014510366
description: scientific article; zbMATH DE number 3965819