Eindimensionales Zuschnittproblem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das eindimensionale Zuschnittproblem (engl. one-dimensional cutting stock problem) ist ein -schweres ganzzahliges lineares Optimierungsproblem mit dem Ziel, eindimensionale Teile in vorgegebenen Bedarfszahlen aus möglichst wenig Stücken Material gegebener Länge zuzuschneiden. Dieses Problem verdankt seine große Bedeutung auch dem Umstand, dass es als Relaxation für kompliziertere mehrdimensionale Pack- und Zuschnittprobleme verwendet wird, zum Beispiel beim Containerbeladeproblem mit Quadern, wenn man sich alle Teile in Streifen zerlegt denkt.

Problemstellung und grundlegende Definitionen[Bearbeiten | Quelltext bearbeiten]

Gegeben ist eine unbegrenzte Zahl von Stücken eindimensionalen Rohmaterials vorgegebener Länge . Daraus sollen Teile der Länge zugeschnitten werden, mit insgesamt also Teile. Dafür sollen möglichst wenige Stücke des Rohmaterials verbraucht werden. Reststücke können nicht miteinander verbunden werden und zählen als Abfall. Sind die Bedarfszahlen sehr klein, spricht man auch vom (eindimensionalen) Behälterproblem (Bin-Pack-Problem).

Unmittelbare Anwendungen sind zum Beispiel das Zuschneiden von Rohren oder das Abspeichern von nicht teilbaren und nicht weiter komprimierbaren Dateien auf möglichst wenig Datenträgern einheitlicher Kapazität. Die Verallgemeinerung auf mehrere verschiedene Längen an Rohmaterial wird später behandelt.

Soll eine bestimmte Schnittbreite berücksichtigt werden, ist dies möglich, indem alle Längen, also und () um vergrößert werden. Damit wird das Problem auf eines mit Schnittbreite 0 zurückgeführt.

Zunächst werden die Längen und die Bedarfszahlen (für ) zu Vektoren und zusammengefasst. Die Zusammenfassung aller Daten zu einer Instanz erfolgt als Quadrupel . Hierbei bedeutet der Begriff Problem immer eine Problemklasse, während erst mit konkreten Daten eine Instanz vorliegt.

Eine Zuschnittvariante ist ein Vektor nichtnegativer ganzer Zahlen, der angibt, wie oft jedes Teil in dieser Variante vorkommt. Die Variante ist genau dann zulässig, wenn

(1)

gilt. Die Indexmenge aller zulässigen Varianten   sei mit bezeichnet. Damit lautet das ganzzahlige lineare Optimierungsproblem:

(2)

bei

(3)
für alle (4)

Dieses Problem ist stets lösbar, wenn für alle Teilelängen gilt, da die Zielfunktion (2) nach unten beschränkt ist und nur ganzzahlige Werte annimmt und eine zulässige Lösung existiert, etwa aus jedem Stück Ausgangsmaterial nur ein Teil zu fertigen. Der Bedarf an zuzuschneidenden Teilen aller Sorten wird aufgrund der Bedingung (3) gedeckt. Ersetzt man in ihr das Gleichheitszeichen durch ≥, entsteht ein zum Modell (2)–(4) äquivalentes, denn man kann aus Zuschnittvarianten, die zu Überproduktion führen, einzelne Teile herauslassen. Auf diese Weise erhält man aus einer Optimallösung des abgeänderten Problems eine für das Problem (2)–(4) mit gleichem Zielfunktionswert.

Da die Anzahl der zulässigen Varianten und damit der Variablen in der Aufgabe (2)–(4) oft sehr groß ist, wurde auch nach alternativen Modellen gesucht. Ein solches besteht u. a. in der Formulierung als Optimierung eines Flusses in einem Netzwerk. Jenes Fluss-Modell stellt sich als äquivalent zur obigen Problemformulierung heraus. Wegen Einzelheiten sei z. B. auf[1] verwiesen.

Eine zulässige Zuschnittvariante heißt eigentlich, wenn gilt, also die Variante, für sich alleine einmal verwendet, keine Überproduktion liefert. Offensichtlich reichen eigentliche Varianten zur Lösung des Problems (2)–(4) aus.

Das Problem ist -schwer, denn schon die Frage, ob alle Teile aus nur zwei Stück Ausgangsmaterial geschnitten werden können, führt auf das Rucksackproblem, und dieses ist vollständig. Gemäß[2] ist das eindimensionale Bin-Pack-Problem sogar stark vollständig. Trotz dieser ungünstigen Komplexität können für viele Instanzen in akzeptabler Zeit Optimallösungen bestimmt werden, zum Beispiel mittels geeigneter Heuristiken. Um die Güte einer zulässigen Lösung zu bewerten, benötigt man möglichst scharfe untere Schranken.

Eine einfache untere Schranke für den optimalen Zielfunktionswert der ganzzahligen Optimierungsaufgabe stellt die Materialschranke

dar. Allerdings ist diese Schranke meist zu ungenau, denn die Differenz wächst im Allgemeinen unbeschränkt mit den Bedarfszahlen. Durch Abmilderung der Bedingung (4) gewinnt man aus dem Problem (2)–(4) Relaxationen mit oft deutlich schärferen Schranken, nämlich die

  • stetige Relaxation:
  bei für alle (5)
  • Einschränkung auf eigentliche Varianten:
  bei für alle mit , falls (6)

Die optimalen Zielfunktionswerte beider Relaxationen seien mit und bezeichnet. Dann zeigt man leicht . Von besonderem theoretischem Interesse ist die Lücke

.

Es stellt sich heraus, dass es schwer ist, für irgendeine Instanz zu prüfen.

Eine Verschärfung der Relaxation (6) erhält man mit der Einführung oberer Schranken für die Variantenhäufigkeiten. So darf etwa eine Schnittvariante höchstens -mal verwendet werden. Doch auch für diese kompliziertere Relaxation konstruiert man leicht Instanzen, bei denen die Schrankenverschärfung versagt.

Beispiel[Bearbeiten | Quelltext bearbeiten]

Beispielinstanz zum eindimensionalen Zuschnittproblem mit Optimallösung der stetigen Relaxation

Für die Instanz sind die Daten in nebenstehender Abbildung nochmals angegeben (rosa eingefärbt), dazu (grün gefärbt) die eindeutige Optimallösung der stetigen Relaxation (5). Nur die zweite Zuschnittvariante, nämlich , weist Verschnitt auf. Außer dieser Variante sind alle in der Relaxationslösung in positiver Häufigkeit vorkommenden Varianten uneigentlich. Wie man die Relaxationen löst, erklärt ein späterer Abschnitt. Es gilt . Die Instanz ergibt die für den Fall, dass kein Teil mehr als die Hälfte des Ausgangsmaterials ausmacht, größte bisher bekannte Lücke (Stand 2007).

Vervielfacht man die Bedarfszahlen mit elf oder ersetzt man sie durch den neuen Vektor , ergibt sich wieder die Lücke , jedoch wird für die abgeänderte Instanz . Nur noch die Verschärfung der Relaxation (6) verrät . Doch eine geringfügige Verkürzung einzelner der gemäß zu schneidenden 25 Teile ermöglicht, auch die Verschärfung der Relaxation (6) wirkungslos zu machen.

Äquivalente Instanzen[Bearbeiten | Quelltext bearbeiten]

Zwei Instanzen und heißen äquivalent, wenn und gilt und jede für eine der beiden Instanzen zulässige Variante auch für die andere Instanz zulässig ist. Äquivalente Instanzen erhält man aus einer gegebenen zum Beispiel durch Multiplikation aller Längen mit einer positiven Konstanten oder indem man Teilelängen um bis zu ε verkleinert oder das Ausgangsmaterial um ε verlängert, falls hinreichend klein ist, weil keine neue Variante hinzu kommt. Somit kann man stets zu rationalen und nach Multiplikation mit dem Hauptnenner zu ganzzahligen Daten übergehen.

Eine gemäß (1) zulässige Variante heißt maximal, wenn gilt, also der Verschnitt kleiner als das kleinste zuzuschneidende Teil ist. Um zu prüfen, ob die Instanzen und bei äquivalent sind, genügt es offensichtlich zu untersuchen, ob jede für eine Instanz maximale Variante auch für die andere Instanz zulässig ist und umgekehrt. Dagegen darf nicht schon auf Äquivalenz geschlossen werden, wenn jede für maximale Variante auch für maximal ist, wie das Gegenbeispiel , zeigt.

