Das eindimensionale Zuschnittproblem (englisch one-dimensional cutting stock problem) ist ein NP-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
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 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äß 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
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
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 . 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 Simplex-Verfahren 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: 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
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 (englisch modified integer round-up property, MIRUP) geprägt. Eine Instanz weist diese Eigenschaft auf, wenn gilt. 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. Ein einfacherer Beweis von Guntram Scheithauer und Johannes Terno wurde in der Dissertation von Jürgen Rietz 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 .
- Für beliebiges sei das kleinste gemeinsame Vielfache von (oder ein Mehrfaches davon). Dann besitzt die Instanz eine Lücke .
- Sei beliebig und . Dann gilt für die Instanz .
Lösung der stetigen Relaxation 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.
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. Simplex-Verfahren#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
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
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
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:
- Löse die Relaxation (6) und trenne den ganzzahligen Anteil ab.
- Es verbleibe eine residuale Instanz . Wähle von den verbliebenen Varianten eine mit maximaler Häufigkeit. Diese Variante sei .
- Bei streiche überzählige Teile aus .
- Ergänze, wenn möglich, weitere noch zuzuschneidende Teile in .
- Falls der Nullvektor ist, ist nichts mehr zu schneiden, halt.
- Solange es möglich ist, ersetze in jeweils ein Teil durch ein größeres noch zu schneidendes.
- 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
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, die auf der Dualitätstheorie der linearen Optimierung beruht.
Das zur stetigen Relaxation (5) gehörige duale Optimierungsproblem lautet
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
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 die Dissertation von Jürgen Rietz, während die diesbezüglichen Beiträge von Rietz et al. 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
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
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