An instance of the cutting stock problem for which the rounding property does not hold (Q1080366)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An instance of the cutting stock problem for which the rounding property does not hold |
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