Beispiel zur Äquivalenz: Thomas Gau fand bei Testrechnungen die Instanz mit Lücke .[3] Ersetzt man die 3001 durch 3125, ergibt sich eine äquivalente Instanz, da alle anderen Längen durch 250 teilbar sind und die Variante maximal ist. Deshalb geht keine zulässige Variante verloren. Dividiert man nun alle Längen durch 125, ergibt sich wieder eine äquivalente Instanz, nämlich . Eine weitere äquivalente Instanz entsteht hieraus durch Multiplikation aller Längen mit und geeignetes Runden, nämlich .

Um nachzuweisen, dass keine äquivalente Instanz mit durchgängig ganzzahligen Daten und kleinerer Länge des Ausgangsmaterials existiert, kann das duale Simplexverfahren ohne Zielfunktion eingesetzt werden. Drei Typen von Ungleichungen sind von den äquivalenten Instanzen zu erfüllen:

  • für aufgrund der Sortierung
  • für jede maximale Variante
  • für jede unzulässige Variante wegen der Ganzzahligkeit.

Die meisten dieser Ungleichungen sind überflüssig, d. h., sie folgen aus anderen. Im Simplexschema können derartige Zeilen gestrichen werden, wenn sie keine negativen Einträge enthalten und die zugehörige Basisvariable nicht zu den oder gehört. Zuletzt bleiben für die gesuchten Längen nur Zeilen übrig. Allerdings existieren Beispiele, die zur Beschreibung aller äquivalenten Instanzen mit durchgängig ganzzahligen Daten mehr Ungleichungen benötigen, wo also zusätzliche Zeilen mit mindestens einem negativen Eintrag im Endschema verbleiben.

Beispiel[4]: Gesucht werden alle zur Instanz äquivalenten Instanzen mit durchgängig ganzzahligen Längen, wobei für alle gilt. Offensichtlich ist zu fordern. Neben den Unzulässigkeitsbedingungen und könnten noch viele überflüssige Ungleichungen notiert werden, darunter zu nicht aufgeführten weiteren maximalen Varianten. Die zu diesen sechs Ungleichungen gehörenden nichtnegativen Schlupfvariablen seien mit , bezeichnet. Sie sind als Differenz ganzzahliger Größen ebenfalls ganzzahlig. Folgendes Schema entsteht:

Demzufolge darf die Schlupfvariable nicht beliebig unabhängig von den anderen erhöht werden. Tauscht man gegen , geht die Ganzzahligkeit von verloren, falls alle Schlupfvariablen der Nichtbasis danach auf 0 gesetzt werden. Insgesamt ergibt sich, dass und , mit den vier Parametern beschrieben werden können, während gilt, also die ganzzahligen Punkte eines Intervalls zu nehmen sind. In anderen Beispielen können derartige Besonderheiten noch komplizierter aussehen. Eine weitere Schwierigkeit besteht jeweils darin, die Äquivalenz vollständig zu prüfen, ob also keine notwendige Ungleichung, insbesondere zu unzulässigen Varianten, fehlt.

Eine andere Art der Gleichwertigkeit ergibt sich, indem man Teile mit Bedarfszahlen größer als 1 als mehrere verschiedene Teile, die jeweils genau einmal gefordert werden, auffasst. Wenn zum Beispiel dreimal ein Teil der Länge 5 gewünscht wird, kann man ebenso etwa und anstelle des einen Teils mit der Bedarfszahl 3 schreiben. Folglich ist das eindimensionale Bin-Pack-Problem, bei dem jedes Teil genau einmal in Behälter der Größe zu packen ist, gleichwertig zum oben eingeführten eindimensionalen Zuschnittproblem (2)–(4).

Der Teilbarkeitsfall; modifizierte Ganzzahl-Aufrundungseigenschaft[Bearbeiten | Quelltext bearbeiten]

Eine zulässige Variante heißt elementar, wenn sie nur eine Teilesorte enthält, also von der Gestalt mit ist, wobei den -ten Basis-Einheitsvektor des bezeichnet, .

Der Teilbarkeitsfall liegt vor, wenn ganzzahliges Vielfaches jeder Teilelänge ist. Dann ergibt sich sofort , indem in der stetigen Relaxation (5) nur maximale elementare Varianten verwendet werden.

Beispiel: Die Instanz besitzt für die Relaxation (5) wegen den optimalen Zielfunktionswert . Hier gilt aber , d. h., es ist unmöglich, mit nur zwei Stück Ausgangsmaterial alle Teile zu fertigen. Diese Instanz ergibt die größte bisher im Teilbarkeitsfall bekannte Differenz , nämlich (Stand 2007).

Für obige Instanz gilt die Ganzzahl-Aufrundungseigenschaft nicht. Da alle bisherigen Erfahrungen darauf schließen ließen, dass die Lücke für beliebige Instanzen des eindimensionalen Zuschnittproblems (2)–(4) stets klein ist, wurde der Begriff der modifizierten Ganzzahl-Aufrundungseigenschaft (engl. modified integer round-up property, MIRUP) geprägt. Eine Instanz weist diese Eigenschaft auf, wenn gilt.[5] Die Vermutung, jede Instanz des eindimensionalen Zuschnittproblems (2)–(4) besitze MIRUP, konnte bisher (Stand 2007) nur in Spezialfällen nachgewiesen werden, zum Beispiel für den Teilbarkeitsfall.[6] Ein einfacherer Beweis von Guntram Scheithauer und Johannes Terno[7] wurde in der Dissertation[8] noch verschärft. Es gilt folgender

Satz: Für jede Instanz des Teilbarkeitsfalls gilt . Sind sämtliche Teile größer als des Ausgangsmaterials, gilt sogar .

Das Vorhandensein unendlich vieler, paarweise nicht äquivalenter Instanzen des Teilbarkeitsfalls mit folgt unter anderem aus diesen Aussagen:

  • Seien paarweise teilerfremde ganze Zahlen mit und . Für alle sei , und es gebe keine Lösung der ganzzahligen Aufgabe (2)–(4), in der diese Teile (mit den Bedarfszahlen ) in höchstens Varianten untergebracht werden. Ferner seien und für . Die so festgelegte Instanz besitzt eine Lücke .[9]
  • Für beliebiges sei das kleinste gemeinsame Vielfache von (oder ein Mehrfaches davon). Dann besitzt die Instanz eine Lücke .[10]
  • Sei beliebig und . Dann gilt für die Instanz .[8]

Lösung der stetigen Relaxation[Bearbeiten | Quelltext bearbeiten]

Schon für relativ kleine Parameter ist die Mächtigkeit der Menge oft so groß, dass eine vollständige Aufzählung aller zulässigen Zuschnittvarianten nicht in Frage kommt. Daran ändert sich auch nichts, wenn nur verschnittarme Varianten betrachtet werden. Da aber auch in einer Optimallösung gelegentlich verschnittreiche Varianten vorkommen, wäre dieser Lösungsansatz falsch. Aus dieser Not machten Gilmore und Gomory eine Tugend, indem sie die Relaxation mit dem revidierten Simplexverfahren lösten, als Start mit den einfachsten Varianten begannen und bessere bei Bedarf im Laufe der Optimierung suchten.[11]

In der revidierten Simplexmethode werden die zur Zielfunktion gehörenden Koeffizienten in Basis- und Nichtbasisanteil bzw. aufgeteilt, ebenso die Nebenbedingungen in der Weise , wobei die Basismatrix regulär ist. Löst man nach auf und setzt dies in die Zielfunktion ein, so ergibt sich . Da in unserem Zuschnittproblem alle Zielfunktionskoeffizienten 1 sind, ist eine Verbesserung des Zielfunktionswertes der stetigen Relaxation (5) folglich nur möglich, wenn eine gemäß (1) zulässige Variante mit existiert. Für diese Spaltengenerierung ist somit jeweils ein Rucksackproblem

  bei   (7)

zu lösen, wobei gilt. Eine einfache Rechenkontrolle besteht in .

