Eindimensionales Zuschnittproblem

Das eindimensionale Zuschnittproblem (englisch one-dimensional cutting s​tock problem) i​st ein NP-schweres ganzzahliges lineares Optimierungsproblem m​it dem Ziel, eindimensionale Teile i​n vorgegebenen Bedarfszahlen a​us möglichst w​enig Stücken Material gegebener Länge zuzuschneiden. Dieses Problem verdankt s​eine große Bedeutung a​uch dem Umstand, d​ass es a​ls Relaxation für kompliziertere mehrdimensionale Pack- u​nd Zuschnittprobleme verwendet wird, z​um Beispiel b​eim Containerbeladeproblem m​it Quadern, w​enn man s​ich alle Teile i​n Streifen zerlegt denkt.

Problemstellung und grundlegende Definitionen

Gegeben ist eine unbegrenzte Zahl von Stücken eindimensionalen Rohmaterials vorgegebener Länge ${\displaystyle L\in \mathbb {R} ^{+}}$. Daraus sollen ${\displaystyle b_{i}\in \mathbb {N} ^{+}}$ Teile der Länge ${\displaystyle l_{i}\in \mathbb {R} ^{+}}$ zugeschnitten werden, mit ${\displaystyle (i=1,2,\dots ,m);}$ insgesamt also ${\displaystyle \sum _{i=1}^{m}b_{i}}$ 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 ${\displaystyle b_{i}}$ sehr klein, spricht man auch vom (eindimensionalen) Behälterproblem (Bin-Pack-Problem).

Unmittelbare Anwendungen s​ind zum Beispiel d​as Zuschneiden v​on Rohren o​der das Abspeichern v​on nicht teilbaren u​nd nicht weiter komprimierbaren Dateien a​uf möglichst w​enig Datenträgern einheitlicher Kapazität. Die Verallgemeinerung a​uf mehrere verschiedene Längen a​n Rohmaterial w​ird später behandelt.

Soll eine bestimmte Schnittbreite ${\displaystyle s>0}$ berücksichtigt werden, ist dies möglich, indem alle Längen, also ${\displaystyle L}$ und ${\displaystyle l_{i}}$ (${\displaystyle i=1,2,\dots ,m}$) um ${\displaystyle s}$ vergrößert werden. Damit wird das Problem auf eines mit Schnittbreite 0 zurückgeführt.

Zunächst werden die Längen ${\displaystyle l_{i}}$ und die Bedarfszahlen ${\displaystyle b_{i}}$ (für ${\displaystyle i\in I:=\{1,2,\dots ,m\}}$) zu Vektoren ${\displaystyle \mathbf {l} }$ und ${\displaystyle \mathbf {b} }$ zusammengefasst. Die Zusammenfassung aller Daten zu einer Instanz erfolgt als Quadrupel ${\displaystyle (m;L;{\mathbf {l} };{\mathbf {b} })}$. 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 ${\displaystyle {\mathbf {a} }\in {\mathbb {Z} }_{+}^{m}}$ ist genau dann zulässig, wenn

${\displaystyle {\mathbf {a} }^{\top }{\mathbf {l} }\leq L}$

(1)

gilt. Die Indexmenge aller zulässigen Varianten ${\displaystyle \mathbf {a} ^{j}}$  sei mit ${\displaystyle J\ }$ bezeichnet. Damit lautet das ganzzahlige lineare Optimierungsproblem:

${\displaystyle z:=\sum _{j\in J}x_{j}\to \min !}$

(2)

bei

${\displaystyle \sum _{j\in J}x_{j}*{\mathbf {a} }^{j}={\mathbf {b} }}$

(3)

${\displaystyle x_{j}\in {\mathbb {Z} }_{+}}$ für alle ${\displaystyle j\in J}$

(4)

Dieses Problem ist stets lösbar, wenn für alle Teilelängen ${\displaystyle l_{i}\leq L}$ 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 d​ie Anzahl d​er zulässigen Varianten u​nd damit d​er Variablen i​n der Aufgabe (2)–(4) o​ft sehr groß ist, w​urde auch n​ach alternativen Modellen gesucht. Ein solches besteht u. a. i​n der Formulierung a​ls Optimierung e​ines Flusses i​n einem Netzwerk. Jenes Fluss-Modell stellt s​ich als äquivalent z​ur obigen Problemformulierung heraus. Wegen Einzelheiten s​ei z. B. auf[1] verwiesen.

Eine zulässige Zuschnittvariante ${\displaystyle \mathbf {a} }$ heißt eigentlich, wenn ${\displaystyle {\mathbf {a} }\leq \mathbf {b} }$ 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 ${\displaystyle {\mathcal {N}}P}$-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 ${\displaystyle {\mathcal {N}}P}$vollständig. Gemäß[2] ist das eindimensionale Bin-Pack-Problem sogar stark ${\displaystyle {\mathcal {N}}P}$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 ${\displaystyle z_{D}}$ der ganzzahligen Optimierungsaufgabe stellt die Materialschranke

${\displaystyle z_{M}:={\mathbf {l} }^{\top }{\mathbf {b} }/L}$

dar. Allerdings ist diese Schranke meist zu ungenau, denn die Differenz ${\displaystyle z_{D}-z_{M}}$ 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:

${\displaystyle \sum _{j\in J}x_{j}\to \min !}$  bei ${\displaystyle \sum _{j\in J}x_{j}*{\mathbf {a} }^{j}={\mathbf {b} },\;x_{j}\in {\mathbb {R} }_{+}}$ für alle ${\displaystyle j\in J}$

(5)

• Einschränkung auf eigentliche Varianten:

${\displaystyle \sum _{j\in J}x_{j}\to \min !}$  bei ${\displaystyle \sum _{j\in J}x_{j}*{\mathbf {a} }^{j}={\mathbf {b} },\;x_{j}\in {\mathbb {R} }_{+}}$ für alle ${\displaystyle j\in J}$ mit ${\displaystyle x_{j}=0}$, falls ${\displaystyle {\mathbf {a} }^{j}\not \leq \mathbf {b} }$

(6)

Die optimalen Zielfunktionswerte beider Relaxationen seien mit ${\displaystyle z_{C}}$ und ${\displaystyle z_{E}}$ bezeichnet. Dann zeigt man leicht ${\displaystyle z_{M}\leq z_{C}\leq z_{E}\leq z_{D}}$. Von besonderem theoretischem Interesse ist die Lücke

${\displaystyle \Delta :=z_{D}-z_{C}}$.

Es stellt sich heraus, dass es ${\displaystyle {\mathcal {N}}P}$schwer ist, ${\displaystyle \Delta <1}$ 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 ${\displaystyle \mathbf {a} }$ höchstens ${\displaystyle \left\lfloor \min \left\{b_{i}/a_{i}:i\in I,\,a_{i}>0\right\}\right\rfloor }$-mal verwendet werden. Doch auch für diese kompliziertere Relaxation konstruiert man leicht Instanzen, bei denen die Schrankenverschärfung versagt.

Beispiel

Beispielinstanz zum eindimensionalen Zuschnittproblem mit Optimallösung der stetigen Relaxation

Für die Instanz ${\displaystyle E:=(7;210;(105,74,73,70,68,64,42)^{\top };(1,1,1,2,1,1,2)^{\top })}$ 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 ${\displaystyle (0,1,0,1,0,1,0)^{\top }}$, 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 ${\displaystyle z_{M}=304/105<z_{C}=2,9<z_{E}=3+1/15<z_{D}=4}$. Die Instanz ${\displaystyle E}$ ergibt die für den Fall, dass kein Teil mehr als die Hälfte des Ausgangsmaterials ausmacht, größte bisher bekannte Lücke ${\displaystyle \Delta =11/10}$ (Stand 2007).

Vervielfacht man die Bedarfszahlen mit elf oder ersetzt man sie durch den neuen Vektor ${\displaystyle {\tilde {\mathbf {b} }}=(3,3,3,3,3,3,7)^{\top }}$, ergibt sich wieder die Lücke ${\displaystyle \Delta =1{,}1}$, jedoch wird für die abgeänderte Instanz ${\displaystyle z_{C}=z_{E}}$. Nur noch die Verschärfung der Relaxation (6) verrät ${\displaystyle z_{D}>z_{C}+1}$. Doch eine geringfügige Verkürzung einzelner der gemäß ${\displaystyle {\tilde {\mathbf {b} }}}$ zu schneidenden 25 Teile ermöglicht, auch die Verschärfung der Relaxation (6) wirkungslos zu machen.

Äquivalente Instanzen

Zwei Instanzen ${\displaystyle E:=(m;L;{\mathbf {l} };{\mathbf {b} })}$ und ${\displaystyle {\bar {E}}:=\left({\bar {m}};{\bar {L}};{\bar {\mathbf {l} }};{\bar {\mathbf {b} }}\right)}$ heißen äquivalent, wenn ${\displaystyle m={\bar {m}}}$ und ${\displaystyle {\mathbf {b} }={\bar {\mathbf {b} }}}$ 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 ${\displaystyle \varepsilon >0}$ 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 ${\displaystyle \mathbf {a} }$ heißt maximal, wenn ${\displaystyle L-{\mathbf {l} }^{\top }{\mathbf {a} }<\min _{i\in I}l_{i}}$ gilt, also der Verschnitt kleiner als das kleinste zuzuschneidende Teil ist. Um zu prüfen, ob die Instanzen ${\displaystyle E}$ und ${\displaystyle {\bar {E}}}$ bei ${\displaystyle m={\bar {m}}\land {\mathbf {b} }={\bar {\mathbf {b} }}}$ ä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 ${\displaystyle E}$ maximale Variante auch für ${\displaystyle {\bar {E}}}$ maximal ist, wie das Gegenbeispiel ${\displaystyle E:=\left(2;9;(5,3)^{\top };{\mathbf {b} }\right)}$, ${\displaystyle {\bar {E}}:=\left(2;10;(5,3)^{\top };{\mathbf {b} }\right)}$ zeigt.

Beispiel zur Äquivalenz: Thomas Gau fand bei Testrechnungen die Instanz ${\displaystyle \left(5;10\,000;(5000,3750,3250,3001,2000)^{\top };(1,1,1,1,2)^{\top }\right)}$ mit Lücke ${\displaystyle 16/15}$.[3] Ersetzt man die 3001 durch 3125, ergibt sich eine äquivalente Instanz, da alle anderen Längen durch 250 teilbar sind und die Variante ${\displaystyle (0,0,0,3,0)^{\top }}$ 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 ${\displaystyle \left(5;80;(40,30,26,25,16)^{\top };(1,1,1,1,2)^{\top }\right)}$. Eine weitere äquivalente Instanz entsteht hieraus durch Multiplikation aller Längen mit ${\displaystyle 3/4}$ und geeignetes Runden, nämlich ${\displaystyle \left(5;60;(30,22,20,19,12)^{\top };(1,1,1,1,2)^{\top }\right)}$.

Um nachzuweisen, d​ass keine äquivalente Instanz m​it durchgängig ganzzahligen Daten u​nd kleinerer Länge d​es Ausgangsmaterials existiert, k​ann das d​uale Simplex-Verfahren o​hne Zielfunktion eingesetzt werden. Drei Typen v​on Ungleichungen s​ind von d​en äquivalenten Instanzen z​u erfüllen:

• ${\displaystyle l_{i}\geq l_{i+1}}$ für ${\displaystyle i\in I\setminus \{m\}}$ aufgrund der Sortierung
• ${\displaystyle L-{\mathbf {a} }^{\top }{\mathbf {l} }\geq 0}$ für jede maximale Variante ${\displaystyle \mathbf {a} }$
• ${\displaystyle {\mathbf {u} }^{\top }{\mathbf {l} }-L\geq 1}$ für jede unzulässige Variante ${\displaystyle {\mathbf {u} }\in {\mathbb {Z} }_{+}^{m}}$ 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 ${\displaystyle l_{i}}$ oder ${\displaystyle L}$ gehört. Zuletzt bleiben für die ${\displaystyle m+1}$ gesuchten Längen nur ${\displaystyle m+1}$ 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 ${\displaystyle \left(4;210;(105,70,42,30)^{\top };{\mathbf {b} }\right)}$ äquivalenten Instanzen mit durchgängig ganzzahligen Längen, wobei ${\displaystyle b_{i}>0}$ für alle ${\displaystyle i\in I}$ gilt. Offensichtlich ist ${\displaystyle \max \left\{2l_{1},3l_{2},5l_{3},7l_{4}\right\}\leq L}$ zu fordern. Neben den Unzulässigkeitsbedingungen ${\displaystyle l_{1}+l_{2}+l_{3}>L}$ und ${\displaystyle 2l_{2}+l_{3}+l_{4}>L}$ 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 ${\displaystyle z_{1},z_{2},z_{3},z_{4},u_{1},u_{2}}$, bezeichnet. Sie sind als Differenz ganzzahliger Größen ebenfalls ganzzahlig. Folgendes Schema entsteht:

