An instance of the cutting stock problem for which the rounding property does not hold (Q1080366): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Integer Rounding for Polymatroid and Branching Optimization Problems / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4198056 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The cutting stock problem and integer rounding / rank | |||
Normal rank | |||
Revision as of 14:28, 17 June 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
