Titlebar

Export bibliographic data
Literature by the same author
plus on the publication server
plus at Google Scholar

 

Minimal proper non-IRUP instances of the one-dimensional Cutting Stock Problem

Title data

Kartak, Vadim ; Kurz, Sascha ; Scheithauer, Guntram ; Ripatti, Artem:
Minimal proper non-IRUP instances of the one-dimensional Cutting Stock Problem.
In: Discrete Applied Mathematics. Vol. 187 (May 2015) . - pp. 120-129.
ISSN 0166-218x
DOI: https://doi.org/10.1016/j.dam.2015.02.020

Abstract in another language

We consider the well-known one dimensional cutting stock problem (1CSP). Based on the pattern structure of the classical ILP formulation of Gilmore and Gomory, we can decompose the infinite set of 1CSP instances, with a fixed demand n, into a finite number of equivalence classes. We show up a strong relation to weighted simple games. Studying the integer round-up property we computationally show that all 1CSP instances with n ≤ 9 are proper
IRUP, while we give examples of a proper non-IRUP instances with n = 10. A gap larger than 1 occurs for n = 11. The worst known gap is raised from 1.003 to 1.0625. The used algorithmic approaches are based on exhaustive enumeration
and integer linear programming. Additionally we give some theoretical bounds showing that all 1CSP instances with some specific parameters have the proper IRUP.

Further data

Item Type: Article in a journal
Refereed: Yes
Keywords: bin packing problem; cutting stock problem; integer round-up property; equivalence of instances; branch and bound method; linear programming; weighted simple games
Subject classification: MSC: 90C10; 90B80; 90C27; 90C06; 91B12
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics in Economy
Profile Fields > Emerging Fields > Governance and Responsibility
Faculties
Profile Fields
Profile Fields > Emerging Fields
Result of work at the UBT: Yes
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
500 Science > 510 Mathematics
Date Deposited: 10 Apr 2015 09:47
Last Modified: 10 Apr 2015 09:47
URI: https://eref.uni-bayreuth.de/id/eprint/10042