${\displaystyle {\begin{array}{c|*{6}r}&1&z_{2}&z_{3}&z_{4}&u_{1}&u_{2}\\\hline L&105&70&21&15&0&105\\l_{1}&50&33&10&7&1&49\\l_{2}&35&23&7&5&0&35\\l_{3}&21&14&4&3&0&21\\l_{4}&15&10&3&2&0&15\\z_{1}&5&4&1&1&-2&7\\\end{array}}}$

Demzufolge darf die Schlupfvariable ${\displaystyle u_{1}}$ nicht beliebig unabhängig von den anderen erhöht werden. Tauscht man ${\displaystyle u_{1}}$ gegen ${\displaystyle z_{1}}$, geht die Ganzzahligkeit von ${\displaystyle l_{1}}$ verloren, falls alle Schlupfvariablen der Nichtbasis danach auf 0 gesetzt werden. Insgesamt ergibt sich, dass ${\displaystyle L}$ und ${\displaystyle l_{2},l_{3},l_{4}}$, mit den vier Parametern ${\displaystyle z_{2},z_{3},z_{4},u_{2}\in \mathbb {N} }$ beschrieben werden können, während ${\displaystyle 50+33z_{2}+10z_{3}+7z_{4}+49u_{2}\leq l_{1}\leq 52{,}5+35z_{2}+10{,}5z_{3}+7{,}5z_{4}+52{,}5u_{2}}$ 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 ${\displaystyle l_{1}=l_{2}=l_{3}=5}$ und ${\displaystyle b_{1}=b_{2}=b_{3}=1}$ 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 ${\displaystyle L}$ zu packen ist, gleichwertig zum oben eingeführten eindimensionalen Zuschnittproblem (2)–(4).

Der Teilbarkeitsfall; modifizierte Ganzzahl-Aufrundungseigenschaft

Eine zulässige Variante heißt elementar, wenn sie nur eine Teilesorte enthält, also von der Gestalt ${\displaystyle k*{\mathbf {e} }^{i}}$ mit ${\displaystyle k\leq L/l_{i},\;k\in \mathbb {N} }$ ist, wobei ${\displaystyle {\mathbf {e} }^{i}}$ den ${\displaystyle i}$-ten Basis-Einheitsvektor des ${\displaystyle {\mathbb {R} }^{m}}$ bezeichnet, ${\displaystyle i\in I}$.

Der Teilbarkeitsfall liegt vor, wenn ${\displaystyle L}$ ganzzahliges Vielfaches jeder Teilelänge ist. Dann ergibt sich sofort ${\displaystyle z_{C}=z_{M}}$, indem in der stetigen Relaxation (5) nur maximale elementare Varianten verwendet werden.

Beispiel: Die Instanz ${\displaystyle (3;132;(44,33,12)^{\top };(2,3,6)^{\top })}$ besitzt für die Relaxation (5) wegen ${\displaystyle 132=3*44=4*33=11*12}$ den optimalen Zielfunktionswert ${\displaystyle z_{C}={\frac {2}{3}}+{\frac {3}{4}}+{\frac {6}{11}}={\frac {259}{132}}}$. Hier gilt aber ${\displaystyle z_{D}=3}$, 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 ${\displaystyle \Delta =z_{D}-z_{C}}$, nämlich ${\displaystyle 137/132\approx 1{,}0379}$ (Stand 2007).

Für obige Instanz gilt die Ganzzahl-Aufrundungseigenschaft ${\displaystyle z_{D}=\lceil z_{C}\rceil }$ nicht. Da alle bisherigen Erfahrungen darauf schließen ließen, dass die Lücke ${\displaystyle \Delta }$ 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 ${\displaystyle z_{D}\leq \lceil z_{C}\rceil +1}$ 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 ${\displaystyle E}$ des Teilbarkeitsfalls gilt ${\displaystyle \Delta (E)=z_{D}(E)-z_{C}(E)<7/5}$. Sind sämtliche Teile größer als ${\displaystyle 1/19}$ des Ausgangsmaterials, gilt sogar ${\displaystyle \Delta (E)<5/4}$.

Das Vorhandensein unendlich vieler, paarweise nicht äquivalenter Instanzen des Teilbarkeitsfalls mit ${\displaystyle \Delta >1}$ folgt unter anderem aus diesen Aussagen:

• Seien ${\displaystyle k_{1},k_{2},\dots ,k_{m-1}}$ paarweise teilerfremde ganze Zahlen mit ${\displaystyle 1<k_{1}<\cdots <k_{m-1},m\geq 3}$ und ${\displaystyle k_{m}:=\prod \limits _{i=1}^{m-1}k_{i}-1}$. Für alle ${\displaystyle i\in I\setminus \{m\}}$ sei ${\displaystyle b_{i}=k_{i}-1}$, und es gebe keine Lösung der ganzzahligen Aufgabe (2)–(4), in der diese Teile (mit den Bedarfszahlen ${\displaystyle b_{i}}$) in höchstens ${\displaystyle m-2}$ Varianten untergebracht werden. Ferner seien ${\displaystyle b_{m}:=\left\lfloor k_{m}*\sum \limits _{i=1}^{m-1}{\frac {1}{k_{i}}}\right\rfloor ,L:=\prod \limits _{i\in I}k_{i}}$ und ${\displaystyle l_{i}:={\frac {L}{k_{i}}}}$ für ${\displaystyle i\in I}$. Die so festgelegte Instanz ${\displaystyle (m;L;{\mathbf {l} };{\mathbf {b} })}$ besitzt eine Lücke ${\displaystyle \Delta =1+{\frac {1}{k_{m}}}*\left(\left\lceil \sum \limits _{i=1}^{m-1}{\frac {1}{k_{i}}}\right\rceil -\sum \limits _{i=1}^{m-1}{\frac {1}{k_{i}}}\right)>1}$.[9]
• Für beliebiges ${\displaystyle p\in {\mathbb {N} }\setminus \{0\}}$ sei ${\displaystyle L}$ das kleinste gemeinsame Vielfache von ${\displaystyle 3p,\,3p+1,\,9p+2}$ (oder ein Mehrfaches davon). Dann besitzt die Instanz ${\displaystyle \left(3;L;\left({\frac {L}{3p}},{\frac {L}{3p+1}},{\frac {L}{9p+2}}\right)^{\top };(3p-1,3p,6)^{\top }\right)}$ eine Lücke ${\displaystyle \Delta >1}$.[10]
• Sei ${\displaystyle p\in {\mathbb {N} }\setminus \{0\}}$ beliebig und ${\displaystyle L:=(6p+2)*(6p+3)*(6p+5)}$. Dann gilt ${\displaystyle \Delta >1}$ für die Instanz ${\displaystyle \left(3;L;\left({\frac {L}{6p+2}},{\frac {L}{6p+3}},{\frac {L}{6p+5}}\right)^{\top };(6p+1,3p+3,3p+2)^{\top }\right)}$.[8]

Lösung der stetigen Relaxation

Schon für relativ kleine Parameter ${\displaystyle m}$ ist die Mächtigkeit der Menge ${\displaystyle J}$ 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 ${\displaystyle z={\mathbf {c} }^{\top }\mathbf {x} }$ gehörenden Koeffizienten in Basis- und Nichtbasisanteil ${\displaystyle {\mathbf {c} }_{B}}$ bzw. ${\displaystyle {\mathbf {c} }_{N}}$ aufgeteilt, ebenso die Nebenbedingungen in der Weise ${\displaystyle {\mathbf {B} \mathbf {x} }_{B}+{\mathbf {N} \mathbf {x} }_{N}=\mathbf {b} }$, wobei die Basismatrix ${\displaystyle \mathbf {B} }$ regulär ist. Löst man nach ${\displaystyle {\mathbf {x} }_{B}}$ auf und setzt dies in die Zielfunktion ein, so ergibt sich ${\displaystyle z={\mathbf {c} }_{B}^{\top }{\mathbf {B} }^{-1}{\mathbf {b} }+({\mathbf {c} }_{N}^{\top }-{\mathbf {c} }_{B}^{\top }{\mathbf {B} }^{-1}{\mathbf {N} }){\mathbf {x} }_{N}}$. 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 ${\displaystyle \mathbf {a} }$ mit ${\displaystyle {\bar {c}}:=1-{\mathbf {c} }_{B}^{\top }{\mathbf {B} }^{-1}{\mathbf {a} }<0}$ existiert. Für diese Spaltengenerierung ist somit jeweils ein Rucksackproblem

${\displaystyle {\mathbf {g} }^{\top }{\mathbf {a} }\to \max !}$   bei   ${\displaystyle {\mathbf {l} }^{\top }{\mathbf {a} }\leq L,\;{\mathbf {a} }\in {\mathbb {Z} }_{+}^{m}}$

(7)

zu lösen, wobei ${\displaystyle {\mathbf {g} }^{\top }={\mathbf {c} }_{B}^{\top }{\mathbf {B} }^{-1}}$ gilt. Eine einfache Rechenkontrolle besteht in ${\displaystyle z={\mathbf {c} }_{B}^{\top }({\mathbf {B} }^{-1}{\mathbf {b} })={\mathbf {g} }^{\top }\mathbf {b} }$.

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 ${\displaystyle \mathbf {a} }$ abgespeichert wurde, für die ${\displaystyle {\mathbf {g} }^{\top }{\mathbf {a} }>1}$ 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 ${\displaystyle 2:2:1}$. Die Materialausnutzung ist zu maximieren. Das bedeutet, hier ist eine Optimallösung der stetigen Relaxation (5) von der Instanz ${\displaystyle \left(3;11;(6,4,1)^{\top };(2,2,1)^{\top }\right)}$ gesucht. Für die erste Basis werden maximale elementare Varianten gewählt, das sind ${\displaystyle {\mathbf {a} }^{1}=(1,0,0)^{\top }={\mathbf {e} }^{1}}$, ${\displaystyle {\mathbf {a} }^{2}=(0,2,0)^{\top }=2{\mathbf {e} }^{2}}$ und ${\displaystyle {\mathbf {a} }^{3}=(0,0,11)^{\top }=11{\mathbf {e} }^{3}}$, so dass ${\displaystyle \mathbf {B} }$ 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 ${\displaystyle (\bigstar )}$ gekennzeichnet. Aus Gründen der einfacheren Programmierung wurden die rechten Seiten und der Vektor ${\displaystyle {\mathbf {g} }^{\top }}$ in der ersten Spalte bzw. Zeile untergebracht. Ganz rechts steht jeweils die transformierte neue Spalte, bestehend aus ${\displaystyle {\bar {c}}}$ und ${\displaystyle -{\mathbf {B} }^{-1}\mathbf {a} }$.

${\displaystyle {\begin{array}{l|c|ccc|c||l|c|ccr|c||l|c|rcr}S_{0}&1&&&&&S_{1}&1&&&&&S_{2}&1\\\hline z&{\frac {34}{11}}&1&{\frac {1}{2}}&{\frac {1}{11}}&-{\frac {13}{22}}&z&{\frac {5}{2}}&1&{\frac {1}{2}}&-{\frac {1}{2}}&-{\frac {1}{2}}&z&2&{\frac {1}{2}}&{\frac {1}{2}}&0\\[1mm]x_{1}&2&1&&&-1&x_{1}&1&1&&-1&-1\,\bigstar &x_{5}&1&1&&-1\\[1mm]x_{2}&1&&{\frac {1}{2}}&&-{\frac {1}{2}}&x_{2}&{\frac {1}{2}}&&{\frac {1}{2}}&-{\frac {1}{2}}&-{\frac {1}{2}}&x_{2}&0&-{\frac {1}{2}}&{\frac {1}{2}}&0\\[1mm]x_{3}&{\frac {1}{11}}&&&{\frac {1}{11}}&-{\frac {1}{11}}\,\bigstar &x_{4}&1&&&1&0&x_{4}&1&&&1\\\end{array}}}$

