Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A 0.3622-Approximation Algorithm for the Maximum k-Edge-Colored Clustering Problem Kapitel lesen Erstes Kapitel lesen

2020 | OriginalPaper | Buchkapitel

Sensitive Instances of the Cutting Stock Problem

verfasst von : Artem V. Ripatti, Vadim M. Kartak

Erschienen in: Mathematical Optimization Theory and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We consider the well-known cutting stock problem (CSP). The gap of a CSP instance is the difference between its optimal function value and optimal value of its continuous relaxation. For most instances of CSP the gap is less than 1 and the maximal known gap \(6/5=1.2\) was found by Rietz and Dempe [11]. Their method is based on constructing instances with large gaps from so-called sensitive instances with some additional constraints, which are hard to fulfill. We adapt our method presented in [15] to search for sensitive instances with required properties and construct a CSP instance with gap \(77/64=1.203125\). We also present several instances with large gaps much smaller than previously known.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Easy NP-hardness Proofs of Some Subset Choice Problems
Nächstes Kapitel Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions
Literatur
1.
Baum, S., Trotter Jr., L.: Integer rounding for polymatroid and branching optimization problems. SIAM J. Algebraic Discrete Methods 2(4), 416–425 (1981)MathSciNetCrossRef
2.
Delorme, M., Iori, M., Martello, S.: Bin packing and cutting stock problems: mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1), 1–20 (2016)MathSciNetCrossRef
3.
Dyckhoff, H., Kruse, H.J., Abel, D., Gal, T.: Trim loss and related problems. Omega 13(1), 59–72 (1985)CrossRef
4.
Fieldhouse, M.: The duality gap in trim problems. SICUP Bull. 5(4), 4–5 (1990)
5.
Gilmore, P., Gomory, R.: A linear programming approach to the cutting-stock problem. Oper. Res. 9(6), 849–859 (1961)MathSciNetCrossRef
6.
Kantorovich, L.V.: Mathematical methods of organizing and planning production. Manage. Sci. 6(4), 366–422 (1960)MathSciNetCrossRef
7.
8.
Kartak, V.M., Ripatti, A.V., Scheithauer, G., Kurz, S.: Minimal proper non-IRUP instances of the one-dimensional cutting stock problem. Discrete Appl. Math. 187(Complete), 120–129 (2015)
9.
Marcotte, O.: An instance of the cutting stock problem for which the rounding property does not hold. Oper. Res. Lett. 4(5), 239–243 (1986)MathSciNetCrossRef
10.
Rietz, J.: Untersuchungen zu MIRUP für Vektorpackprobleme. Ph.D. thesis, Technischen Universität Bergakademie Freiberg (2003)
11.
Rietz, J., Dempe, S.: Large gaps in one-dimensional cutting stock problems. Discrete Appl. Math. 156(10), 1929–1935 (2008)MathSciNetCrossRef
12.
Rietz, J., Scheithauer, G., Terno, J.: Families of non-IRUP instances of the one-dimensional cutting stock problem. Discrete Appl. Math. 121(1), 229–245 (2002)MathSciNetCrossRef
13.
Rietz, J., Scheithauer, G., Terno, J.: Tighter bounds for the gap and non-IRUP constructions in the one-dimensional cutting stock problem. Optimization 51(6), 927–963 (2002)MathSciNetCrossRef
14.
15.
16.
Scheithauer, G., Terno, J.: About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem. In: Gaul, W., Bachem, A., Habenicht, W., Runge, W., Stahl, W.W. (eds.) Operations Research Proceedings. Operations Research Proceedings 1991, vol. 1991. Springer, Heidelberg (1992). https://​doi.​org/​10.​1007/​978-3-642-46773-8_​111CrossRef
17.
Scheithauer, G., Terno, J.: The modified integer round-up property of the one-dimensional cutting stock problem. Eur. J. Oper. Res. 84(3), 562–571 (1995)CrossRef
18.
Sweeney, P.E., Paternoster, E.R.: Cutting and packing problems: a categorized, application-orientated research bibliography. J. Oper. Res. Soc. 43(7), 691–706 (1992)CrossRef
Metadaten
Titel
Sensitive Instances of the Cutting Stock Problem
verfasst von
Artem V. Ripatti
Vadim M. Kartak
Copyright-Jahr
2020
Buch
Mathematical Optimization Theory and Operations Research

Print ISBN: 978-3-030-58656-0

Electronic ISBN: 978-3-030-58657-7

Copyright-Jahr: 2020

DOI
https://doi.org/10.1007/978-3-030-58657-7_9