Damit im Simplexverfahren Zyklen vermieden werden, empfiehlt sich die Regel von Bland (vgl. Simplexverfahren#Zeilenauswahl). Um diese Regel umzusetzen, hebt man jede gefundene Variante auf und prüft, bevor das Spaltengenerierungsproblem (7) gelöst wird, ob früher eine Variante abgespeichert wurde, für die gilt. In diesem Falle wird nicht das Rucksackproblem (7) bearbeitet, sondern von den abgespeicherten Varianten eine in die Basis getauscht, die den größten Wert für das Skalarprodukt ergibt. Ansonsten muss die Spaltengenerierungsaufgabe gelöst werden. Den Aufwand für eine exakte Lösung des Problems sollte man nicht scheuen, da sonst in der Regel wesentlich mehr Simplexschritte gebraucht werden.

Ein einfaches Beispiel: Von eindimensionalem Ausgangsmaterial der Länge 11 sind in besonders hoher Stückzahl Teile der Längen 6, 4 und 1 zu schneiden, und zwar im Verhältnis . Die Materialausnutzung ist zu maximieren. Das bedeutet, hier ist eine Optimallösung der stetigen Relaxation (5) von der Instanz gesucht. Für die erste Basis werden maximale elementare Varianten gewählt, das sind , und , so dass anfangs eine Diagonalmatrix ist. Es ergeben sich die nachfolgenden revidierten Simplexschemata, unter denen die neue Variante angegeben ist. Die Pivotelemente sind jeweils mit einem Stern gekennzeichnet. Aus Gründen der einfacheren Programmierung wurden die rechten Seiten und der Vektor in der ersten Spalte bzw. Zeile untergebracht. Ganz rechts steht jeweils die transformierte neue Spalte, bestehend aus und .

                          optimal

Die Varianten und sind folglich im Verhältnis zu schneiden. Beim letzten Austausch war (und nicht ) aus der Basis zu tauschen, um der Regel von Bland zu gehorchen, nämlich bei mehreren wählbaren Zeilen immer diejenige auszuwählen, die zum Austausch der Variable mit dem kleinsten Index aus der Basis führt. Obwohl dieses Beispiel akademisch aussehen mag, zeigt es, dass auch negative Werte im Laufe der Rechnung auftreten können, wenn die Bedarfszahlen geeignet vorgegeben waren. Soll die Relaxation (6) mit Einschränkung auf eigentliche Varianten gelöst werden, kann dieser Effekt noch wesentlich stärker auftreten. Im Spaltengenerierungsproblem ist die Verwendung jener Teile verboten, so dass sich die Spaltengenerierungsaufgabe vereinfacht.

Residuale Instanzen[Bearbeiten | Quelltext bearbeiten]

Um das ganzzahlige Problem (2)–(4) zumindest nahezu optimal zu lösen, kann zunächst die Relaxation (5) oder (6) herangezogen werden. Durch einfaches Aufrunden ergibt sich eine zulässige Lösung, wenn Überproduktion erlaubt wird. Bei einzelnen Zuschnittvarianten kann vielleicht sogar abgerundet werden. Doch selbst bei optimaler Rundung erhielte man im Allgemeinen einen Zielfunktionswert deutlich über dem optimalen Wert . Dieses Vorgehen erscheint deshalb nur sinnvoll, wenn die Anzahl verschiedener Varianten minimiert werden soll, weil die Umstellung der Fertigungsanlage auf andere Schnittpläne sehr aufwendig ist. Ansonsten empfiehlt es sich, durchgängig abzurunden und für die verbliebenen Teile entweder mit einer neuen Heuristik fortzufahren oder noch einmal die Relaxation (6) zu benutzen.

Sei eine mittels Simplexverfahren ermittelte optimale Basislösung der stetigen Relaxation (5). Ersetzt man in der Instanz den Vektor der Bedarfszahlen durch , entsteht eine sogenannte residuale Instanz . Dabei dürfen durchaus auch Nullen im Bedarfsvektor auftreten. Bei vielen Abschätzungen der Lücke hilft folgendes

Lemma: Seien beliebig. Dann gilt für residuale Instanzen die Implikation

.[12]

Beweis: Nach Voraussetzung gibt es eine optimale Basislösung, in der jede Variante eine Häufigkeit hat. Einen ganzzahligen Zuschnittplan mit Überproduktionen erhält man aus der Optimallösung der Relaxation (5) durch einfaches Aufrunden. Das ergibt und somit

.

Zum -fachen dieser Ungleichung addieren wir die gemäß Voraussetzung gültige Ungleichung und erhalten . Division durch liefert die Behauptung.

Stets gilt , so dass für theoretische Untersuchungen die Betrachtung residualer Instanzen ausreicht. Insbesondere kann man aus einer Optimallösung des ganzzahligen Problems (2)–(4) für eine für konstruieren, falls die Ganzzahl-Aufrundungseigenschaft erfüllt. Kennt man eine gute ganzzahlige Lösung für , dann auch für . Leider gilt dies nicht stets auch für die Optimalität, wie folgendes Gegenbeispiel zeigt:

hat eine eindeutige Optimallösung der Relaxation (5), nämlich für , wobei die (in der Relaxation) verschnittfreien Varianten , , und zugrunde gelegt wurden. Es gilt und , wobei es mehrere verschiedene Optimallösungen für das ganzzahlige Problem (2)–(4) gibt. Die residuale Instanz ist hier eindeutig (mit ), und es gilt , so dass das Abtrennen des ganzzahligen Anteils von der Optimallösung der stetigen Relaxation zu einer Erhöhung der Lücke führte. Bei Verwendung der Relaxation (6) wäre dieser Effekt nicht eingetreten. Doch bei Vorgabe des Bedarfsvektors vermag auch die Einschränkung auf eigentliche Varianten diese Unannehmlichkeit nicht zu verhindern.

Ein Näherungsalgorithmus mittels Relaxation[Bearbeiten | Quelltext bearbeiten]

Soll das ganzzahlige Problem (2)–(4) exakt gelöst werden, erweist es sich oft als vorteilhaft, gelegentlich innerhalb der Optimierung mit Hilfe eines Näherungsverfahrens nach guten zulässigen Lösungen zu suchen. Eine entsprechende Verfahrensskizze ist diese:

  1. Löse die Relaxation (6) und trenne den ganzzahligen Anteil ab.
  2. Es verbleibe eine residuale Instanz . Wähle von den verbliebenen Varianten eine mit maximaler Häufigkeit. Diese Variante sei .
  3. Bei streiche überzählige Teile aus .
  4. Ergänze, wenn möglich, weitere noch zuzuschneidende Teile in .
  5. Falls der Nullvektor ist, ist nichts mehr zu schneiden, halt.
  6. Solange es möglich ist, ersetze in jeweils ein Teil durch ein größeres noch zu schneidendes.
  7. Schneide die Variante möglichst oft zu, passe die Bedarfszahlen an und gehe zum Punkt 2.

Der Aufwand für Punkt 6 ist mit abzuschätzen. Die in Punkt 1 ausgewählten Varianten können vor dem Abtrennen mitunter auch wie in den Punkten 2–7 nachbearbeitet werden. Die so verbesserte Heuristik fand bei pseudozufällig erzeugten Testinstanzen oft Optimallösungen. Falls der erzielte Zielfunktionswert für das ganzzahlige Problem (2)–(4) doch größer als wird, kann in Punkt 2 auch noch einmal die Relaxation (6) gelöst werden.

Die Farley-Schranke[Bearbeiten | Quelltext bearbeiten]

Um eine gute zulässige Lösung des ganzzahligen Zuschnittproblems (2)–(4) zu ermitteln, genügt manchmal eine zulässige, nicht optimale Lösung der Relaxation (5) oder (6). Falls man aus diesem Grunde die Optimierung vorzeitig abbrechen möchte, zum Beispiel weil die erzielten Zielfunktionswerte zu stagnieren beginnen, benötigt man dennoch Gewähr, dass man tatsächlich nahe am Optimum ist. Dies leistet eine untere Schranke nach A. A. Farley,[13] die auf der Dualitätstheorie der linearen Optimierung beruht.

Das zur stetigen Relaxation (5) gehörige duale Optimierungsproblem lautet

bei für jede zulässige Variante .

Jedes , welches zum zulässigen Bereich des dualen Problems gehört, liefert somit eine untere Schranke für den optimalen Zielfunktionswert. Ein geeignetes findet man leicht, sobald das Rucksackproblem (7) gelöst wurde. Die ermittelte Variante sei . Gilt , liegt eine Optimallösung der Relaxation vor. Andernfalls setzen wir und erhalten für jede beliebige zulässige Zuschnittvariante die Abschätzung laut Annahme über . Folglich ist das gewählte für die duale Aufgabe zulässig. Daraus ergibt sich die gewünschte untere Schranke

,

die sich bei Fortsetzung der Optimierung dem optimalen Zielfunktionswert der Relaxation nähert. Analog sieht die Schranke für (6) aus.

Beispiel: Für die Instanz wurden oben die berechneten Simplexschemata angegeben. Vor dem ersten Austausch galten und sowie , also . Nach dem Eintauschen der Variante in die Basis wurden , und ermittelt. Folglich sinkt die untere Schranke vorübergehend auf und wächst nicht monoton.

Für mehrdimensionale Zuschnittprobleme kann eine entsprechende untere Schranke ebenso aufgestellt werden. Gemäß A. A. Farley ermöglicht diese Schranke die Einsparung vieler Spaltengenerierungs- und Austauschzyklen, ohne Gefahr zu laufen, weit vom Optimum entfernt zu sein.

(k,k+1)-Instanzen[Bearbeiten | Quelltext bearbeiten]

Sei eine positive ganze Zahl. Die Instanz heiße -Instanz, falls für alle zutrifft, also jedes Teil genau - oder -mal (zuzüglich Verschnitt) in das Ausgangsmaterial passt. Das Studium dieser Instanzen ermöglicht einerseits den Bau besonders bösartiger Beispiele, andererseits Abschätzungen – auch im allgemeinen Fall – für die Lücke . Umfangreiche Untersuchungen enthält,[8] während die diesbezüglichen Beiträge in[10] und[12] Vorläufer darstellen.

Unter einer -Teile-Variante verstehen wir eine beliebige zulässige Zuschnittvariante , mit der genau Teile zugeschnitten werden (), d. h. , wobei für den aus lauter Einsen bestehenden Einsvektor steht.

(k,k+1)-Instanzen mit Δ=1[Bearbeiten | Quelltext bearbeiten]

Offensichtlich gilt bei die Ganzzahl-Aufrundungseigenschaft, weil nur möglich ist. Bei ändert sich die Situation jedoch grundlegend. Ist , ergibt sich und für die Instanz

,

wobei die Teile nicht nach der Länge geordnet wurden. Verwendet man in der stetigen Relaxation (5) die verschnittfreien Varianten , und je -mal, die Varianten , und je -mal so bestätigt man schnell .

Für folgende Instanzen gilt jeweils und :

  • :
  • :
  • :

Es gibt keine (2,3)-Instanz mit . Dagegen gilt und für die Instanzen

  • bei
  • bei .

Komplementäre Instanzen[Bearbeiten | Quelltext bearbeiten]

Zuerst betrachten wir (2,3)-Instanzen mit . Mit der Festlegung für alle erhalten wir eine (2,3)-Instanz mit , die wir komplementäre Instanz zu nennen. Die zu komplementäre Instanz ist wieder . Ist eine (für ) verschnittfreie Variante mit genau drei Teilen, ist auch für zulässig und verschnittfrei. Dagegen entsprechen verschnittbehafteten 3-Teile-Varianten in unzulässige in und umgekehrt. Folglich kann man nicht von Optimallösungen der Aufgaben (2)–(4) oder (5) oder (6) für auf die entsprechenden Optimallösungen für schließen. Dennoch fällt die Verallgemeinerung auf -Instanzen nicht schwer.

Gegeben sei nun eine -Instanz mit , für die zutrifft, in der also in jeder Optimallösung der stetigen Relaxation nur verschnittfreie Varianten mit je Teilen in positiver Häufigkeit verwendet werden. Dann ist für hinreichend großes die Instanz

eine zu äquivalente Instanz, denn in -Instanzen sind alle Varianten mit höchstens Teilen zulässig und alle Varianten mit mindestens Teilen unzulässig, während der Verschnitt einer -Teile-Variante in ebenso groß wie in ist. Für unsere Zwecke reicht die Forderung

aus. Die zu komplementäre Instanz definieren wir als

Dabei braucht nicht notwendig -Instanz zu sein. Hat die Instanz eine Lücke , gilt das auch für fast alle in der Instanz , da es nur endlich viele Kombinationen von höchstens Teilen gibt, die eine verschnittfreie Variante ergeben. Folglich erfüllt auch die komplementäre Instanz , für fast alle , die der oben angegebenen Bedingung genügen, die Ganzzahl-Aufrundungseigenschaft nicht.

Beispiel: weist für alle eine Lücke 1 auf, und es gilt . Für alle ist eine (2,3)-Instanz. Die zugehörige komplementäre Instanz lautet und besitzt für alle ebenfalls die Lücke 1. Für ist auch eine (2,3)-Instanz.

(2,3)-Instanzen mit auffälligen Nennern[Bearbeiten | Quelltext bearbeiten]

Bevor (2,3)-Instanzen mit Lücke angegeben werden, demonstrieren wir, wie vielfältig der Nenner von werden kann. Dazu sei beliebig gewählt. Die Festlegungen , , und , für liefern eine (2,3)-Instanz mit . Der Bruch kann nur durch 9 gekürzt werden. Dagegen ergeben sich bei der (2,3)-Instanz

für die optimalen Zielfunktionswerte und für die stetige Relaxation (5), was zur Vermutung

führt. Der Beweis steht noch aus. Für sind Zähler und Nenner teilerfremde natürliche Zahlen.

Variiert man die Längen geringfügig oder streicht man einzelne Teile aus der Instanz, können sich noch ganz andere Nenner ergeben, zum Beispiel:

  • ,
  • ,
  • ,
  • ,
  • ,

(2,3)-Instanzen mit Δ>1[Bearbeiten | Quelltext bearbeiten]

Verknüpft man die Instanzen mit den Zweierpotenznennern und diejenigen mit Lücke 1 in geeigneter Weise, entstehen nach wenigen weiteren Umgestaltungen (2,3)-Instanzen mit Lücke , nämlich

  • ,
  • ,
  • ,
  • , .

Die Instanzen mit den ungeraden Nennern eignen sich für diese Konstruktion nur bedingt, weil sie verhältnismäßig viel Verschnitt verursachen.

Rückführung auf einfachere Instanzen[Bearbeiten | Quelltext bearbeiten]

Um obere Schranken für die Lücke nachzuweisen, erscheint es aufgrund vorstehender Ergebnisse notwendig, die Instanzen zu vereinfachen. Dies ist leicht möglich. Um nicht den Rahmen zu sprengen, verzichten wir hier auf Beweise.

Sei eine beliebige -Instanz. Bezeichnen und die Häufigkeiten aller -Teile-Varianten in Optimallösungen der Relaxation (5) bzw. des ganzzahligen Problems (2)–(4), gilt . Gilt , können die größten Teile in -Teile-Varianten zugeschnitten werden, und nach deren Abtrennung verbleibt eine Instanz mit und . Im Gegensatz zu den residualen Instanzen wächst hier die Lücke nicht. Mit jedem weiteren Abtrennen des jeweils größten verbliebenen Teils nimmt der optimale Zielfunktionswert der stetigen Relaxation (5) nochmals um ab. Daraus ergibt sich eine wichtige

Folgerung: Jede -Instanz mit kann auf eine Instanz mit , und reduziert werden. Das heißt insbesondere: Ist so, dass für alle -Instanzen mit die modifizierte Ganzzahl-Aufrundungseigenschaft (MIRUP) gilt, dann auch für alle -Instanzen mit .

Beispiel: In der (2,3)-Instanz

gilt und , also . In Optimallösungen des ganzzahligen Problems (2)–(4) kommen folglich mindestens zwei Varianten mit je höchstens zwei Teilen vor. Vier Teile der Länge 4097 werden in zwei 2-Teile-Varianten zugeschnitten. In der entstehenden Instanz gilt und . Schneidet man nun die beiden größten Teile, also mit Längen 4097 und 3073, in einer gesonderten Variante, sinkt der optimale Zielfunktionswert der Relaxation (5) auf . Trennt man nun noch zwei Teile der Länge 3073 ab, ergibt sich für die Restinstanz . Dennoch gibt es viele nicht ganzzahlige Optimallösungen der Relaxation (5).

Gemäß der Folgerung bedeutet es keine Einschränkung, wenn ab hier nur noch -Instanzen mit und betrachtet werden. Ohne Beschränkung der Allgemeinheit seien die Teile nach fallenden Längen geordnet, also . Die Anzahl aller zuzuschneidenden Teile mit Länge oberhalb sei . Für bezeichne jeweils die Gesamthäufigkeit aller in einer vorliegenden Optimallösung der stetigen Relaxation (5) vorkommenden Varianten, die genau Teile aus (und größere Teile) enthalten.

Aufgrund dieser Einteilung der Teile in größere und kleinere ergibt sich und , also auch . Gilt , können die größten Teile aus in einer abgesonderten Variante geschnitten werden, und die Abtrennung dieser Variante ändert die Lücke nicht. Unter Umständen findet man anstelle dieser eine zulässige -Teile-Variante, die ein größeres Teil enthält, aber keine kleineren. Dann kann die Reduktion eventuell häufiger vorgenommen werden.

Beispiel: In der (2,3)-Instanz

gilt , so dass gewiss siebenmal je drei Teile der Länge 2731 in einer Variante abgetrennt werden können. Diese Variante wird aber durch und dominiert. Diese beiden verschnittfreien Varianten können zwei- bzw. fünfmal zugeschnitten werden, ohne Überproduktion zu erzielen. In der erhaltenen Instanz gilt wieder , und nun kann die Variante einmal abgetrennt werden. (Teil 5 war schon verbraucht.) Das führt auf die Instanz

mit und , so dass noch neunmal die Variante abzutrennen ist, ohne die Lücke zu ändern. Auf der Grundlage obiger Aussagen ist keine weitere Reduktion mehr möglich. Mittels Heuristiken findet man nun leicht eine ganzzahlige Optimallösung, und .

A-priori-Zulässigkeit von Varianten[Bearbeiten | Quelltext bearbeiten]

Seien , , und . In der -Instanz mit seien und für wieder wie im vorigen Abschnitt definiert. Die Zuschnittvariante ist unabhängig von den Längen und zulässig, kurz geschrieben, wenn eine der folgenden Bedingungen erfüllt ist:

Bei gilt auch . Gemäß den Reduktionen im vorigen Abschnitt kann dies erzwungen werden, auch und . Dies wird im Folgenden vorausgesetzt, wenn obige sehr technische Aussagen auf (2,3)-Instanzen angewandt werden. Dann gilt auch .

Unter den oben angegebenen Voraussetzungen ist in einer (2,3)-Instanz die Variante zulässig, kurz geschrieben, wenn eine der folgenden Bedingungen zutrifft:

(a) oder
(b) oder
(c) (erfordert Fallunterscheidung bezüglich )
(d)

Die gemäß diesen hinreichenden Kriterien zulässigen Zuschnittvarianten sollen (a)-, (b)-, (c)- bzw. (d)-Variante heißen. Von diesen Kriterien kann keins durch die anderen ausgedrückt werden, obwohl jede (d)-Variante mit auch (a)-Variante ist und die (a)-Varianten die (b)-Varianten dominieren. Bedingung (a) ist aber bei nicht anwendbar. (a)-Varianten sind bei am günstigsten, (c)-Varianten bei , weil wird.

Beispiel: Seien und . Bei findet man z. B. die (a)-Variante (5,16,26), denn . (d) hätte wegen kein Ergebnis gebracht. Eine (b)-Variante ist (2,18,27), denn . Wegen durfte (a) nicht benutzt werden. Bei findet man wegen keine (a)- und (b)-Varianten. Eine (d)-Variante ist (9,10,27), denn . Wegen (gemäß Reduktionen) und ist und daher (9,19,21) eine (c)-Variante, denn und . Hier hätte das Kriterium (d) wegen versagt.

Nun seien , und gegeben. Dann gilt und , so dass es die (a)-Varianten (1,4,6), (2,3,6) und (3,4,5) gibt. Wäre , könnte man schnell einen Widerspruch konstruieren oder zeigen, dass (2,4,5) die einzige verwendete Variante für Teil 2 in der Relaxation (5) wäre. Beide Fälle ergeben .

Aufstellung ganzzahliger Schnittpläne[Bearbeiten | Quelltext bearbeiten]

Es kommt nicht nur darauf an, die Zulässigkeit einzelner Zuschnittvarianten nachzuweisen, sondern dass kein nur einmal vorhandenes Teil in mehreren Varianten verwendet wird. Wieder betrachten wir nur -Instanzen mit , in denen die obigen Reduktionen vorgenommen wurden, wo also auch und gilt. Alleine von , und abhängige Abschätzungen für werden angegeben.

Zwei Zuschnittvarianten sollen unkorreliert heißen, wenn sie eigentlich sind und kein Teil gleichzeitig in beiden Varianten vorkommt, also gilt. Sei die Anzahl derjenigen Teile aus , die nicht gleichzeitig in paarweise unkorrelierten -Teile-Varianten untergebracht werden können, einerlei welcher Plan für das Problem (2)–(4) zugrunde gelegt wird. Dann gilt:

  • mit
  • , speziell bei .

Daraus folgt für (2,3)-Instanzen mit sofort MIRUP, also . Bei kann man geeignete (a)- und/oder (d)-Varianten auswählen, so dass höchstens sechs große Teile übrig bleiben, was auch MIRUP ergibt. Zum Beispiel gibt es bei , stets die (d)-Varianten (7,17,30), (8,18,29), (9,19,28), (10,20,27), (11,21,26), (12,22,25) und (13,23,24). Bei ist damit alles gezeigt, ansonsten ersetzt man die erste Variante durch die (a)-Variante (7,14,30) und bei noch weitere Varianten entsprechend. Dagegen kann alleine mittels obiger Aussagen MIRUP im Fall nicht mehr bewiesen werden.

Aussagen zum allgemeinen Fall[Bearbeiten | Quelltext bearbeiten]

Inwieweit die Lücke für eine beliebige Instanz beschränkt ist, konnte noch nicht abschließend erforscht werden. So blieb beispielsweise noch offen, ob durch eine Konstante beschränkt ist oder linear mit wachsen kann oder etwa eine Abschätzung der Art mit einer Konstante für alle Instanzen des eindimensionalen Zuschnittproblems zutrifft.

Aus der Betrachtung residualer Instanzen folgt die fast triviale Aussage

.

Deutlich komplizierter ist der Beweis für die Abschätzungen

und

sowie der Nachweis der Ganzzahl-Aufrundungseigenschaft für alle Instanzen mit .[12] Dagegen ist es eine leichte Übung, nachzuweisen, falls ganzzahlig ist.

Ferner konnte MIRUP, also , für folgende Fälle bewiesen werden:[8]

  • , wenn außerdem alle Teile größer als ein Viertel des Ausgangsmaterials sind.

Dazu diente auch folgende Aussage, für die[14] eine gute Vorlage enthielt:

Lemma: Über die Instanz werden für alle , ferner sowie und vorausgesetzt. Gilt , so sei , andernfalls und . Dann besitzen die Instanzen und die gleiche Lücke , d. h., beim einmaligen Zuschneiden des größten Teils und des ggf. größten dazu passenden Teils ändert sich unter den angegebenen Voraussetzungen die Lücke nicht.

Keine der Voraussetzungen kann weggelassen werden, wie die Gegenbeispiele und mit und zeigen.

Das MAXGAP-Problem; Konstruktionssätze für große Δ[Bearbeiten | Quelltext bearbeiten]

Das MAXGAP-Problem (gap ‹engl.› Lücke, Schlucht, Aussparung, ...) lautet: Man finde Instanzen des eindimensionalen Zuschnittproblems (2)–(4) mit möglichst großer Lücke .[15]

Die größte bisher (Stand 2007) erreichte Lücke beträgt .[8]

Eine Instanz mit und ist diese: ,

Der Nachweis, dass die Ganzzahl-Aufrundungseigenschaft nicht gilt, erfolgte mit Schnittebenenverfahren.[16]

Sollte für unbeschränkt sein, kann das MAXGAP-Problem sinnvollerweise wie folgt abgeändert werden: Man bestimme Instanzen mit möglichst großer Lücke zu vorgegebener oberer Schranke für die Anzahl verschiedener Teile.

Inzwischen konnten mit Hilfe zweier Konstruktionssätze unter anderem Instanzen mit folgenden Werten für gefunden werden:[17]

Erster Konstruktionssatz: Die Instanz mit rationalen Längen weise die Lücke auf. Sei . Ferner sei so gewählt, dass für jeden Vektor mit und auch gilt. Dann besitzt die Instanz eine Lücke größer oder gleich .[10]

Sind alle Daten ganzzahlig, erfüllt stets die Voraussetzungen, da jede unzulässige Variante mindestens eine Einheit zu viel Material benötigt. Die Anwendung dieses Konstruktionssatzes mit auf die Instanzen , und das am Anfang angegebene illustrierte Beispiel, die die Lücken , bzw. aufweisen, ergibt die Instanzen , und mit den Lücken , und .

Vor weiteren Konstruktionen für Instanzen mit großer Lücke erklären wir zusammengesetzte Instanzen. Für zwei Instanzen und gelte zunächst . In diesem Fall bedeutet die zusammengesetzte Instanz den Auftrag, alle Teile aus und in den jeweils geforderten Stückzahlen aus dem einheitlichen Material der Länge zuzuschneiden. In der Situation werden alle Längen in einer Instanz mit einer geeigneten Konstante multipliziert. Man kann auch beide Instanzen so anpassen. Bis auf Äquivalenz ergibt sich damit dasselbe.

Beispiel: ist genau die obige mit der Abbildung illustrierte Beispielinstanz . Hier addieren sich die Lücken 0,1 und 1,0 zu 1,1.

Spezielle parametrisierte Instanzen mit Lücke sind die folgenden:

Diese Instanzen erweisen sich als nützlich zur Konstruktion großer Lücken. Die Teilelängen der beiden ersten Instanzen nähern sich für , während in der dritten Instanz das vierte bis neunte Teil relativ klein sind. Für beliebige mit gibt es natürliche Zahlen , , so dass für zutrifft. Analoges gilt für .

Zweiter Konstruktionssatz: In der Instanz mit und ist ausdrücklich auch erlaubt. Erhöht man um 1, so nehme der optimale Zielfunktionswert der ganzzahligen Aufgabe (2)–(4) zu. Dann gibt es natürliche Zahlen , mit , so dass die zusammengesetzte Instanzen und die Lücke aufweisen,[8] vgl. auch[12]

Beispiel: Die Instanz erfüllt die Voraussetzungen, denn in keiner Optimallösung des Problems (2)–(4) findet sich eine Zuschnittvariante mit mindestens zwölf Einheiten Verschnitt. Mit entsteht die Instanz mit Lücke .

Die Annahme bedeutet wegen , dass der größtmögliche Verschnitt in einer Variante, die in einer Optimallösung des ganzzahligen Problems (2)–(4) in positiver Häufigkeit vorkommen kann, kleiner ist als die Hälfte des kleinsten Teils in der Instanz. Diese Bedingung zu erfüllen, stellt die Hauptschwierigkeit bei der Anwendung des zweiten Konstruktionssatzes dar. So genügt es nicht, wenn der größtmögliche Verschnitt genau halb so groß wie das kleinste Teil ist. Zum Beispiel ist die Lücke nicht mit konstruierbar, sondern erfordert einige Teile mehr.

Die Idee für obige Instanz mit 34 verschiedenen Teilen und einige verwandte Instanzen mit gleicher Lücke, aber einer geringeren Anzahl unterschiedlicher Teile, besteht in der Zusammensetzung mehrerer der oben angegebenen parametrisierten Baustein-Instanzen, zu denen noch vier Teile der Länge hinzugefügt werden. Die Längen der Teile Nr. 4–28 verhalten sich zur Länge des Ausgangsmaterials ungefähr wie , , , und . Betrachtet man annähernd gleich lange Teile als identisch, entsteht eine Modellinstanz, die die Voraussetzungen des zweiten Konstruktionssatzes erfüllt, nämlich

mit der Zusatzbedingung, dass die gemäß verschnittfreien Varianten je einmal nicht benutzt werden dürfen. In Optimallösungen des ganzzahligen Problems (2)–(4) für die Modellinstanz wird der Gesamtverschnitt von neun Längeneinheiten in oder aufgeteilt, und wegen ist die Verschnittbedingung erfüllt. Anstelle dieser Plausibilitätserklärung müssen für die fertig konstruierten Instanzen exakte Verfahren eingesetzt werden, um zu beweisen.

Im Gegensatz zum ersten Konstruktionssatz ist der zweite kaum wiederholt auf eine Instanz anzuwenden, da ein kleines Teil, welches in eine andere Variante verlegt werden kann, zu großen Verschnitt hinterlässt. Dafür konnten mit dem zweiten Konstruktionssatz Lücken bis aufgebaut werden; mit dem ersten wurden es .

Um die Anzahl notwendiger verschiedener Teilelängen zu reduzieren und dennoch dieselbe Lücke zu erhalten, könnte man versuchen, die entsprechenden Baustein-Instanzen geeignet zu verändern. So entstand die Instanz aus im Wesentlichen dadurch, dass gleiche Teilelängen erzwungen wurden. Dies stößt jedoch auf Hindernisse, wie folgendes Lemma aus[17] zeigt:

Lemma: In der Instanz mit seien die Zuschnittvarianten , , , , und zulässig. Dann gilt , , , , . Gilt außerdem , so folgt , , , und .

Minimale Instanzen ohne Ganzzahl-Aufrundungseigenschaft[Bearbeiten | Quelltext bearbeiten]

Wir setzen ohne Beschränkung der Allgemeinheit voraus, dass sämtliche Daten ganzzahlig sind. Dann kann die Minimalität einer Instanz mit immer noch verschieden verstanden werden:

  • minimale Anzahl verschiedener Teilelängen: mit ist so eine Instanz. Wegen musste sein.
  • minimale Länge des Ausgangsmaterials: Bisher (Stand 2007) ist hier nur mit bekannt; bei der Zusatzforderung wäre zum Beispiel zu nennen. Ob auch kleinere als 16 bzw. 18 möglich sind, ist noch offen. Im Teilbarkeitsfall wird .
  • minimale Anzahl insgesamt zuzuschneidender Teile oder anders ausgedrückt, minimale Teilezahl im Bin-Pack-Problem: Man kann mit einer längeren Fallunterscheidung zeigen, dass mindestens fünf Teile benötigt werden und in diesem Falle wird. Entsprechende Instanzen sind und , jeweils mit .

Online-Optimierung[Bearbeiten | Quelltext bearbeiten]

Bei Online-Optimierungsproblemen werden die Daten erst im Laufe der Optimierung bekanntgegeben, zum Beispiel wenn kontinuierlich ein Prozess optimal gesteuert werden soll. In so einem Falle wird nicht nur verlangt, eine möglichst gute zulässige Lösung in Echtzeit zu liefern, sondern die Teile können noch nicht einmal vorher nach ihrer Größe sortiert werden. Mitunter dürfen wenige Teile zurückgestellt werden, so dass zumindest für diese Teile einige Freiheit besteht. Es versteht sich von selbst, dass bei Online-Optimierungsproblemen eine exakte Optimierung ausgeschlossen ist und man sich mit schnellen Heuristiken begnügen muss.

Einen Überblick über Näherungsalgorithmen und ihre Güte gibt zum Beispiel.[18] Einige Ergebnisse aus diesem Übersichtsartikel werden im Folgenden vorgestellt.

Das Problem (2)–(4) werde mit dem Approximationsalgorithmus bearbeitet. Für eine beliebige Instanz sei der ermittelte Zielfunktionswert . Ein absolutes Güteverhältnis im ungünstigsten Fall ergibt sich zu . Für eine asymptotische Güteeinschätzung werden Folgen von Instanzen mit betrachtet. Der entsprechende Limes superior des Verhältnisses werde mit bezeichnet.

Die Heuristik Next Fit (NF), stets nur eine Zuschnitt- oder Packvariante offen zu halten und, falls das nächste Teil nicht mehr hineinpasst, mit der Eröffnung einer neuen Packvariante die letzte zu schließen, also für kein weiteres Teil mehr zu verwenden, ergibt im ungünstigsten Fall für fast als erzielten Zielfunktionswert, etwa wenn immer abwechselnd Teile der Größen und mit sehr kleinem gepackt werden sollen. Folglich ist .

Die Heuristiken First Fit (FF) und Best Fit (BF) sind ungefähr gleich gut; sowohl als auch können sich für verschiedene Instanzen ergeben. Beiden Heuristiken ist gemeinsam, dass alle bereits angefangenen Varianten für noch zu packende Teile verwendet werden dürfen, sofern das Teil passt. Bei First Fit wird die erste passende Packvariante gewählt, bei Best Fit eine mit minimalem verbleibendem freien Platz. Eine besonders ungünstige Folge zu packender Teile für diese Heuristiken liegt beispielsweise vor, wenn wiederholt Teile mit den Längen mit sehr kleinem positivem in der Reihenfolge monoton wachsender Größe gepackt werden sollen. Ein noch ungünstigeres Beispiel enthält[19] mit (beliebig) und . Da gleichzeitig gemäß jenem Artikel und für jede Instanz gilt, folgt .

Any Fit (AF) heiße eine Heuristik, die neue Packvarianten erst beginnt, wenn das nächste zu packende Teil in keine vorherige Variante passt. Für beliebige solche Online-Heuristiken gilt .

Falls immer höchstens Packvarianten gleichzeitig offen sein dürfen, wobei eine endliche Konstante ist, schränkt das die möglichen Heuristiken ein. Unter dieser Bedingung wird für Online-Algorithmen stets .

Um ein besseres asymptotisches Verhalten zu gewährleisten, braucht man folglich Heuristiken, die beliebig viele Varianten offenhalten dürfen und in Abhängigkeit von der Teilegröße bereit sind, eine neue Packvariante zu beginnen, obwohl das nächste zu packende Teil noch in eine bereits vorhandene Variante hineinpasst. Auch ohne Sortierung kann auf diese Weise ein asymptotisches Verhältnis erzielt werden, jedoch existiert kein Online-Algorithmus mit . Bessere Verhältnisse können erzielt werden, wenn die zu packenden Teile relativ klein gegenüber sind.

Werden die Teile vor Optimierungsbeginn nach monoton fallender Größe sortiert, kann nur noch von Offline-Optimierung gesprochen werden. Für die zu First Fit und Best Fit gehörenden entsprechenden Heuristiken gilt . Die absolute Güteeinschätzung ist hier . Mit verfeinerten Algorithmen kann nach der Sortierung das asymptotische Verhältnis beliebig dem Wert 1 genähert werden, wobei weiterhin lineare Zeit erforderlich ist, d. h., für alle gibt es Approximationsalgorithmen mit . Darüber hinaus existieren Approximationsalgorithmen mit polynomialer Komplexität und . Allerdings wächst die absolute Differenz bei solchen Algorithmen stark an.

Die vorstehenden Aussagen beleuchten jeweils das Verhalten im ungünstigsten Fall. Soll der durchschnittliche Fall untersucht werden, sind zusätzliche Annahmen über die eingehenden Zufallsgrößen erforderlich. Unter geeigneten Voraussetzungen sind Aussagen über gewisse Erwartungswerte möglich.

Verallgemeinerungen und Erweiterungen[Bearbeiten | Quelltext bearbeiten]

Falls mehrere verschiedene Materialien mit Längen und Preisen gegeben sind, sind anstelle des Spaltengenerierungsproblems (7) mehrere Rucksackprobleme zu lösen, nämlich mit Rucksackkapazität für . Eine Verbesserung des Zielfunktionswertes der stetigen Relaxation ist möglich, wenn wird und keine Entartung vorliegt. Auch Vorratsbeschränkungen für gewisse Materialien können leicht in das lineare Optimierungsmodell eingearbeitet werden. Um eine zulässige Startlösung zu erhalten, borgt man sich gegebenenfalls fiktives Ausgangsmaterial ausreichender Länge und mit sehr hohem Preis. Wenn trotz Vorratsbeschränkungen das Problem lösbar ist, werden alle fiktiven Materialien durch tatsächlich vorhandene ersetzt. Diese Idee ist auch für Plattenzuschnittprobleme und ähnliche anwendbar.[20]

Nun kann umgekehrt gefragt werden, welche Vorräte verschieden langen Ausgangsmaterials gekauft werden müssen, um mehrere Zuschnittaufträge möglichst billig erledigen zu können. Dabei wird angenommen, dass längere Stücke Material stets teurer sind als kürzere und aus organisatorischen Gründen die Zuschnittaufträge nicht vermischt werden dürfen. Das heißt, aus einem Stück Material dürfen Teile immer nur für einen Auftrag geschnitten werden. Dieses Sortimentsproblem wird einschließlich numerischer Experimente in der Habilitationsschrift[21] behandelt.

Eine andere Verallgemeinerung des eindimensionalen Zuschnittproblems ist das mehrdimensionale Vektorpackproblem, das aus Planungsaufgaben entstehen kann. Anstelle der Zulässigkeitsbedingung (1) werden hier mehrere derartige Bedingungen gleichzeitig gestellt, zum Beispiel dass eine gewisse geometrische Länge und zugleich ein bestimmtes Gesamtgewicht der gepackten Teile nicht überschritten werden dürfen. Ebenso könnte auch die Zeit zu einer derartigen Nebenbedingung führen.

Das Streifenpackproblem stellt eine weitere aus Planungsproblemen entstehende Verallgemeinerung des eindimensionalen Zuschnittproblems dar. Die Aufgabe besteht darin, in ein Rechteck der Abmessungen mit fester Breite und möglichst kleiner Höhe nicht drehbare kleinere Rechtecke mit gegebenen Ausdehnungen und Bedarfszahlen überlappungsfrei zu packen. Wären die Höhen aller anzuordnenden Rechtecke gleich, handelte es sich um das eindimensionale Zuschnittproblem. Eine unmittelbare Anwendung des Streifenpackproblems besteht in der Planung mit einer begrenzt verfügbaren Ressource, so dass nach möglichst kurzer Zeit eine Liste von Aufträgen, die die Ressource benötigen, vollständig abgearbeitet ist.

Eine völlig andere Erweiterung des eindimensionalen Zuschnittproblems liegt vor, wenn wegen begrenzten Platzes neben der Zuschnittanlage bei einem Großauftrag gefordert wird, dass stets höchstens verschiedene Teilesorten in Bearbeitung sind, wobei die positive ganze Zahl fest vorgegeben ist. Bevor also die -te Sorte begonnen werden kann, muss eine andere Teilesorte abgeschlossen worden sein. Gesucht wird zusätzlich zu den Zuschnittvarianten eine Reihenfolge, die dafür sorgt, dass möglichst wenig Material verbraucht und die Zusatzbedingung eingehalten wird.

Ein Überblick über eine Vielzahl weiterer Pack- und Zuschnittprobleme, für die das eindimensionale Problem (2)–(4) auch als Relaxation dienen kann, wird unter anderem in[22] gegeben.

Das "Zuschnittproblem mit Muster-Minimierung" ("cutting stock problem with pattern minimization") ist eine Erweiterung des klassischen Zuschnittproblems. Die Erweiterung "Muster-Minimierung" bedeutet, dass neben dem Rohmaterialverbrauch zusätzlich die Anzahl der verschiedenen verwendeten Zuschnittsvarianten minimiert werden soll. Dieses Problem tritt auf, wenn für jede Zuschnittsvariante einmalige Produktionskosten (Rüstkosten) anfallen, unabhängig davon, wie oft die Variante produziert wird, z. B. wenn für jede Variante, ein Rohr in mehrere Teilstücke zu zersägen, eine eigene Zuschnittschablone benötigt wird. Bezeichnet die Kosten für ein Stück Rohmaterial sowie die einmaligen Kosten, die für jede Zuschnittsvariante anfallen, muss hier an Stelle der Gleichung (2) folgender Wert minimiert werden:

(8)

Dieses Problem gilt seit den 1960ern als ungelöst. Die Artikel[23][24] befassen sich mit dem Problem, indem sie die nicht stetige Funktion (8) durch stetige Funktionen approximieren und mit nicht-linearer Optimierung arbeiten.

Zur Geschichte[Bearbeiten | Quelltext bearbeiten]

Bereits 1939 gab Leonid Witaljewitsch Kantorowitsch ein ganzzahliges Modell für das eindimensionale Zuschnittproblem an, aber die zu seinem Modell gehörende stetige Relaxation ist sehr schwach; sie liefert nur die Materialschranke. Nachdem bis 1960 die Grundlagen der linearen Optimierung, darunter das revidierte Simplexverfahren, bereitgestellt worden waren, veröffentlichten Gilmore und Gomory bereits 1961/63 das Lösungsverfahren für die stetige Relaxation, nämlich die Simplexmethode mit der Spaltengenerierung zu kombinieren. Damit konnten, ausreichend Rechenzeit vorausgesetzt, für nicht zu große Instanzen (fast) optimale Lösungen ermittelt werden. Da aber die Rechenzeit für größere Instanzen inakzeptabel hoch wird, weil viele Simplexschritte notwendig sind und viele Rucksackprobleme gelöst werden müssen, interessierte man sich auch für schnelle Heuristiken und ihre Qualitäten. Dies geschah in den 1970er Jahren. Da immer wieder , also Ganzzahl-Aufrundungseigenschaft beobachtet wurde, drängte sich eine entsprechende Vermutung auf, bis Odile Marcotte 1985 anhand des 3-Matching-Problems nachweisen konnte, dass es Instanzen des eindimensionalen Zuschnittproblems mit Lücke geben müsse.[25] 1986 veröffentlichte Frau Marcotte ein konkretes Beispiel.[26] Da dieses Beispiel aber (ganze) Zahlen zwischen einer und zehn Millionen enthielt, wurde gesagt, so etwas käme in der Praxis nicht vor. Als Fieldhouse 1990 die wesentlich einfachere Instanz angab,[27] sah man zwar ein, dass Derartiges durchaus in der Praxis vorkommt, aber es handele sich um singuläre Einzelfälle. Mit der Angabe unendlich vieler, paarweise nichtäquivalenter Instanzen mit Differenz fiel die falsche These über die Ganzzahl-Aufrundungseigenschaft im eindimensionalen Zuschnittproblem endgültig. Noch Ende des 20. Jahrhunderts gelang es, für die exakte Lösung des ganzzahligen Problems (2)–(4) als Alternative zum Verzweigungsverfahren das Schnittebenenverfahren I von Gomory erfolgreich anzupassen.[28] Inzwischen wurde das Verfahren weiterentwickelt zu Branch and price and cut.

Einige noch offene Fragen[Bearbeiten | Quelltext bearbeiten]

Neben den Fragestellungen aus der Komplexitätstheorie besteht zum eindimensionalen Zuschnittproblem noch einiger Forschungsbedarf, zum Beispiel:

  • Bezeichnet die Menge aller Instanzen des eindimensionalen Zuschnittproblems mit höchstens verschiedenen Teilelängen, fragen wir nach . Wie kann möglichst scharf abgeschätzt werden?
  • Die gleichen Fragen stellen wir für Spezialfälle wie den Teilbarkeitsfall oder wenn eine ganze Zahl mit für alle existiert oder wenn kein Teil länger als die Hälfte des Ausgangsmaterials ist.
  • Wenn insgesamt genau fünf Teile zuzuschneiden sind, d. h. , kann man ausrechnen, dass von allen diesen Instanzen der Anteil der Instanzen mit Lücke ungefähr ein Zwanzigtausendstel beträgt. Wie groß ist der Anteil, wenn mehr Teile zuzuschneiden sind?
  • Wodurch sind diejenigen Instanzen gekennzeichnet, die eine kleinere Differenz aufweisen als die zugehörigen residualen Instanzen?
  • Für welche minimalen bei durchgängig ganzzahligen Daten kann werden? Sind für kleinere als 30, 18 und 16 möglich?

Quellenangaben[Bearbeiten | Quelltext bearbeiten]

  1. G. Scheithauer: Zuschnitt- und Packungsoptimierung – Problemstellungen, Modellierungstechniken, Lösungsmethoden. Vieweg + Teubner 2008, S. 59f. ISBN 978-3-8351-0215-6
  2. M. R. Garey, D. S. Johnson: "Strong" NP-Completeness Results: Motivation, Examples, and Implications. Journal of the Association for Computing Machinery, Vol 25, No 3, July 1978, 499–508.
  3. G. Wäscher, T. Gau: Heuristics for the Integer One-dimensional Cutting Stock Problem: a computational study. OR Spektrum 18 (1996) 131–144.
  4. J. Rietz: On the one-dimensional cutting stock problem – minimal non-IRUP instances. 17th Workshop on Discrete Optimization, Siegmundsburg 2006; Jenaer Schriften zur Mathematik und Informatik Math/Inf/06/06, Friedrich-Schiller-Universität Jena 2006, S. 20–23.
  5. G. Scheithauer, J. Terno: Theoretical investigations on the Modified integer Round-Up Property for the one-dimensional cutting stock problem. Oper. Res. Lett. 20 (1997) 93–100.
  6. O. Marcotte: Topics in combinatorial packing and covering. Forschungsbericht 568, School of Oper. Res. and Ind. Eng., Cornell University (Ithaca, NY) 1982.
  7. G. Scheithauer, J. Terno: About the gap between the optimal values of the integer and continuous relaxation in the one-dimensional cutting stock problem. In: Operations Research Proceedings 1991, Springer-Verlag Berlin 1992.
  8. a b c d e f J. Rietz: Untersuchungen zu MIRUP für Vektorpackprobleme. Dissertation, TU Bergakademie Freiberg, 2003.
  9. V. Nica: A general counterexample to the Integer Round-Up property. (Unveröffentlichtes) Manuskript, Abteilung für ökonomische Kybernetik, Ökonomische Akademie, Bukarest 1994.
  10. a b c J. Rietz, G. Scheithauer, J. Terno: Families of non-IRUP instances of the one-dimensional cutting stock problem. Discrete Applied Mathematics 121 (2002) 229–245.
  11. P. C. Gilmore, R. E. Gomory: A linear programming approach to the cutting-stock problem (Part I). Oper. Res. 9 (1961) 849–859.
  12. a b c d J. Rietz, G. Scheithauer, J. Terno: Tighter bounds for the gap and non-IRUP constructions in the one-dimensional cutting stock problem. Optimization 51 (2002) 927–963.
  13. A. A. Farley: A note on bounding a class of linear programming problems. Operations Research Vol. 38, Nr. 5, Sept./Okt. 1990, S. 922f.
  14. C. Nitsche, G. Scheithauer, J. Terno: New cases of the cutting stock problem having MIRUP. Math. Meth. Oper. Res. 48 (1998) 105–115.
  15. G. Scheithauer, J. Terno: The Modified Integer Round-Up Property of the One-Dimensional Cutting Stock Problem. European Journal of Operational Research 84 (1995) 562–571.
  16. G. Scheithauer, J. Terno, A. Müller, G. Belov: Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm. Journal of the Operational Research Society 52 (2001) 1390–1401.
  17. a b J. Rietz, S. Dempe: Large gaps in one-dimensional cutting stock problems. Discrete Applied Mathematics, Vol. 156, Issue 10 (Mai 2008), 1929–1935.
  18. E. G. Coffman jr., M. R. Garey, D. S. Johnson: Approximation algorithms for bin packing: A survey. in: Approximation Algorithms for NP-Hard Problems, D. Hochbaum (ed.), PWS Publishing, Boston 1996, 46–93.
  19. D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, R. L. Graham: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. Vol. 3, No. 4, December 1974, 299–325.
  20. J. Terno, R. Lindemann, G. Scheithauer: Zuschnittprobleme und ihre praktische Lösung. VEB Fachbuchverlag, Leipzig 1987.
  21. O. Holthaus: Kostenorientierte Zuschneideplanung. Entwurf und experimentelle Analyse von Lösungsverfahren für eindimensionale Zuschneide- und Sortimentsprobleme. Shaker Verlag, Aachen 2002. ISBN 3-8322-0087-8
  22. H. Dyckhoff, G. Scheithauer, J. Terno: Cutting and Packing. in: Annotated Bibliographies in Combinatorial Optimization, herausgegeben von M. Dell'Amico, F. Maffioli und S. Martello, John Wiley & Sons Ltd., 1997, S. 393–412.
  23. S. Umetani, M. Yagiura, and T. Ibaraki (2003). One dimensional cutting stock problem to minimize the number of different patterns. European Journal of Operational Research 146, 388–402.
  24. A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk and S. Naidoo (1996). Setup minimizing conditions in the trim loss problem. European Journal of Operational Research 95:631-640.
  25. O. Marcotte: The cutting stock problem and integer rounding. Mathematical Programming 33 (1985) 82–92.
  26. O. Marcotte: An instance of the cutting stock problem for which the rounding property does not hold. Operations Research Letters 4/5 (1986) 239–243.
  27. M. Fieldhouse. The duality gap in trim problems. SICUP-Bulletin No. 5, 1990.
  28. A. Müller: Anwendung des Schnittebenenverfahrens auf das eindimensionale Zuschnittproblem. Diplomarbeit, Technische Universität Dresden 1998.

Weblinks[Bearbeiten | Quelltext bearbeiten]

  • Auf der Seite der Interessengruppe Cutting and Packing an der TU Dresden finden Interessenten unter anderem 53 schwierige Testbeispiele ohne Ganzzahl-Aufrundungseigenschaft zum eindimensionalen Zuschnittproblem.
  • winvedaga: Lösung des Eindimensionalen Zuschnittproblems mit Hilfe des Approximationsalgorithmus