${\displaystyle {\mathbf {a} }^{4}=(1,1,1)^{\top }}$   ${\displaystyle {\mathbf {a} }^{5}=(1,1,0)^{\top }}$    optimal

Die Varianten ${\displaystyle {\mathbf {a} }^{4}}$ und ${\displaystyle {\mathbf {a} }^{5}}$ sind folglich im Verhältnis ${\displaystyle 1:1}$ zu schneiden. Beim letzten Austausch war ${\displaystyle x_{1}}$ (und nicht ${\displaystyle x_{2}}$) 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 ${\displaystyle g_{i}}$ ${\displaystyle (i\in I)}$ 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

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 ${\displaystyle z_{D}}$. 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 ${\displaystyle {\mathbf {x} }^{C}}$ eine mittels Simplexverfahren ermittelte optimale Basislösung der stetigen Relaxation (5). Ersetzt man in der Instanz ${\displaystyle E:=(m;L;{\mathbf {l} };{\mathbf {b} })}$ den Vektor der Bedarfszahlen durch ${\displaystyle {\mathbf {b} }-\sum _{j\in J}\lfloor x_{j}^{C}\rfloor *{\mathbf {a} }^{j}}$, entsteht eine sogenannte residuale Instanz ${\displaystyle E^{(r)}}$. Dabei dürfen durchaus auch Nullen im Bedarfsvektor auftreten. Bei vielen Abschätzungen der Lücke ${\displaystyle \Delta }$ hilft folgendes

Lemma: Seien ${\displaystyle p,q\in {\mathbb {R} },p\geq 1}$ beliebig. Dann gilt für residuale Instanzen ${\displaystyle E^{(r)}}$ die Implikation

${\displaystyle z_{D}\left(E^{(r)}\right)<p*z_{C}\left(E^{(r)}\right)+q\Longrightarrow \Delta \left(E^{(r)}\right)<{\frac {p-1}{p}}*m+{\frac {q}{p}}=m*\left(1-{\frac {1}{p}}\right)+{\frac {q}{p}}}$.[12]

Beweis: Nach Voraussetzung gibt es eine optimale Basislösung, in der jede Variante ${\displaystyle {\mathbf {a} }^{j}}$ eine Häufigkeit ${\displaystyle x_{j}<1}$ hat. Einen ganzzahligen Zuschnittplan mit Überproduktionen erhält man aus der Optimallösung der Relaxation (5) durch einfaches Aufrunden. Das ergibt ${\displaystyle z_{D}\left(E^{(r)}\right)\leq m}$ und somit

${\displaystyle \Delta \left(E^{(r)}\right)\leq m-z_{C}\left(E^{(r)}\right)}$.

Zum ${\displaystyle (p-1)}$-fachen dieser Ungleichung addieren wir die gemäß Voraussetzung gültige Ungleichung ${\displaystyle \Delta \left(E^{(r)}\right)<(p-1)*z_{C}\left(E^{(r)}\right)+q}$ und erhalten ${\displaystyle p*\Delta \left(E^{(r)}\right)<(p-1)*m+q}$. Division durch ${\displaystyle p}$ liefert die Behauptung.

Stets gilt ${\displaystyle \Delta \left(E^{(r)}\right)\geq \Delta (E)}$, 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 ${\displaystyle E^{(r)}}$ eine für ${\displaystyle E}$ konstruieren, falls ${\displaystyle E^{(r)}}$ die Ganzzahl-Aufrundungseigenschaft erfüllt. Kennt man eine gute ganzzahlige Lösung für ${\displaystyle E^{(r)}}$, dann auch für ${\displaystyle E}$. Leider gilt dies nicht stets auch für die Optimalität, wie folgendes Gegenbeispiel zeigt:

${\displaystyle E:=\left(4;924;(308,231,132,84)^{\top };(2,3,7,6)^{\top }\right)}$ hat eine eindeutige Optimallösung der Relaxation (5), nämlich ${\displaystyle x_{1}^{C}={\frac {2}{3}},x_{2}^{C}={\frac {3}{4}},x_{3}^{C}=1,x_{4}^{C}={\frac {6}{11}},x_{j}^{C}=0}$ für ${\displaystyle j>4}$, wobei die (in der Relaxation) verschnittfreien Varianten ${\displaystyle {\mathbf {a} }^{1}=3{\mathbf {e} }^{1}}$, ${\displaystyle {\mathbf {a} }^{2}=4{\mathbf {e} }^{2}}$, ${\displaystyle {\mathbf {a} }^{3}=7{\mathbf {e} }^{3}}$ und ${\displaystyle {\mathbf {a} }^{4}=11{\mathbf {e} }^{4}}$ zugrunde gelegt wurden. Es gilt ${\displaystyle z_{C}(E)=z_{M}(E)=3-{\frac {5}{132}}}$ und ${\displaystyle z_{D}(E)=3}$, wobei es mehrere verschiedene Optimallösungen für das ganzzahlige Problem (2)–(4) gibt. Die residuale Instanz ${\displaystyle E^{(r)}}$ ist hier eindeutig (mit ${\displaystyle {\mathbf {b} }^{(r)}=(2,3,0,6)^{\top }}$), und es gilt ${\displaystyle z_{D}\left(E^{(r)}\right)=3}$, so dass das Abtrennen des ganzzahligen Anteils von der Optimallösung der stetigen Relaxation zu einer Erhöhung der Lücke ${\displaystyle \Delta =z_{D}-z_{C}}$ führte. Bei Verwendung der Relaxation (6) wäre dieser Effekt nicht eingetreten. Doch bei Vorgabe des Bedarfsvektors ${\displaystyle (5,7,7,17)^{\top }}$ vermag auch die Einschränkung auf eigentliche Varianten diese Unannehmlichkeit nicht zu verhindern.

Ein Näherungsalgorithmus mittels Relaxation

Soll d​as ganzzahlige Problem (2)–(4) e​xakt gelöst werden, erweist e​s sich o​ft als vorteilhaft, gelegentlich innerhalb d​er Optimierung m​it Hilfe e​ines Näherungsverfahrens n​ach guten zulässigen Lösungen z​u suchen. Eine entsprechende Verfahrensskizze i​st diese:

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

Der Aufwand für Punkt 6 ist mit ${\displaystyle {\mathcal {O}}(m^{2})}$ 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 ${\displaystyle \lceil z_{E}\rceil }$ wird, kann in Punkt 2 auch noch einmal die Relaxation (6) gelöst werden.

Die Farley-Schranke

Um e​ine gute zulässige Lösung d​es ganzzahligen Zuschnittproblems (2)–(4) z​u ermitteln, genügt manchmal e​ine zulässige, n​icht optimale Lösung d​er Relaxation (5) o​der (6). Falls m​an aus diesem Grunde d​ie Optimierung vorzeitig abbrechen möchte, z​um Beispiel w​eil die erzielten Zielfunktionswerte z​u stagnieren beginnen, benötigt m​an dennoch Gewähr, d​ass man tatsächlich n​ahe am Optimum ist. Dies leistet e​ine untere Schranke n​ach A. A. Farley,[13] d​ie auf d​er Dualitätstheorie d​er linearen Optimierung beruht.

Das z​ur stetigen Relaxation (5) gehörige d​uale Optimierungsproblem lautet

${\displaystyle {\mathbf {b} }^{\top }{\mathbf {u} }\to \max !}$ bei ${\displaystyle {\mathbf {a} }^{\top }{\mathbf {u} }\leq 1}$ für jede zulässige Variante ${\displaystyle {\mathbf {a} }}$.

Jedes ${\displaystyle {\mathbf {u} }\in {\mathbb {R} }^{m}}$, welches zum zulässigen Bereich des dualen Problems gehört, liefert somit eine untere Schranke ${\displaystyle {\mathbf {b} }^{\top }\mathbf {u} }$ für den optimalen Zielfunktionswert. Ein geeignetes ${\displaystyle \mathbf {u} }$ findet man leicht, sobald das Rucksackproblem (7) gelöst wurde. Die ermittelte Variante sei ${\displaystyle {\tilde {\mathbf {a} }}}$. Gilt ${\displaystyle {\mathbf {g} }^{\top }{\tilde {\mathbf {a} }}=1}$, liegt eine Optimallösung der Relaxation vor. Andernfalls setzen wir ${\displaystyle {\mathbf {u} }:={\frac {1}{{\mathbf {g} }^{\top }{\tilde {\mathbf {a} }}}}\mathbf {g} }$ und erhalten für jede beliebige zulässige Zuschnittvariante ${\displaystyle \mathbf {a} }$ die Abschätzung ${\displaystyle {\mathbf {a} }^{\top }{\mathbf {u} }={\mathbf {a} }^{\top }{\mathbf {g} }/{\mathbf {g} }^{\top }{\tilde {\mathbf {a} }}\leq 1}$ laut Annahme über ${\displaystyle {\tilde {\mathbf {a} }}}$. Folglich ist das gewählte ${\displaystyle \mathbf {u} }$ für die duale Aufgabe zulässig. Daraus ergibt sich die gewünschte untere Schranke

${\displaystyle z_{C}\geq {\mathbf {b} }^{\top }{\mathbf {u} }={\frac {{\mathbf {b} }^{\top }\mathbf {g} }{{\mathbf {g} }^{\top }{\tilde {\mathbf {a} }}}}={\frac {z}{{\mathbf {g} }^{\top }{\tilde {\mathbf {a} }}}}}$,

die s​ich bei Fortsetzung d​er Optimierung d​em optimalen Zielfunktionswert d​er Relaxation nähert. Analog s​ieht die Schranke für (6) aus.

Beispiel: Für die Instanz ${\displaystyle E:=\left(3;11;(6,4,1)^{\top };(2,2,1)^{\top }\right)}$ wurden oben die berechneten Simplexschemata angegeben. Vor dem ersten Austausch galten ${\displaystyle z={\frac {34}{11}}}$ und ${\displaystyle {\mathbf {g} }={\frac {1}{22}}(22,11,2)^{\top }}$ sowie ${\displaystyle {\tilde {\mathbf {a} }}={\mathbf {a} }^{4}=(1,1,1)^{\top }}$, also ${\displaystyle z/{\mathbf {g} }^{\top }{\mathbf {a} }^{4}={\frac {68}{35}}}$. Nach dem Eintauschen der Variante ${\displaystyle {\mathbf {a} }^{4}}$ in die Basis wurden ${\displaystyle z={\frac {5}{2}}}$, ${\displaystyle {\mathbf {g} }={\frac {1}{2}}(2,1,-1)^{\top }}$ und ${\displaystyle {\mathbf {a} }^{5}=(1,1,0)^{\top }}$ ermittelt. Folglich sinkt die untere Schranke ${\displaystyle z/{\mathbf {g} }^{\top }{\tilde {\mathbf {a} }}}$ vorübergehend auf ${\displaystyle {\frac {5}{3}}<{\frac {68}{35}}}$ und wächst nicht monoton.

Für mehrdimensionale Zuschnittprobleme k​ann eine entsprechende untere Schranke ebenso aufgestellt werden. Gemäß A. A. Farley ermöglicht d​iese Schranke d​ie Einsparung vieler Spaltengenerierungs- u​nd Austauschzyklen, o​hne Gefahr z​u laufen, w​eit vom Optimum entfernt z​u sein.

(k,k+1)-Instanzen

Sei ${\displaystyle k}$ eine positive ganze Zahl. Die Instanz ${\displaystyle E:=(m;L;{\mathbf {l} };{\mathbf {b} })}$ heiße ${\displaystyle (k,k+1)}$-Instanz, falls ${\displaystyle L/(k+2)<l_{i}\leq L/k}$ für alle ${\displaystyle i\in I}$ zutrifft, also jedes Teil genau ${\displaystyle k}$- oder ${\displaystyle (k+1)}$-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 ${\displaystyle \Delta =z_{D}-z_{C}}$. Umfangreiche Untersuchungen enthält,[8] während die diesbezüglichen Beiträge in[10] und[12] Vorläufer darstellen.

