An instance of the cutting stock problem for which the rounding property does not hold (Q1080366): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0167-6377(86)90009-x / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2014510366 / rank | |||
Normal rank | |||
Latest revision as of 09:08, 30 July 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An instance of the cutting stock problem for which the rounding property does not hold |
scientific article |
Statements
An instance of the cutting stock problem for which the rounding property does not hold (English)
0 references
1986
0 references
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.
0 references
cutting stock
0 references
integer rounding property
0 references
NP-hard
0 references
