An instance of the cutting stock problem for which the rounding property does not hold (Q1080366): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| 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 | |||
| 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 | |||
| links / mardi / name | links / mardi / name | ||
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