Unter einer ${\displaystyle p}$-Teile-Variante verstehen wir eine beliebige zulässige Zuschnittvariante ${\displaystyle \mathbf {a} }$, mit der genau ${\displaystyle p}$ Teile zugeschnitten werden (${\displaystyle p\leq k+1}$), d. h. ${\displaystyle {\mathbf {e} }^{\top }{\mathbf {a} }=p}$, wobei ${\displaystyle {\mathbf {e} }\in {\mathbb {R} }^{m}}$ für den aus lauter Einsen bestehenden Einsvektor steht.

(k,k+1)-Instanzen mit Δ=1

Offensichtlich gilt bei ${\displaystyle k=1}$ die Ganzzahl-Aufrundungseigenschaft, weil nur ${\displaystyle \Delta \in \{0;0{,}5\}}$ möglich ist. Bei ${\displaystyle k\geq 2}$ ändert sich die Situation jedoch grundlegend. Ist ${\displaystyle t\geq \max \left\{3k^{3}-k^{2}-3k;3k^{2}+3k+1\right\}}$, ergibt sich ${\displaystyle z_{M}=z_{C}=3}$ und ${\displaystyle z_{D}=4}$ für die Instanz

${\displaystyle \left(9;(k+1)*(t+3k);(t+3k^{2}+2k,t+2k^{2}+k,t+6k,t+1,t+k+2,t+3k-3,t,t+k,t+3k)^{\top };(1,1,1,k-1,k-1,k-1,1,1,1)^{\top }\right)}$,

wobei die Teile nicht nach der Länge geordnet wurden. Verwendet man in der stetigen Relaxation (5) die verschnittfreien Varianten ${\displaystyle {\mathbf {e} }^{1}+k{\mathbf {e} }^{4}}$, ${\displaystyle {\mathbf {e} }^{2}+k{\mathbf {e} }^{5}}$ und ${\displaystyle {\mathbf {e} }^{3}+k{\mathbf {e} }^{6}}$ je ${\displaystyle {\frac {k-1}{k}}}$-mal, die Varianten ${\displaystyle {\mathbf {e} }^{1}+(k-1){\mathbf {e} }^{7}+{\mathbf {e} }^{8}}$, ${\displaystyle {\mathbf {e} }^{2}+(k-1){\mathbf {e} }^{8}+{\mathbf {e} }^{9}}$ und ${\displaystyle {\mathbf {e} }^{3}+(k-1){\mathbf {e} }^{9}+{\mathbf {e} }^{7}}$ je ${\displaystyle {\frac {1}{k}}}$-mal so bestätigt man schnell ${\displaystyle z_{C}=3}$.

Für folgende Instanzen gilt jeweils ${\displaystyle z_{M}<z_{C}=2}$ und ${\displaystyle z_{D}=3}$:

• ${\displaystyle k=2}$: ${\displaystyle \left(5;75;(29,28,25,23,19)^{\top };(1,1,2,1,1)^{\top }\right)}$
• ${\displaystyle k=3}$: ${\displaystyle \left(5;94;(29,28,25,23,19)^{\top };(1,1,2,1,3)^{\top }\right)}$
• ${\displaystyle k\geq 4}$: ${\displaystyle \left(5;10k^{2}-8k;(10k-8,10k-9,10k-12,10k-14,10k-18)^{\top };(1,1,2,1,2k-3)^{\top }\right)}$

Es gibt keine (2,3)-Instanz mit ${\displaystyle z_{M}=z_{C}=2<z_{D}}$. Dagegen gilt ${\displaystyle z_{M}=z_{C}=2}$ und ${\displaystyle z_{D}=3}$ für die Instanzen

• ${\displaystyle \left(7;7k^{2}+26k+23;(7k+29,7k+27,7k+21,7k+19,7k+17,7k+16,7k+12)^{\top };(1,1,1,2k-4,1,1,1)^{\top }\right)}$ bei ${\displaystyle 3\leq k\leq 7}$
• ${\displaystyle \left(7;10k^{2}+6k;(10k+6,10k+4,10k-2,10k-4,10k-6,10k-7,10k-11)^{\top };(1,1,1,2k-4,1,1,1)^{\top }\right)}$ bei ${\displaystyle k\geq 8}$.

Komplementäre Instanzen

