Literatur vom gleichen Autor/der gleichen Autor*in
plus bei Google Scholar

Bibliografische Daten exportieren
 

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

Titelangaben

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

Abstract

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.

Weitere Angaben

Publikationsform: Artikel in einer Zeitschrift
Begutachteter Beitrag: Ja
Keywords: bin packing problem; cutting stock problem; integer round-up property; equivalence of instances; branch and bound method; linear programming; weighted simple games
Fachklassifikationen: MSC: 90C10; 90B80; 90C27; 90C06; 91B12
Institutionen der Universität: Fakultäten > Fakultät für Mathematik, Physik und Informatik
Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut
Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut > Lehrstuhl Wirtschaftsmathematik
Profilfelder > Emerging Fields > Governance and Responsibility
Fakultäten
Profilfelder
Profilfelder > Emerging Fields
Titel an der UBT entstanden: Ja
Themengebiete aus DDC: 000 Informatik,Informationswissenschaft, allgemeine Werke > 004 Informatik
500 Naturwissenschaften und Mathematik > 510 Mathematik
Eingestellt am: 10 Apr 2015 09:47
Letzte Änderung: 16 Mär 2023 11:51
URI: https://eref.uni-bayreuth.de/id/eprint/10042