Zuerst betrachten wir (2,3)-Instanzen ${\displaystyle (m;L;{\mathbf {l} };{\mathbf {b} })}$ mit ${\displaystyle {\frac {5}{12}}L>\ell _{1}\geq \cdots \geq l_{m}>{\frac {L}{4}}}$. Mit der Festlegung ${\displaystyle l_{i}':={\frac {2}{3}}L-l_{i}}$ für alle ${\displaystyle i\in I}$ erhalten wir eine (2,3)-Instanz ${\displaystyle E':=\left(m;L;{\mathbf {l} }';{\mathbf {b} }\right)}$ mit ${\displaystyle {\frac {L}{4}}<l_{1}'\leq \cdots \leq l_{m}'<{\frac {5}{12}}L}$, die wir komplementäre Instanz zu ${\displaystyle E}$ nennen. Die zu ${\displaystyle E'}$ komplementäre Instanz ist wieder ${\displaystyle E}$. Ist ${\displaystyle \mathbf {a} }$ eine (für ${\displaystyle E}$) verschnittfreie Variante mit genau drei Teilen, ist ${\displaystyle \mathbf {a} }$ auch für ${\displaystyle E'}$ zulässig und verschnittfrei. Dagegen entsprechen verschnittbehafteten 3-Teile-Varianten in ${\displaystyle E}$ unzulässige in ${\displaystyle E'}$ und umgekehrt. Folglich kann man nicht von Optimallösungen der Aufgaben (2)–(4) oder (5) oder (6) für ${\displaystyle E}$ auf die entsprechenden Optimallösungen für ${\displaystyle E'}$ schließen. Dennoch fällt die Verallgemeinerung auf ${\displaystyle (k,k+1)}$-Instanzen nicht schwer.

Gegeben sei nun eine ${\displaystyle (k,k+1)}$-Instanz ${\displaystyle E=(m;L;{\mathbf {l} };{\mathbf {e} })}$ mit ${\displaystyle l_{1}\geq \cdots \geq l_{m}}$, für die ${\displaystyle m/(k+1)=z_{C}=z_{M}}$ zutrifft, in der also in jeder Optimallösung der stetigen Relaxation nur verschnittfreie Varianten mit je ${\displaystyle k+1}$ Teilen in positiver Häufigkeit verwendet werden. Dann ist für hinreichend großes ${\displaystyle t\in \mathbb {R} }$ die Instanz

${\displaystyle E(t):=\left(m;L+(k+1)*t;{\mathbf {l} }+t{\mathbf {e} };{\mathbf {e} }\right)}$

eine zu ${\displaystyle E}$ äquivalente Instanz, denn in ${\displaystyle (k,k+1)}$-Instanzen sind alle Varianten mit höchstens ${\displaystyle k}$ Teilen zulässig und alle Varianten mit mindestens ${\displaystyle k+2}$ Teilen unzulässig, während der Verschnitt einer ${\displaystyle (k+1)}$-Teile-Variante in ${\displaystyle E(t)}$ ebenso groß wie in ${\displaystyle E}$ ist. Für unsere Zwecke reicht die Forderung

${\displaystyle t>\max \left\{L-(k+2)*l_{m},\;k*l_{1}-L\right\}}$

aus. Die zu ${\displaystyle E(t)}$ komplementäre Instanz ${\displaystyle E'(t)}$ definieren wir als

${\displaystyle E'(t):=\left(m;L+(k+1)*t;\left({\frac {2}{k+1}}L+t\right){\mathbf {e} }-{\mathbf {l} };{\mathbf {e} }\right)}$

Dabei braucht ${\displaystyle E'(t)}$ nicht notwendig ${\displaystyle (k,k+1)}$-Instanz zu sein. Hat die Instanz ${\displaystyle E}$ eine Lücke ${\displaystyle \Delta \geq 1}$, gilt das auch für fast alle ${\displaystyle t>-l_{m}}$ in der Instanz ${\displaystyle E(t)}$, da es nur endlich viele Kombinationen von höchstens ${\displaystyle k}$ Teilen gibt, die eine verschnittfreie Variante ergeben. Folglich erfüllt auch die komplementäre Instanz ${\displaystyle E'(t)}$, für fast alle ${\displaystyle t}$, die der oben angegebenen Bedingung genügen, die Ganzzahl-Aufrundungseigenschaft nicht.

Beispiel: ${\displaystyle E(t):=\left(9;51+3t;(23+t,19+t,19+t,17+t,17+t,16+t,15+t,14+t,13+t)^{\top };{\mathbf {e} }\right)}$ weist für alle ${\displaystyle t>-13,t\notin \{-12,-11,-9\}}$ eine Lücke 1 auf, und es gilt ${\displaystyle z_{C}=z_{M}=3=m/3}$. Für alle ${\displaystyle t>\max\{51-4*13,\;2*23-51\}=-1}$ ist ${\displaystyle E(t)}$ eine (2,3)-Instanz. Die zugehörige komplementäre Instanz lautet ${\displaystyle E'(t)=\left(9;51+3t;(11+t,15+t,15+t,17+t,17+t,18+t,19+t,20+t,21+t)^{\top };{\mathbf {e} }\right)}$ und besitzt für alle ${\displaystyle t>-11,t\neq -10}$ ebenfalls die Lücke 1. Für ${\displaystyle t>\max\{51-4*11,\;2*21-51\}=7}$ ist auch ${\displaystyle E'(t)}$ eine (2,3)-Instanz.

(2,3)-Instanzen mit auffälligen Nennern

Bevor (2,3)-Instanzen mit Lücke ${\displaystyle \Delta >1}$ angegeben werden, demonstrieren wir, wie vielfältig der Nenner von ${\displaystyle z_{C}}$ werden kann. Dazu sei ${\displaystyle p\in \mathbb {N} }$ beliebig gewählt. Die Festlegungen ${\displaystyle m:=2p+1}$, ${\displaystyle L:=2^{m}+3}$, ${\displaystyle l_{1}:=(L+1)/3}$ und ${\displaystyle l_{i}:=L-2l_{i-1}}$, für ${\displaystyle i=2,\dots ,m}$ liefern eine (2,3)-Instanz ${\displaystyle (m;L;{\mathbf {l} };{\mathbf {e} })}$ mit ${\displaystyle z_{C}={\frac {(3m+1)*2^{m}+1}{9*2^{m}}}}$. Der Bruch kann nur durch 9 gekürzt werden. Dagegen ergeben sich bei der (2,3)-Instanz

${\displaystyle \left(2^{p};6*2^{p}-5;(5*2^{p-1}-2,5*2^{p-1}-3,\dots ,3*2^{p-1},3*2^{p-1}-1)^{\top };{\mathbf {e} }\right)}$

für ${\displaystyle p=0,\dots ,6}$ die optimalen Zielfunktionswerte ${\displaystyle {\frac {1}{2}},{\frac {3}{4}},{\frac {7}{5}},{\frac {30}{11}},{\frac {124}{23}},{\frac {504}{47}}}$ und ${\displaystyle {\frac {2032}{95}}}$ für die stetige Relaxation (5), was zur Vermutung

${\displaystyle z_{C}{\stackrel {?}{=}}{\frac {2^{2p-1}-2^{p-2}}{3*2^{p-1}-1}}={\frac {{\frac {m^{2}}{2}}-{\frac {m}{4}}}{{\frac {3}{2}}m-1}}={\frac {1}{18}}*{\frac {(6m+1)*\left({\frac {3}{2}}m-1\right)+1}{{\frac {3}{2}}m-1}}}$

führt. Der Beweis steht noch aus. Für ${\displaystyle p\geq 2}$ sind Zähler und Nenner teilerfremde natürliche Zahlen.

Variiert m​an die Längen geringfügig o​der streicht m​an einzelne Teile a​us der Instanz, können s​ich noch g​anz andere Nenner ergeben, z​um Beispiel:

• ${\displaystyle \left(5;90;(42,36,31,25,23)^{\top };{\mathbf {e} }\right)}$, ${\displaystyle z_{C}=1+11/14}$
• ${\displaystyle \left(8;90;(43,42,36,31,26,25,24,23)^{\top };{\mathbf {e} }\right)}$, ${\displaystyle z_{C}=2+14/17}$
• ${\displaystyle \left(8;128;(52,50,46,43,42,40,36,34)^{\top };{\mathbf {e} }\right)}$, ${\displaystyle z_{C}=2+27/38}$
• ${\displaystyle \left(12;187;(78,77,75,72,65,60,58,57,54,53,52,49)^{\top };{\mathbf {e} }\right)}$, ${\displaystyle z_{C}=4+1/26}$
• ${\displaystyle \left(14;187;(78,77,75,72,69,65,63,60,58,57,53,52,50,49)^{\top };{\mathbf {e} }\right)}$, ${\displaystyle z_{C}=4+45/62}$

(2,3)-Instanzen mit Δ>1

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 ${\displaystyle \Delta \approx 73/72}$, nämlich

• ${\displaystyle \left(10;387;(177,145,133,130,129,127,121,113,105,97)^{\top };(3,2,2,1,2,2,2,1,1,1)^{\top }\right)}$, ${\displaystyle z_{C}=6-1/96}$
• ${\displaystyle \left(12;1539;(705,577,529,517,514,513,511,505,481,449,417,385)^{\top };(3,2,2,1,1,2,2,2,2,1,1,1)^{\top }\right)}$, ${\displaystyle z_{C}=7-5/384}$
• ${\displaystyle \left(14;6147;(2817,2305,2113,2065,2053,2050,2049,2047,2041,2017,1921,1793,1665,1537)^{\top };(3,2,2,1,1,1,2,2,2,2,2,1,1,1)^{\top }\right)}$, ${\displaystyle z_{C}=8-7/512}$
• ${\displaystyle \left(16;24579;(11265,9217,8449,8257,8209,8197,8194,8193,8191,8185,8161,8065,7681,7169,6657,6145)^{\top };\,\,(3,2,2,1,1,1,1,2,2,2,2,2,2,1,1,1)^{\top }\right)}$, ${\displaystyle z_{C}=9-85/6144}$.

Die Instanzen m​it den ungeraden Nennern eignen s​ich für d​iese Konstruktion n​ur bedingt, w​eil sie verhältnismäßig v​iel Verschnitt verursachen.

Rückführung auf einfachere Instanzen

Um obere Schranken für die Lücke ${\displaystyle \Delta }$ 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 ${\displaystyle E=(m;L;{\mathbf {l} };{\mathbf {e} })}$ eine beliebige ${\displaystyle (k,k+1)}$-Instanz. Bezeichnen ${\displaystyle y_{C}}$ und ${\displaystyle y_{D}}$ die Häufigkeiten aller ${\displaystyle k}$-Teile-Varianten in Optimallösungen der Relaxation (5) bzw. des ganzzahligen Problems (2)–(4), gilt ${\displaystyle y_{D}\geq y_{C}}$. Gilt ${\displaystyle q:=k*\lceil y_{C}\rceil <m}$, können die ${\displaystyle q}$ größten Teile in ${\displaystyle k}$-Teile-Varianten zugeschnitten werden, und nach deren Abtrennung verbleibt eine Instanz ${\displaystyle E'=\left(m';L;{\mathbf {l} }';{\mathbf {b} }'\right)}$ mit ${\displaystyle \Delta (E)\geq \Delta \left(E'\right)>\Delta (E)-1/(k+1)}$ und ${\displaystyle (k+1)*z_{C}=\sum \limits _{i=1}^{m'}b_{i}'\in \mathbb {N} }$. 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 ${\displaystyle 1/(k+1)}$ ab. Daraus ergibt sich eine wichtige

Folgerung: Jede ${\displaystyle (k,k+1)}$-Instanz ${\displaystyle E=(m;L;{\mathbf {l} };{\mathbf {b} })}$ mit ${\displaystyle z_{C}(E)\notin \mathbb {N} }$ kann auf eine Instanz ${\displaystyle E'}$ mit ${\displaystyle z_{C}\left(E'\right)\in \mathbb {N} }$, ${\displaystyle z_{C}\left(E'\right)<z_{C}(E)}$ und ${\displaystyle \Delta (E)-1<\Delta \left(E'\right)<\Delta (E)}$ reduziert werden. Das heißt insbesondere: Ist ${\displaystyle C(k)\in \mathbb {N} }$ so, dass für alle ${\displaystyle (k,k+1)}$-Instanzen mit ${\displaystyle z_{C}\leq C(k)\land z_{C}\in \mathbb {N} }$ die modifizierte Ganzzahl-Aufrundungseigenschaft (MIRUP) gilt, dann auch für alle ${\displaystyle (k,k+1)}$-Instanzen mit ${\displaystyle z_{C}<C(k)+1}$.

Beispiel: In d​er (2,3)-Instanz

${\displaystyle E_{1}:=\left(13;8195;(4097,3073,2817,2753,2737,2733,2732,2731,2729,2721,2689,2561,2049)^{\top };5{\mathbf {e} }+45{\mathbf {e} }^{8}\right)}$

gilt ${\displaystyle z_{C}\approx 37{,}2217}$ und ${\displaystyle y_{C}\approx 1{,}6650}$, also ${\displaystyle y_{D}\geq 2}$. 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 ${\displaystyle E_{2}}$ gilt ${\displaystyle y_{C}\left(E_{2}\right)=0}$ und ${\displaystyle z_{C}\left(E_{2}\right)=35+1/3}$. 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 ${\displaystyle 34+2/3}$. Trennt man nun noch zwei Teile der Länge 3073 ab, ergibt sich für die Restinstanz ${\displaystyle z_{C}=34}$. Dennoch gibt es viele nicht ganzzahlige Optimallösungen der Relaxation (5).

Gemäß der Folgerung bedeutet es keine Einschränkung, wenn ab hier nur noch ${\displaystyle (k,k+1)}$-Instanzen ${\displaystyle (m;L;{\mathbf {l} };{\mathbf {e} })}$ mit ${\displaystyle z_{C}\in \mathbb {N} }$ und ${\displaystyle m=(k+1)*z_{C}}$ betrachtet werden. Ohne Beschränkung der Allgemeinheit seien die Teile nach fallenden Längen geordnet, also ${\displaystyle l_{1}\geq \cdots \geq l_{m}}$. Die Anzahl aller zuzuschneidenden Teile mit Länge oberhalb ${\displaystyle L/(k+1)}$ sei ${\displaystyle g}$. Für ${\displaystyle p=1,\dots ,k+1}$ bezeichne ${\displaystyle y_{p}}$ jeweils die Gesamthäufigkeit aller in einer vorliegenden Optimallösung der stetigen Relaxation (5) vorkommenden Varianten, die genau ${\displaystyle p}$ Teile aus ${\displaystyle \{g+1,\dots ,m\}}$ (und ${\displaystyle k+1-p}$ größere Teile) enthalten.

Aufgrund dieser Einteilung der Teile in größere und kleinere ergibt sich ${\displaystyle z_{C}=\sum \limits _{p=1}^{k+1}y_{p}}$ und ${\displaystyle g=\sum \limits _{p=1}^{k+1}(k+1-p)*y_{p}}$, also auch ${\displaystyle y_{k+1}\geq z_{C}-g}$. Gilt ${\displaystyle y_{k+1}\geq 1}$, können die ${\displaystyle k+1}$ größten Teile aus ${\displaystyle \{g+1,\dots ,m\}}$ in einer abgesonderten Variante geschnitten werden, und die Abtrennung dieser Variante ändert die Lücke ${\displaystyle \Delta }$ nicht. Unter Umständen findet man anstelle dieser eine zulässige ${\displaystyle (k+1)}$-Teile-Variante, die ein größeres Teil enthält, aber keine kleineren. Dann kann die Reduktion eventuell häufiger vorgenommen werden.

Beispiel: In d​er (2,3)-Instanz

${\displaystyle E_{3}:=\left(12;8195;(3073,2817,2753,2737,2733,2732,2731,2729,2721,2689,2561,2049)^{\top };5{\mathbf {e} }-3{\mathbf {e} }^{1}+45{\mathbf {e} }^{7}\right)}$

gilt ${\displaystyle g=27<z_{C}=34}$, so dass gewiss siebenmal je drei Teile der Länge 2731 in einer Variante abgetrennt werden können. Diese Variante wird aber durch ${\displaystyle 2{\mathbf {e} }^{6}+{\mathbf {e} }^{7}}$ und ${\displaystyle {\mathbf {e} }^{5}+2{\mathbf {e} }^{7}}$ dominiert. Diese beiden verschnittfreien Varianten können zwei- bzw. fünfmal zugeschnitten werden, ohne Überproduktion zu erzielen. In der erhaltenen Instanz gilt wieder ${\displaystyle g<z_{C}}$, und nun kann die Variante ${\displaystyle {\mathbf {e} }^{6}+2{\mathbf {e} }^{7}}$ einmal abgetrennt werden. (Teil 5 war schon verbraucht.) Das führt auf die Instanz

${\displaystyle E_{4}:=\left(10;8195;(3073,2817,2753,2737,2731,2729,2721,2689,2561,2049)^{\top };(2,5,5,5,36,5,5,5,5,5)^{\top }\right)}$

mit ${\displaystyle z_{C}\left(E_{4}\right)=26}$ und ${\displaystyle g=17}$, so dass noch neunmal die Variante ${\displaystyle 3{\mathbf {e} }^{5}}$ 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, ${\displaystyle \Delta \left(E_{4}\right)=0}$ und ${\displaystyle z_{D}\left(E_{1}\right)=38}$.

A-priori-Zulässigkeit von Varianten

Seien ${\displaystyle k,p_{1},\dots ,p_{k+1},q\in \mathbb {N} \setminus \{0\}}$, ${\displaystyle k\geq 2}$, ${\displaystyle q\leq k}$ und ${\displaystyle p_{1}\leq \cdots \leq p_{k+1}\leq m}$. In der ${\displaystyle (k,k+1)}$-Instanz ${\displaystyle E=(m;L;{\mathbf {l} };{\mathbf {e} })}$ mit ${\displaystyle l_{1}\geq \cdots \geq l_{m}}$ seien ${\displaystyle g}$ und ${\displaystyle y_{i}}$ für ${\displaystyle i=1,\dots ,k+1}$ wieder wie im vorigen Abschnitt definiert. Die Zuschnittvariante ${\displaystyle \sum \limits _{i=1}^{k+1}{\mathbf {e} }^{p_{i}}}$ ist unabhängig von den Längen ${\displaystyle L}$ und ${\displaystyle l_{i}}$ zulässig, kurz ${\displaystyle (p_{1},\dots ,p_{k+1})}$ geschrieben, wenn eine der folgenden Bedingungen erfüllt ist:

• ${\displaystyle p_{q}\leq g<p_{q+1}\land y_{k+1-q}>g-p_{q}+m-p_{k+1}+\sum \limits _{i=2}^{q}{\frac {p_{i}-p_{i-1}}{q-i+2}}+\sum \limits _{i=q+2}^{k+1}{\frac {p_{i}-p_{i-1}}{k-i+3}}}$
• ${\displaystyle m=(k+1)*z_{C}\land p_{1}+\sum \limits _{i=1}^{k}{\frac {k+1}{(k+1-i)*(k+2-i)}}*p_{i+1}>k*m}$

Bei ${\displaystyle m=(k+1)*z_{C}}$ gilt auch ${\displaystyle y_{1}\geq g-(k-1)*z_{C}}$. Gemäß den Reduktionen im vorigen Abschnitt kann dies erzwungen werden, auch ${\displaystyle z_{C}\in \mathbb {N} }$ und ${\displaystyle y_{k+1}<1}$. Dies wird im Folgenden vorausgesetzt, wenn obige sehr technische Aussagen auf (2,3)-Instanzen angewandt werden. Dann gilt auch ${\displaystyle y_{1}=g-z_{C}+y_{3}}$.

Unter den oben angegebenen Voraussetzungen ist in einer (2,3)-Instanz die Variante ${\displaystyle {\mathbf {e} }^{p_{1}}+{\mathbf {e} }^{p_{2}}+{\mathbf {e} }^{p_{3}}}$ zulässig, kurz ${\displaystyle \left(p_{1},p_{2},p_{3}\right)}$ geschrieben, wenn eine der folgenden Bedingungen zutrifft:

(a) ${\displaystyle p_{1}\leq p_{2}\leq g<p_{3}\land (p_{1}+p_{2}+2p_{3}>2g+6z_{C}-2y_{1}}$ oder ${\displaystyle p_{1}+p_{2}+2p_{3}\geq 8z_{C}+1)}$

(b) ${\displaystyle p_{1}\leq g<p_{2}\leq p_{3}\land (p_{1}+2p_{3}>g+6z_{C}-2y_{1}}$ oder ${\displaystyle p_{1}+2p_{3}\geq 8z_{C}-g+1)}$

(c) ${\displaystyle p_{1}\leq g<p_{2}\leq p_{3}\land 2p_{1}+p_{2}+p_{3}>6z_{C}+4y_{1}}$ (erfordert Fallunterscheidung bezüglich ${\displaystyle y_{1}}$)

(d) ${\displaystyle 2p_{1}+p_{2}+3p_{3}\geq 12z_{C}+1}$

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 ${\displaystyle p_{2}\leq g}$ auch (a)-Variante ist und die (a)-Varianten die (b)-Varianten dominieren. Bedingung (a) ist aber bei ${\displaystyle p_{2}>g}$ nicht anwendbar. (a)-Varianten sind bei ${\displaystyle g=2z_{C}}$ am günstigsten, (c)-Varianten bei ${\displaystyle g=z_{C}}$, weil ${\displaystyle y_{1}<1}$ wird.

Beispiel: Seien ${\displaystyle m=27}$ und ${\displaystyle z_{C}=9}$. Bei ${\displaystyle g=17}$ findet man z. B. die (a)-Variante (5,16,26), denn ${\displaystyle 5\leq 16\leq 17<26\land 5+16+2*26=73\geq 8*9+1}$. (d) hätte wegen ${\displaystyle 2*5+16+3*26=104<12*9+1=109}$ kein Ergebnis gebracht. Eine (b)-Variante ist (2,18,27), denn ${\displaystyle 2+2*27+17=73\geq 8*9+1}$. Wegen ${\displaystyle 18>g}$ durfte (a) nicht benutzt werden. Bei ${\displaystyle g=9}$ findet man wegen ${\displaystyle 9+9+2*27=72\leq 8*9}$ keine (a)- und (b)-Varianten. Eine (d)-Variante ist (9,10,27), denn ${\displaystyle 2*9+10+3*27=109\geq 12*9+1}$. Wegen ${\displaystyle y_{3}<1}$ (gemäß Reduktionen) und ${\displaystyle y_{1}=g-z_{C}+y_{3}}$ ist ${\displaystyle y_{1}<1}$ und daher (9,19,21) eine (c)-Variante, denn ${\displaystyle 2*9+19+21=58>6*9+4y_{1}}$ und ${\displaystyle 9\leq g<19\leq 21}$. Hier hätte das Kriterium (d) wegen ${\displaystyle 2*9+19+3*21=100<109}$ versagt.

Nun seien ${\displaystyle z_{C}=2}$, ${\displaystyle m=6}$ und ${\displaystyle g=4}$ gegeben. Dann gilt ${\displaystyle y_{1}=2}$ und ${\displaystyle y_{2}=y_{3}=0}$, so dass es die (a)-Varianten (1,4,6), (2,3,6) und (3,4,5) gibt. Wäre ${\displaystyle z_{D}=3}$, 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 ${\displaystyle z_{C}=z_{D}=2}$.

Aufstellung ganzzahliger Schnittpläne

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 ${\displaystyle (k,k+1)}$-Instanzen ${\displaystyle (m;L;{\mathbf {l} };{\mathbf {e} })}$ mit ${\displaystyle l_{1}\geq \cdots \geq l_{m}}$, in denen die obigen Reduktionen vorgenommen wurden, wo also auch ${\displaystyle m=(k+1)*z_{C}}$ und ${\displaystyle z_{C}\in \mathbb {N} }$ gilt. Alleine von ${\displaystyle g}$, ${\displaystyle k}$ und ${\displaystyle z_{C}}$ abhängige Abschätzungen für ${\displaystyle z_{D}}$ werden angegeben.

Zwei Zuschnittvarianten ${\displaystyle {\mathbf {a} },{\mathbf {a} }'}$ sollen unkorreliert heißen, wenn sie eigentlich sind und kein Teil gleichzeitig in beiden Varianten vorkommt, also ${\displaystyle {\mathbf {a} }^{\top }{\mathbf {a} }'=0}$ gilt. Sei ${\displaystyle t}$ die Anzahl derjenigen Teile aus ${\displaystyle \{1,\dots ,g\}}$, die nicht gleichzeitig in paarweise unkorrelierten ${\displaystyle (k+1)}$-Teile-Varianten untergebracht werden können, einerlei welcher Plan für das Problem (2)–(4) zugrunde gelegt wird. Dann gilt:

• ${\displaystyle \Delta \leq {\frac {t-1}{k*(k+1)}}+1}$
• ${\displaystyle t\leq g-k*\min \left\{\left\lfloor {\frac {g}{k}}\right\rfloor ,\left\lceil {\frac {1+g-(k-1)*z_{C}}{s}}-1\right\rceil \right\}}$ mit ${\displaystyle s=\sum \limits _{i=1}^{k}{\frac {1}{i}}}$
• ${\displaystyle t\leq (k+1)*\left(z_{C}+1-\left\lceil {\frac {(k+1)*\left(z_{C}+{\frac {1}{2}}\right)}{{\frac {k*(k+3)}{2}}-\sum \limits _{i=3}^{k+1}{\frac {k+1}{i}}}}\right\rceil \right)}$, speziell ${\displaystyle t\leq 3*\left\lceil {\frac {z_{C}-1}{4}}\right\rceil }$ bei ${\displaystyle k=2}$.

Daraus folgt für (2,3)-Instanzen mit ${\displaystyle z_{C}\leq 9}$ sofort MIRUP, also ${\displaystyle \Delta <2}$. Bei ${\displaystyle z_{C}=10}$ 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 ${\displaystyle z_{C}=10}$, ${\displaystyle m=30}$ 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 ${\displaystyle g<14}$ ist damit alles gezeigt, ansonsten ersetzt man die erste Variante durch die (a)-Variante (7,14,30) und bei ${\displaystyle g>14}$ noch weitere Varianten entsprechend. Dagegen kann alleine mittels obiger Aussagen MIRUP im Fall ${\displaystyle z_{C}\geq 11}$ nicht mehr bewiesen werden.

Aussagen zum allgemeinen Fall

Inwieweit die Lücke ${\displaystyle \Delta =z_{D}-z_{C}}$ für eine beliebige Instanz ${\displaystyle (m;L;{\mathbf {l} };{\mathbf {b} })}$ beschränkt ist, konnte noch nicht abschließend erforscht werden. So blieb beispielsweise noch offen, ob ${\displaystyle \Delta }$ durch eine Konstante beschränkt ist oder linear mit ${\displaystyle m}$ wachsen kann oder etwa eine Abschätzung der Art ${\displaystyle \Delta <1+C*\ln m}$ mit einer Konstante ${\displaystyle C>0}$ für alle Instanzen des eindimensionalen Zuschnittproblems zutrifft.

Aus d​er Betrachtung residualer Instanzen f​olgt die f​ast triviale Aussage

${\displaystyle \Delta <\max\{1,\,m-1\}}$.

Deutlich komplizierter i​st der Beweis für d​ie Abschätzungen

${\displaystyle \Delta <\max \left\{2,{\frac {z_{M}+2}{3}}\right\}}$ und ${\displaystyle \Delta <\max \left\{2,\,{\frac {m+2}{4}}\right\}}$

sowie der Nachweis der Ganzzahl-Aufrundungseigenschaft ${\displaystyle z_{D}=\left\lceil z_{C}\right\rceil }$ für alle Instanzen mit ${\displaystyle z_{M}\leq 7/4}$.[12] Dagegen ist es eine leichte Übung, ${\displaystyle \Delta <1}$ nachzuweisen, falls ${\displaystyle {\frac {1}{\left\lceil z_{C}\right\rceil }}*\mathbf {b} }$ ganzzahlig ist.

Ferner konnte MIRUP, also ${\displaystyle z_{D}\leq \left\lceil z_{C}\right\rceil +1}$, für folgende Fälle bewiesen werden:[8]

• ${\displaystyle z_{M}\leq 4{,}75\lor 5<z_{M}\leq 5{,}5\lor 6<z_{M}\leq 6{,}25}$
• ${\displaystyle z_{C}<11}$, wenn außerdem alle Teile größer als ein Viertel des Ausgangsmaterials sind.

Dazu diente a​uch folgende Aussage, für die[14] e​ine gute Vorlage enthielt:

Lemma: Über die Instanz ${\displaystyle E:=(m;L;{\mathbf {l} };{\mathbf {b} })}$ werden ${\displaystyle b_{i}>0}$ für alle ${\displaystyle i\in I}$, ferner ${\displaystyle l_{1}>\cdots >l_{m}}$ sowie ${\displaystyle 2l_{1}>L}$ und ${\displaystyle l_{1}+2l_{m}>L}$ vorausgesetzt. Gilt ${\displaystyle l_{1}+l_{m}>L}$, so sei ${\displaystyle {\mathbf {a} }:={\mathbf {e} }^{1}}$, andernfalls ${\displaystyle t:=\min \left\{i\in I:l_{1}+l_{i}\leq L\right\}}$ und ${\displaystyle {\mathbf {a} }:={\mathbf {e} }^{1}+{\mathbf {e} }^{t}}$. Dann besitzen die Instanzen ${\displaystyle E}$ und ${\displaystyle (m;L;{\mathbf {l} };{\mathbf {b} }-{\mathbf {a} })}$ die gleiche Lücke ${\displaystyle \Delta }$, 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 ${\displaystyle E_{1}:=\left(4;18;(10,9,6,4)^{\top };(1,1,2,1)^{\top }\right)}$ und ${\displaystyle E_{2}:=\left(2;6;(3,2)^{\top };(1,4)^{\top }\right)}$ mit ${\displaystyle \Delta \left(E_{1}\right)=1}$ und ${\displaystyle \Delta \left(E_{2}\right)=1/6}$ zeigen.

Das MAXGAP-Problem; Konstruktionssätze für große Δ

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 ${\displaystyle \Delta =z_{D}-z_{C}}$.[15]

Die größte bisher (Stand 2007) erreichte Lücke beträgt ${\displaystyle 6/5}$.[8]

Eine Instanz mit ${\displaystyle z_{C}=z_{M}=12{,}8}$ und ${\displaystyle z_{D}=14}$ ist diese: ${\displaystyle {\big (}34;2700;}$ ${\displaystyle 2180,2176,2174,1640,1632,1628,1392,1384,1380,912,904,900,898,896,894,892,664,660,658,656,654}$, ${\displaystyle 652,540,536,534,532,530,528,265,263,262,261,260,259)^{\top };{\mathbf {e} }+{\mathbf {e} }^{11}+{\mathbf {e} }^{12}+4{\mathbf {e} }^{23}{\big )}}$

Der Nachweis, d​ass die Ganzzahl-Aufrundungseigenschaft n​icht gilt, erfolgte m​it Schnittebenenverfahren.[16]

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

Inzwischen konnten mit Hilfe zweier Konstruktionssätze unter anderem Instanzen mit folgenden Werten für ${\displaystyle \Delta }$ gefunden werden:[17]

${\displaystyle {\begin{array}{c|*{12}c}m&1&3&5&6&7&8&10&14&16&18&28\\\hline \\[-2ex]\Delta &<1&{\frac {137}{132}}&{\frac {16}{15}}&{\frac {38}{35}}&{\frac {11}{10}}&{\frac {10}{9}}&{\frac {149}{132}}&{\frac {51}{44}}&{\frac {7}{6}}&{\frac {13}{11}}&{\frac {6}{5}}\end{array}}}$

Erster Konstruktionssatz: Die Instanz ${\displaystyle E=(m;L;{\mathbf {l} };{\mathbf {b} })}$ mit rationalen Längen ${\displaystyle L>l_{1}>\cdots >l_{m}>0}$ weise die Lücke ${\displaystyle \Delta (E)\geq 1}$ auf. Sei ${\displaystyle p\in {\mathbb {N} },p\geq 2}$. Ferner sei ${\displaystyle q\geq 2/l_{m}}$ so gewählt, dass für jeden Vektor ${\displaystyle {\mathbf {u} }\in {\mathbb {Z} }_{+}^{m}}$ mit ${\displaystyle {\mathbf {u} }^{\top }{\mathbf {l} }>L}$ und ${\displaystyle {\mathbf {u} }\leq {\mathbf {b} }}$ auch ${\displaystyle q*({\mathbf {u} }^{\top }{\mathbf {l} }-L)>1}$ gilt. Dann besitzt die Instanz ${\displaystyle \left(m+3;p*(qL+1);(p+(p-1)qL,qL+1,q(L-l_{m})+2,ql_{1},\dots ,ql_{m})^{\top };\left(\left\lceil z_{C}(E)\right\rceil ,p-1,1,b_{1},\dots ,b_{m}\right)^{\top }\right)}$ eine Lücke größer oder gleich ${\displaystyle 1+\left(\left\lceil z_{C}(E)\right\rceil -z_{C}(E)\right)/p\geq 1}$.[10]

Sind alle Daten ganzzahlig, erfüllt ${\displaystyle q:=2}$ stets die Voraussetzungen, da jede unzulässige Variante ${\displaystyle \mathbf {u} }$ mindestens eine Einheit zu viel Material benötigt. Die Anwendung dieses Konstruktionssatzes mit ${\displaystyle p=q=2}$ auf die Instanzen ${\displaystyle \left(3;30;(15,10,6)^{\top };(1,2,4)^{\top }\right)}$, ${\displaystyle \left(5;60;(30,22,20,19,12)^{\top };(1,1,1,1,2)^{\top }\right)}$ und das am Anfang angegebene illustrierte Beispiel, die die Lücken ${\displaystyle 31/30}$, ${\displaystyle 16/15}$ bzw. ${\displaystyle 11/10}$ aufweisen, ergibt die Instanzen ${\displaystyle \left(6;122;(62,61,50,30,20,12)^{\top };(2,1,1,1,2,4)^{\top }\right)}$, ${\displaystyle \left(8;242;(122,121,98,60,44,40,38,12)^{\top };(2,1,1,1,1,1,1,2)^{\top }\right)}$ und ${\displaystyle \left(10;842;(422,421,338,210,148,146,140,136,128,84)^{\top };(3,1,1,1,1,1,2,1,1,2)^{\top }\right)}$ mit den Lücken ${\displaystyle 38/35}$, ${\displaystyle 10/9}$ und ${\displaystyle 39/35}$.

Vor weiteren Konstruktionen für Instanzen mit großer Lücke ${\displaystyle \Delta }$ erklären wir zusammengesetzte Instanzen. Für zwei Instanzen ${\displaystyle E_{1}=\left(m_{1};L_{1};{\mathbf {l} }^{1};{\mathbf {b} }^{1}\right)}$ und ${\displaystyle E_{2}=\left(m_{2};L_{2};{\mathbf {l} }^{2};{\mathbf {b} }^{2}\right)}$ gelte zunächst ${\displaystyle L_{1}=L_{2}}$. In diesem Fall bedeutet die zusammengesetzte Instanz ${\displaystyle E:=E_{1}\oplus E_{2}}$ den Auftrag, alle Teile aus ${\displaystyle E_{1}}$ und ${\displaystyle E_{2}}$ in den jeweils geforderten Stückzahlen aus dem einheitlichen Material der Länge ${\displaystyle L:=L_{1}=L_{2}}$ zuzuschneiden. In der Situation ${\displaystyle L_{1}\neq L_{2}}$ 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: ${\displaystyle \left(2;10;(5,2)^{\top };(1,2)^{\top }\right)\oplus \left(5;210;(74,73,70,68,64)^{\top };(1,1,2,1,1)^{\top }\right)}$ ist genau die obige mit der Abbildung illustrierte Beispielinstanz ${\displaystyle \left(7;210;(105,74,73,70,68,64,42)^{\top };(1,1,1,2,1,1,2)^{\top }\right)}$. Hier addieren sich die Lücken 0,1 und 1,0 zu 1,1.

Spezielle parametrisierte Instanzen mit Lücke ${\displaystyle \Delta =1}$ sind die folgenden:

• ${\displaystyle \left(5;75+3t;(29+t,28+t,25+t,23+t,19+t)^{\top };(1,1,2,1,1)^{\top }\right),t>-17\lor t\in (-19,-18)}$
• ${\displaystyle \left(7;75+3t;(35+t,31+t,29+t,25+t,23+t,22+t,21+t,20+t,19+t)^{\top };{\mathbf {e} }\right),t>-19,t\notin \{-18,-17,-15\}}$
• ${\displaystyle E_{0}(p,q):=\left(9;37+3p+q;(25+p+q,21+p+q,19+p+q,11+p,9+p,8+p,7+p,6+p,5+p)^{\top };{\mathbf {e} }\right),0\leq p\leq q}$
• ${\displaystyle E_{1}(p,q):=\left(8;33+3p+q;(21+p+q,19+p+q,15+p+q,10+p,9+p,7+p,6+p,4+p)^{\top };{\mathbf {e} }+{\mathbf {e} }^{6}\right),0\leq p\leq q,p,q\in \mathbb {N} }$

Diese Instanzen erweisen sich als nützlich zur Konstruktion großer Lücken. Die Teilelängen der beiden ersten Instanzen nähern sich ${\displaystyle L/3}$ für ${\displaystyle t\to \infty }$, während in der dritten Instanz das vierte bis neunte Teil relativ klein sind. Für beliebige ${\displaystyle r,s\in \mathbb {R} }$ mit ${\displaystyle 0\leq r<s\leq 1/4}$ gibt es natürliche Zahlen ${\displaystyle p}$, ${\displaystyle q}$, so dass ${\displaystyle rL<l_{i}\leq sL}$ für ${\displaystyle i\in \{4,\dots ,9\}}$ zutrifft. Analoges gilt für ${\displaystyle E_{1}}$.

Zweiter Konstruktionssatz: In der Instanz ${\displaystyle E=(m;L;{\mathbf {l} };{\mathbf {b} })}$ mit ${\displaystyle l_{1}>\cdots >l_{m-1}>2l_{m}}$ und ${\displaystyle L/4\geq l_{m}}$ ist ausdrücklich auch ${\displaystyle b_{m}=0}$ erlaubt. Erhöht man ${\displaystyle b_{m}}$ um 1, so nehme der optimale Zielfunktionswert ${\displaystyle z_{D}}$ der ganzzahligen Aufgabe (2)–(4) zu. Dann gibt es natürliche Zahlen ${\displaystyle p}$, ${\displaystyle q}$ mit ${\displaystyle p\leq q}$, so dass die zusammengesetzte Instanzen ${\displaystyle E\oplus E_{0}(p,q)}$ und ${\displaystyle E\oplus E_{1}(p,q)}$ die Lücke ${\displaystyle 1+\Delta (E)}$ aufweisen,[8] vgl. auch[12]

Beispiel: Die Instanz ${\displaystyle E:=\left(3;132;(44,33,12)^{\top };(2,3,5)^{\top }\right)}$ erfüllt die Voraussetzungen, denn in keiner Optimallösung des Problems (2)–(4) findet sich eine Zuschnittvariante mit mindestens zwölf Einheiten Verschnitt. Mit ${\displaystyle E_{0}(73,668)\oplus E}$ entsteht die Instanz ${\displaystyle \left(11;924;(766,762,760,308,231,84,82,81,80,79,78)^{\top };(1,1,1,2,3,6,1,1,1,1,1)^{\top }\right)}$ mit Lücke ${\displaystyle 149/132}$.

Die Annahme ${\displaystyle b_{m}=0}$ bedeutet wegen ${\displaystyle l_{m-1}>2l_{m}}$, 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 ${\displaystyle 7/6}$ nicht mit ${\displaystyle E_{0}(p,q)\oplus \left(2;6;(3,2)^{\top };(1,1)^{\top }\right)}$ 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 ${\displaystyle L/5}$ hinzugefügt werden. Die Längen der Teile Nr. 4–28 verhalten sich zur Länge des Ausgangsmaterials ungefähr wie ${\displaystyle 27:45}$, ${\displaystyle 23:45}$, ${\displaystyle 15:45}$, ${\displaystyle 11:45}$ und ${\displaystyle 9:45}$. Betrachtet man annähernd gleich lange Teile als identisch, entsteht eine Modellinstanz, die die Voraussetzungen des zweiten Konstruktionssatzes erfüllt, nämlich

${\displaystyle E_{M}:=\left(5;45;(27,23,15,11,9)^{\top };(3,3,9,6,10)^{\top }\right)}$

mit der Zusatzbedingung, dass die gemäß ${\displaystyle 45=27+2*9=23+2*11=3*15}$ verschnittfreien Varianten je einmal nicht benutzt werden dürfen. In Optimallösungen des ganzzahligen Problems (2)–(4) für die Modellinstanz ${\displaystyle E_{M}}$ wird der Gesamtverschnitt von neun Längeneinheiten in ${\displaystyle 3+2+4}$ oder ${\displaystyle 3+1+1+4}$ aufgeteilt, und wegen ${\displaystyle 4<9/2}$ ist die Verschnittbedingung erfüllt. Anstelle dieser Plausibilitätserklärung müssen für die fertig konstruierten Instanzen exakte Verfahren eingesetzt werden, um ${\displaystyle \Delta >1}$ 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 ${\displaystyle 6/5}$ aufgebaut werden; mit dem ersten wurden es ${\displaystyle 39/35\approx 1{,}1143}$.

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 ${\displaystyle E_{1}}$ aus ${\displaystyle E_{0}}$ 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 ${\displaystyle (9;L;{\mathbf {l} };{\mathbf {e} })}$ mit ${\displaystyle z_{D}>3}$ seien die Zuschnittvarianten ${\displaystyle {\mathbf {e} }^{1}+2{\mathbf {e} }^{4}}$, ${\displaystyle {\mathbf {e} }^{2}+2{\mathbf {e} }^{5}}$, ${\displaystyle {\mathbf {e} }^{3}+2{\mathbf {e} }^{6}}$, ${\displaystyle {\mathbf {e} }^{1}+{\mathbf {e} }^{8}+{\mathbf {e} }^{9}}$, ${\displaystyle {\mathbf {e} }^{2}+{\mathbf {e} }^{7}+{\mathbf {e} }^{9}}$ und ${\displaystyle {\mathbf {e} }^{3}+{\mathbf {e} }^{7}+{\mathbf {e} }^{8}}$ zulässig. Dann gilt ${\displaystyle l_{1}\neq l_{2}}$, ${\displaystyle l_{4}\neq l_{5}}$, ${\displaystyle l_{5}\neq l_{7}}$, ${\displaystyle l_{6}\neq l_{7}}$, ${\displaystyle l_{7}\neq l_{8}}$. Gilt außerdem ${\displaystyle l_{4}=l_{7}}$, so folgt ${\displaystyle l_{5}\neq l_{8}}$, ${\displaystyle l_{6}\neq l_{9}}$, ${\displaystyle l_{1}+l_{5}+l_{6}>L}$, ${\displaystyle 2l_{1}>l_{2}+l_{3}}$ und ${\displaystyle z_{M}<3}$.

Minimale Instanzen ohne Ganzzahl-Aufrundungseigenschaft

Wir setzen ohne Beschränkung der Allgemeinheit voraus, dass sämtliche Daten ganzzahlig sind. Dann kann die Minimalität einer Instanz ${\displaystyle (m;L;{\mathbf {l} };{\mathbf {b} })}$ mit ${\displaystyle \Delta \geq 1}$ immer noch verschieden verstanden werden:

• minimale Anzahl ${\displaystyle m}$ verschiedener Teilelängen: ${\displaystyle \left(3;30;(15,10,6)^{\top };(1,2,4)^{\top }\right)}$ mit ${\displaystyle \Delta =31/30}$ ist so eine Instanz. Wegen ${\displaystyle \Delta <\max\{1,\,m-1\}}$ musste ${\displaystyle m>2}$ sein.
• minimale Länge ${\displaystyle L}$ des Ausgangsmaterials: Bisher (Stand 2007) ist hier nur ${\displaystyle \left(5;16;(10,8,7,3,2)^{\top };(1,1,1,1,2)^{\top }\right)}$ mit ${\displaystyle z_{C}=2}$ bekannt; bei der Zusatzforderung ${\displaystyle m\leq 4}$ wäre zum Beispiel ${\displaystyle \left(4;18;(9,7,6,4)^{\top };(1,1,2,2)^{\top }\right)}$ zu nennen. Ob auch kleinere ${\displaystyle L}$ als 16 bzw. 18 möglich sind, ist noch offen. Im Teilbarkeitsfall wird ${\displaystyle L=30}$.
• minimale Anzahl insgesamt zuzuschneidender Teile ${\displaystyle {\mathbf {e} }^{\top }\mathbf {b} }$ 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 ${\displaystyle L\geq 18}$ wird. Entsprechende Instanzen sind ${\displaystyle \left(4;18;(10,9,6,4)^{\top };(1,1,2,1)^{\top }\right)}$ und ${\displaystyle \left(5;18;(12,9,7,4,3)^{\top };{\mathbf {e} }\right)}$, jeweils mit ${\displaystyle z_{C}=2}$.

Online-Optimierung

Bei Online-Optimierungsproblemen werden d​ie Daten e​rst im Laufe d​er Optimierung bekanntgegeben, z​um Beispiel w​enn kontinuierlich e​in Prozess optimal gesteuert werden soll. In s​o einem Falle w​ird nicht n​ur verlangt, e​ine möglichst g​ute zulässige Lösung i​n Echtzeit z​u liefern, sondern d​ie Teile können n​och nicht einmal vorher n​ach ihrer Größe sortiert werden. Mitunter dürfen wenige Teile zurückgestellt werden, s​o dass zumindest für d​iese Teile einige Freiheit besteht. Es versteht s​ich von selbst, d​ass bei Online-Optimierungsproblemen e​ine exakte Optimierung ausgeschlossen i​st und m​an sich m​it schnellen Heuristiken begnügen muss.

Einen Überblick über Näherungsalgorithmen u​nd ihre Güte g​ibt zum Beispiel.[18] Einige Ergebnisse a​us diesem Übersichtsartikel werden i​m Folgenden vorgestellt.

Das Problem (2)–(4) werde mit dem Approximationsalgorithmus ${\displaystyle A}$ bearbeitet. Für eine beliebige Instanz ${\displaystyle E}$ sei der ermittelte Zielfunktionswert ${\displaystyle z_{A}(E)}$. Ein absolutes Güteverhältnis im ungünstigsten Fall ergibt sich zu ${\displaystyle R_{A}:=\sup \limits _{E}\left\{z_{A}(E)/z_{D}(E)\right\}}$. Für eine asymptotische Güteeinschätzung werden Folgen von Instanzen ${\displaystyle E}$ mit ${\displaystyle z_{D}(E)\to \infty }$ betrachtet. Der entsprechende Limes superior des Verhältnisses ${\displaystyle z_{A}(E)/z_{D}(E)}$ werde mit ${\displaystyle R_{A}^{\infty }}$ 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 ${\displaystyle z_{NF}}$ fast ${\displaystyle 2*z_{D}}$ als erzielten Zielfunktionswert, etwa wenn immer abwechselnd Teile der Größen ${\displaystyle L/2}$ und ${\displaystyle \varepsilon >0}$ mit sehr kleinem ${\displaystyle \varepsilon }$ gepackt werden sollen. Folglich ist ${\displaystyle R_{NF}^{\infty }=2}$.

Die Heuristiken First Fit (FF) und Best Fit (BF) sind ungefähr gleich gut; sowohl ${\displaystyle z_{FF}<z_{BF}}$ als auch ${\displaystyle z_{FF}>z_{BF}}$ 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 ${\displaystyle L/2+\varepsilon ,L/3+\varepsilon ,L/7+\varepsilon ,L/43+\varepsilon ,\dots }$ mit sehr kleinem positivem ${\displaystyle \varepsilon }$ in der Reihenfolge monoton wachsender Größe gepackt werden sollen. Ein noch ungünstigeres Beispiel enthält[19] mit ${\displaystyle z_{D}(E)\leq 10N+1,N\in \mathbb {N} }$ (beliebig) und ${\displaystyle z_{FF}(E)=z_{BF}(E)=17N}$. Da gleichzeitig gemäß jenem Artikel ${\displaystyle z_{FF}(E)\leq z_{D}*17/10+2}$ und ${\displaystyle z_{BF}(E)\leq z_{D}*17/10+2}$ für jede Instanz ${\displaystyle E}$ gilt, folgt ${\displaystyle R_{FF}^{\infty }=R_{BF}^{\infty }=17/10}$.

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 ${\displaystyle R_{AF}^{\infty }\geq R_{FF}^{\infty }}$.

Falls immer höchstens ${\displaystyle k}$ Packvarianten gleichzeitig offen sein dürfen, wobei ${\displaystyle k}$ eine endliche Konstante ist, schränkt das die möglichen Heuristiken ein. Unter dieser Bedingung wird für Online-Algorithmen ${\displaystyle A}$ stets ${\displaystyle R_{A}^{\infty }>1{,}69103}$.

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 ${\displaystyle R_{A}^{\infty }<8/5}$ erzielt werden, jedoch existiert kein Online-Algorithmus mit ${\displaystyle R_{A}^{\infty }<1{,}540}$. Bessere Verhältnisse können erzielt werden, wenn die zu packenden Teile relativ klein gegenüber ${\displaystyle L}$ 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 ${\displaystyle z_{A}\leq z_{D}*11/9+1}$. Die absolute Güteeinschätzung ist hier ${\displaystyle R_{A}=3/2}$. 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 ${\displaystyle \varepsilon >0}$ gibt es Approximationsalgorithmen mit ${\displaystyle R_{A}^{\infty }<1+\varepsilon }$. Darüber hinaus existieren Approximationsalgorithmen mit polynomialer Komplexität und ${\displaystyle R_{A}^{\infty }=1}$. Allerdings wächst die absolute Differenz ${\displaystyle z_{A}-z_{D}}$ 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

Falls mehrere verschiedene Materialien mit Längen ${\displaystyle L_{1},\dots ,L_{M}}$ und Preisen ${\displaystyle p_{1},\dots ,p_{M}}$ gegeben sind, sind anstelle des Spaltengenerierungsproblems (7) mehrere Rucksackprobleme zu lösen, nämlich mit Rucksackkapazität ${\displaystyle L_{k}}$ für ${\displaystyle k=1,\dots ,M}$. Eine Verbesserung des Zielfunktionswertes der stetigen Relaxation ist möglich, wenn ${\displaystyle {\mathbf {g} }^{\top }{\mathbf {a} }>p_{k}}$ 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 k​ann umgekehrt gefragt werden, welche Vorräte verschieden langen Ausgangsmaterials gekauft werden müssen, u​m mehrere Zuschnittaufträge möglichst billig erledigen z​u können. Dabei w​ird angenommen, d​ass längere Stücke Material s​tets teurer s​ind als kürzere u​nd aus organisatorischen Gründen d​ie Zuschnittaufträge n​icht vermischt werden dürfen. Das heißt, a​us einem Stück Material dürfen Teile i​mmer nur für e​inen Auftrag geschnitten werden. Dieses Sortimentsproblem w​ird einschließlich numerischer Experimente i​n der Habilitationsschrift[21] behandelt.

Eine andere Verallgemeinerung d​es eindimensionalen Zuschnittproblems i​st das mehrdimensionale Vektorpackproblem, d​as aus Planungsaufgaben entstehen kann. Anstelle d​er Zulässigkeitsbedingung (1) werden h​ier mehrere derartige Bedingungen gleichzeitig gestellt, z​um Beispiel d​ass eine gewisse geometrische Länge u​nd zugleich e​in bestimmtes Gesamtgewicht d​er gepackten Teile n​icht überschritten werden dürfen. Ebenso könnte a​uch die Zeit z​u 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 ${\displaystyle L\times W}$ mit fester Breite ${\displaystyle L}$ und möglichst kleiner Höhe ${\displaystyle W}$ 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 ${\displaystyle k<m}$ verschiedene Teilesorten in Bearbeitung sind, wobei die positive ganze Zahl ${\displaystyle k}$ fest vorgegeben ist. Bevor also die ${\displaystyle (k+1)}$-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 e​ine Vielzahl weiterer Pack- u​nd Zuschnittprobleme, für d​ie das eindimensionale Problem (2)–(4) a​uch als Relaxation dienen kann, w​ird 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 ${\displaystyle c}$ die Kosten für ein Stück Rohmaterial sowie ${\displaystyle d_{j}}$ die einmaligen Kosten, die für jede Zuschnittsvariante anfallen, muss hier an Stelle der Gleichung (2) folgender Wert minimiert werden:

${\displaystyle z:=\sum _{j\in J}\left(c\cdot x_{j}+{\mathbf {1} }_{\{x_{j}>0\}}\cdot d_{j}\right)\to \min !}$

(8)

Dieses Problem g​ilt seit d​en 1960er Jahren a​ls ungelöst. Die Artikel[23][24] befassen s​ich mit d​em Problem, i​ndem sie d​ie nicht stetige Funktion (8) d​urch stetige Funktionen approximieren u​nd mit nicht-linearer Optimierung arbeiten.

Zur Geschichte

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 ${\displaystyle z_{D}=\lceil z_{C}\rceil }$, 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 ${\displaystyle \Delta =z_{D}-z_{C}\geq 1}$ 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 ${\displaystyle \left(3;30;(15,10,6)^{\top };(1,2,4)^{\top }\right)}$ 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 ${\displaystyle \Delta >1}$ 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

Neben d​en Fragestellungen a​us der Komplexitätstheorie besteht z​um eindimensionalen Zuschnittproblem n​och einiger Forschungsbedarf, z​um Beispiel:

• Bezeichnet ${\displaystyle P(m)}$ die Menge aller Instanzen des eindimensionalen Zuschnittproblems mit höchstens ${\displaystyle m}$ verschiedenen Teilelängen, fragen wir nach ${\displaystyle g(m):=\sup \limits _{E\in P(m)}\left\{z_{D}(E)-z_{C}(E)\right\}}$. Wie kann ${\displaystyle g(m)}$ möglichst scharf abgeschätzt werden?
• Die gleichen Fragen stellen wir für Spezialfälle wie den Teilbarkeitsfall oder wenn eine ganze Zahl ${\displaystyle k>1}$ mit ${\displaystyle L/k\geq l_{i}>L/(k+2)}$ für alle ${\displaystyle i\in I}$ existiert oder wenn kein Teil länger als die Hälfte des Ausgangsmaterials ist.
• Wenn insgesamt genau fünf Teile zuzuschneiden sind, d. h. ${\displaystyle {\mathbf {e} }^{\top }{\mathbf {b} }=5}$, kann man ausrechnen, dass von allen diesen Instanzen der Anteil der Instanzen mit Lücke ${\displaystyle \Delta \geq 1}$ 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 ${\displaystyle z_{D}-z_{C}}$ aufweisen als die zugehörigen residualen Instanzen?
• Für welche minimalen ${\displaystyle L}$ bei durchgängig ganzzahligen Daten kann ${\displaystyle \Delta \geq 1}$ werden? Sind für ${\displaystyle m=3,4,5}$ kleinere ${\displaystyle L}$ als 30, 18 und 16 möglich?

Quellenangaben

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. 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. 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. 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. 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

• 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