Zuschnittproblem

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

Problemstellung und grundlegende Definitionen

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

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

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

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

${\mathbf a}^\top{\mathbf l}\le L$

(1)

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

$z:=\sum_{j\in J}x_j\to\min!$

(2)

bei

$\sum_{j\in J}x_j*{\mathbf a}^j={\mathbf b}$

(3)

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

(4)

Dieses Problem ist stets lösbar, wenn für alle Teilelängen $l_i\le 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 die Anzahl der zulässigen Varianten und damit der Variablen in der Aufgabe (2)–(4) oft sehr groß ist, wurde auch nach alternativen Modellen gesucht. Ein solches besteht u. a. in der Formulierung als Optimierung eines Flusses in einem Netzwerk. Jenes Fluss-Modell stellt sich als äquivalent zur obigen Problemformulierung heraus. Wegen Einzelheiten sei z. B. auf ^[1] verwiesen.

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

$z_M:={\mathbf l}^\top{\mathbf b}/L$

dar. Allerdings ist diese Schranke meist zu ungenau, denn die Differenz 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:

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

(5)

• Einschränkung auf eigentliche Varianten:

$\sum_{j\in J}x_j\to\min!$  bei $\sum_{j\in J}x_j*{\mathbf a}^j={\mathbf b},\;x_j\in{\mathbb R}_+$ für alle $j\in J$ mit xj = 0, falls ${\mathbf a}^j\not\le\mathbf b$

(6)

Die optimalen Zielfunktionswerte beider Relaxationen seien mit z_C und z_E bezeichnet. Dann zeigt man leicht $z_M\le z_C\le z_E\le z_D$. Von besonderem theoretischem Interesse ist die Lücke

Δ: = z_D − z_C.

Es stellt sich heraus, dass es $\mathcal NP$-schwer ist, Δ < 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 $\mathbf a$ höchstens $\lfloor\min\{b_i/a_i:i\in I,\,a_i&amp;amp;gt;0\}\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 $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 $(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 z_M = 304 / 105 < z_C = 2,9 < z_E = 3 + 1 / 15 < z_D = 4. Die Instanz E ergibt die für den Fall, dass kein Teil mehr als die Hälfte des Ausgangsmaterials ausmacht, größte bisher bekannte Lücke Δ = 11 / 10 (Stand 2007).

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

Äquivalente Instanzen

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

Beispiel zur Äquivalenz: Thomas Gau fand bei Testrechnungen die Instanz $(5;10\,000;(5000,3750,3250,3001,2000)^\top;(1,1,1,1,2)^\top)$ mit Lücke 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 $(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 $(5;80;(40,30,26,25,16)^\top;(1,1,1,1,2)^\top)$. Eine weitere äquivalente Instanz entsteht hieraus durch Multiplikation aller Längen mit 3 / 4 und geeignetes Runden, nämlich $(5;60;(30,22,20,19,12)^\top;(1,1,1,1,2)^\top)$.

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

• $l_i\ge l_{i+1}$ für $i\in I\setminus\{m\}$ aufgrund der Sortierung
• $L-{\mathbf a}^\top{\mathbf l}\ge 0$ für jede maximale Variante $\mathbf a$
• ${\mathbf u}^\top{\mathbf l}-L\ge 1$ für jede unzulässige Variante ${\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 l_i oder L gehört. Zuletzt bleiben für die m + 1 gesuchten Längen nur 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 $(4;210;(105,70,42,30)^\top;{\mathbf b})$ äquivalenten Instanzen mit durchgängig ganzzahligen Längen, wobei b_i > 0 für alle $i\in I$ gilt. Offensichtlich ist $\max\{2l_1,3l_2,5l_3,7l_4\}\le L$ zu fordern. Neben den Unzulässigkeitsbedingungen l₁ + l₂ + l₃ > L und 2l₂ + l₃ + l₄ > 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 $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:

$\begin{array}{c|*{6}r} &amp;amp;amp;1 &amp;amp;amp;z_2 &amp;amp;amp;z_3 &amp;amp;amp;z_4 &amp;amp;amp;u_1 &amp;amp;amp;u_2\\\hline L &amp;amp;amp;105 &amp;amp;amp;70 &amp;amp;amp;21 &amp;amp;amp;15 &amp;amp;amp;0 &amp;amp;amp;105\\ l_1 &amp;amp;amp;50 &amp;amp;amp;33 &amp;amp;amp;10 &amp;amp;amp;7 &amp;amp;amp;1 &amp;amp;amp;49\\ l_2 &amp;amp;amp;35 &amp;amp;amp;23 &amp;amp;amp;7 &amp;amp;amp;5 &amp;amp;amp;0 &amp;amp;amp;35\\ l_3 &amp;amp;amp;21 &amp;amp;amp;14 &amp;amp;amp;4 &amp;amp;amp;3 &amp;amp;amp;0 &amp;amp;amp;21\\ l_4 &amp;amp;amp;15 &amp;amp;amp;10 &amp;amp;amp;3 &amp;amp;amp;2 &amp;amp;amp;0 &amp;amp;amp;15\\ z_1 &amp;amp;amp;5 &amp;amp;amp;4 &amp;amp;amp;1 &amp;amp;amp;1 &amp;amp;amp;-2 &amp;amp;amp;7\\ \end{array}$

Demzufolge darf die Schlupfvariable u₁ nicht beliebig unabhängig von den anderen erhöht werden. Tauscht man u₁ gegen z₁, geht die Ganzzahligkeit von l₁ verloren, falls alle Schlupfvariablen der Nichtbasis danach auf 0 gesetzt werden. Insgesamt ergibt sich, dass L und $l_2,l_3,l_4\,$ mit den vier Parametern $z_2,z_3,z_4,u_2\in\mathbb N$ beschrieben werden können, während $50+33z_2+10z_3+7z_4+49u_2\le l_1\le 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 l₁ = l₂ = l₃ = 5 und b₁ = b₂ = b₃ = 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 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 $k*{\mathbf e}^i$ mit $k\le L/l_i,\;k\in\mathbb N$ ist, wobei ${\mathbf e}^i$ den i-ten Basis-Einheitsvektor des ${\mathbb R}^m$ bezeichnet, $i\in I$.

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

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

Für obige Instanz gilt die Ganzzahl-Aufrundungseigenschaft $z_D=\lceil z_C\rceil$ nicht. Da alle bisherigen Erfahrungen darauf schließen ließen, dass die Lücke Δ für beliebige Instanzen des eindimensionalen Zuschnittproblems (2)–(4) stets klein ist, wurde der Begriff der modifizierten Ganzzahl-Aufrundungseigenschaft (engl. modified integer round-up property, MIRUP) geprägt. Eine Instanz weist diese Eigenschaft auf, wenn $z_D\le\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 E des Teilbarkeitsfalls gilt Δ(E) = z_D(E) − z_C(E) < 7 / 5. Sind sämtliche Teile größer als 1 / 19 des Ausgangsmaterials, gilt sogar Δ(E) < 5 / 4.

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

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

Lösung der stetigen Relaxation

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

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

(7)

zu lösen, wobei ${\mathbf g}^\top={\mathbf c}_B^\top{\mathbf B}^{-1}$ gilt. Eine einfache Rechenkontrolle besteht in $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. Simplexverfahren#Zeilenauswahl). Um diese Regel umzusetzen, hebt man jede gefundene Variante auf und prüft, bevor das Spaltengenerierungsproblem (7) gelöst wird, ob früher eine Variante $\mathbf a$ abgespeichert wurde, für die ${\mathbf g}^\top{\mathbf a}&amp;amp;gt;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 2:2:1. Die Materialausnutzung ist zu maximieren. Das bedeutet, hier ist eine Optimallösung der stetigen Relaxation (5) von der Instanz $(3;11;(6,4,1)^\top;(2,2,1)^\top)$ gesucht. Für die erste Basis werden maximale elementare Varianten gewählt, das sind ${\mathbf a}^1=(1,0,0)^\top={\mathbf e}^1$, ${\mathbf a}^2=(0,2,0)^\top=2{\mathbf e}^2$ und ${\mathbf a}^3=(0,0,11)^\top=11{\mathbf e}^3$, so dass $\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 ($\bigstar$) gekennzeichnet. Aus Gründen der einfacheren Programmierung wurden die rechten Seiten und der Vektor ${\mathbf g}^\top$ in der ersten Spalte bzw. Zeile untergebracht. Ganz rechts steht jeweils die transformierte neue Spalte, bestehend aus $\bar{c}$ und $-{\mathbf B}^{-1}\mathbf a$.

$\begin{array}{l|c|ccc|c||l|c|ccr|c||l|c|rcr} S_0&amp;amp;amp;1 &amp;amp;amp;&amp;amp;amp;&amp;amp;amp;&amp;amp;amp;&amp;amp;amp;S_1&amp;amp;amp;1 &amp;amp;amp;&amp;amp;amp;&amp;amp;amp;&amp;amp;amp;&amp;amp;amp;S_2&amp;amp;amp;1 \\\hline z&amp;amp;amp;\frac{34}{11}&amp;amp;amp;1&amp;amp;amp;\frac{1}{2}&amp;amp;amp;\frac{1}{11}&amp;amp;amp;-\frac{13}{22}&amp;amp;amp;z&amp;amp;amp;\frac{5}{2}&amp;amp;amp;1&amp;amp;amp;\frac{1}{2}&amp;amp;amp;-\frac{1}{2}&amp;amp;amp;-\frac{1}{2}&amp;amp;amp;z&amp;amp;amp;2&amp;amp;amp;\frac{1}{2}&amp;amp;amp;\frac{1}{2}&amp;amp;amp;0 \\[1mm]x_1&amp;amp;amp;2 &amp;amp;amp;1&amp;amp;amp;&amp;amp;amp;&amp;amp;amp; -1 &amp;amp;amp;x_1&amp;amp;amp;1&amp;amp;amp;1&amp;amp;amp;&amp;amp;amp;-1 &amp;amp;amp;-1\,\bigstar &amp;amp;amp;x_5&amp;amp;amp;1&amp;amp;amp;1&amp;amp;amp;&amp;amp;amp;-1 \\[1mm]x_2&amp;amp;amp;1 &amp;amp;amp;&amp;amp;amp;\frac{1}{2}&amp;amp;amp;&amp;amp;amp;-\frac{1}{2} &amp;amp;amp;x_2&amp;amp;amp;\frac{1}{2}&amp;amp;amp;&amp;amp;amp;\frac{1}{2}&amp;amp;amp;-\frac{1}{2}&amp;amp;amp;-\frac{1}{2}&amp;amp;amp;x_2&amp;amp;amp;0&amp;amp;amp;-\frac{1}{2}&amp;amp;amp;\frac{1}{2}&amp;amp;amp;0 \\[1mm]x_3&amp;amp;amp;\frac{1}{11}&amp;amp;amp;&amp;amp;amp;&amp;amp;amp;\frac{1}{11}&amp;amp;amp;-\frac{1}{11}\,\bigstar&amp;amp;amp;x_4&amp;amp;amp;1&amp;amp;amp;&amp;amp;amp;&amp;amp;amp;1&amp;amp;amp;0 &amp;amp;amp;x_4&amp;amp;amp;1&amp;amp;amp;&amp;amp;amp;&amp;amp;amp;1 \\\end{array}$

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

Die Varianten ${\mathbf a}^4$ und ${\mathbf a}^5$ sind folglich im Verhältnis 1:1 zu schneiden. Beim letzten Austausch war x₁ (und nicht x₂) 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 g_i ($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 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 ${\mathbf x}^C$ eine mittels Simplexverfahren ermittelte optimale Basislösung der stetigen Relaxation (5). Ersetzt man in der Instanz $E:=(m;L;{\mathbf l};{\mathbf b})$ den Vektor der Bedarfszahlen durch ${\mathbf b}-\sum_{j\in J}\lfloor x_j^C\rfloor*{\mathbf a}^j$, entsteht eine sogenannte residuale Instanz E^(r). Dabei dürfen durchaus auch Nullen im Bedarfsvektor auftreten. Bei vielen Abschätzungen der Lücke Δ hilft folgendes

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

$z_D(E^{(r)})&amp;amp;lt;p*z_C(E^{(r)})+q\Longrightarrow\Delta(E^{(r)})&amp;amp;lt;\frac{p-1}{p}*m+\frac{q}{p}=m*(1-\frac{1}{p})+\frac{q}{p}.$^[12]

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

$\Delta(E^{(r)})\le m-z_C(E^{(r)}).$

Zum (p − 1)-fachen dieser Ungleichung addieren wir die gemäß Voraussetzung gültige Ungleichung Δ(E^(r)) < (p − 1) * z_C(E^(r)) + q und erhalten p * Δ(E^(r)) < (p − 1) * m + q. Division durch p liefert die Behauptung.

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

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

Ein Näherungsalgorithmus mittels Relaxation

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

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

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

Die Farley-Schranke

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

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

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

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

$z_C\ge{\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 sich bei Fortsetzung der Optimierung dem optimalen Zielfunktionswert der Relaxation nähert. Analog sieht die Schranke für (6) aus.

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

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

(k,k + 1)-Instanzen

Sei k eine positive ganze Zahl. Die Instanz $E:=(m;L;{\mathbf l};{\mathbf b})$ heiße (k,k + 1)-Instanz, falls $L/(k+2)&amp;amp;lt;l_i\le L/k$ für alle $i\in I$ zutrifft, also jedes Teil genau k- oder (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 Δ = 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 p-Teile-Variante verstehen wir eine beliebige zulässige Zuschnittvariante $\mathbf a$, mit der genau p Teile zugeschnitten werden ($p\le k+1)$, d. h. ${\mathbf e}^\top{\mathbf a}=p$, wobei ${\mathbf e}\in{\mathbb R}^m$ für den aus lauter Einsen bestehenden Vektor steht.

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

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

$(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)$,

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

Für folgende Instanzen gilt jeweils z_M < z_C = 2 und z_D = 3:

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

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

• $(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)$ bei $3\le k\le 7$
• $(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)$ bei $k\ge 8$.

Komplementäre Instanzen

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

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

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

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

$t&amp;amp;gt;\max\{L-(k+2)*l_m,\;k*l_1-L\}$

aus. Die zu E(t) komplementäre Instanz E'(t) definieren wir als

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

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

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

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

Bevor (2,3)-Instanzen mit Lücke Δ > 1 angegeben werden, demonstrieren wir, wie vielfältig der Nenner von z_C werden kann. Dazu sei $p\in\mathbb N$ beliebig gewählt. Die Festlegungen m: = 2p + 1, L: = 2^m + 3, l₁: = (L + 1) / 3 und $l_i:=L-2l_{i-1}\,$ für $i=2,\dots,m$ liefern eine (2,3)-Instanz $(m;L;{\mathbf l};{\mathbf e})$ mit $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

$(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})$

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

$z_C\stackrel{?}{=}\frac{2^{2p-1}-2^{p-2}}{3*2^{p-1}-1}=\frac{m^2/2-m/4}{\frac{3}{2}m-1}=\frac{1}{18}*\frac{(6m+1)*(\frac{3}{2}m-1)+1}{\frac{3}{2}m-1}$

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

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

• $(5;90;(42,36,31,25,23)^\top;{\mathbf e})$, z_C = 1 + 11 / 14
• $(8;90;(43,42,36,31,26,25,24,23)^\top;{\mathbf e})$, z_C = 2 + 14 / 17
• $(8;128;(52,50,46,43,42,40,36,34)^\top;{\mathbf e})$, z_C = 2 + 27 / 38
• $(12;187;(78,77,75,72,65,60,58,57,54,53,52,49)^\top;{\mathbf e})$, z_C = 4 + 1 / 26
• $(14;187;(78,77,75,72,69,65,63,60,58,57,53,52,50,49)^\top;{\mathbf e})$, 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 $\Delta\approx 73/72$, nämlich

• $(10;387;(177,145,133,130,129,127,121,113,105,97)^\top;(3,2,2,1,2,2,2,1,1,1)^\top)$, z_C = 6 − 1 / 96
• $(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)$, z_C = 7 − 5 / 384
• $(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)$, z_C = 8 − 7 / 512
• $(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)$, z_C = 9 − 85 / 6144.

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

Rückführung auf einfachere Instanzen

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

Sei $E=(m;L;{\mathbf l};{\mathbf e})$ eine beliebige (k,k + 1)-Instanz. Bezeichnen y_C und y_D die Häufigkeiten aller k-Teile-Varianten in Optimallösungen der Relaxation (5) bzw. des ganzzahligen Problems (2)–(4), gilt $y_D\ge y_C$. Gilt $q:=k*\lceil y_C\rceil&amp;amp;lt;m$, können die q größten Teile in k-Teile-Varianten zugeschnitten werden, und nach deren Abtrennung verbleibt eine Instanz $E'=(m';L;{\mathbf l}';{\mathbf b}')$ mit $\Delta(E)\ge\Delta(E')&amp;amp;gt;\Delta(E)-1/(k+1)$ und $(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 1 / (k + 1) ab. Daraus ergibt sich eine wichtige

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

Beispiel: In der (2,3)-Instanz

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

gilt $z_C\approx 37{,}2217$ und $y_C\approx 1{,}6650$, also $y_D\ge 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 E₂ gilt y_C(E₂) = 0 und z_C(E₂) = 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 34 + 2 / 3. Trennt man nun noch zwei Teile der Länge 3073 ab, ergibt sich für die Restinstanz 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 (k,k + 1)-Instanzen $(m;L;{\mathbf l};{\mathbf e})$ mit $z_C\in\mathbb N$ und m = (k + 1) * z_C betrachtet werden. Ohne Beschränkung der Allgemeinheit seien die Teile nach fallenden Längen geordnet, also $l_1\ge\cdots\ge l_m$. Die Anzahl aller zuzuschneidenden Teile mit Länge oberhalb L / (k + 1) sei g. Für $p=1,\dots,k+1$ bezeichne y_p jeweils die Gesamthäufigkeit aller in einer vorliegenden Optimallösung der stetigen Relaxation (5) vorkommenden Varianten, die genau p Teile aus $\{g+1,\dots,m\}$ (und k + 1 − p größere Teile) enthalten.

Aufgrund dieser Einteilung der Teile in größere und kleinere ergibt sich $z_C=\sum\limits_{p=1}^{k+1}y_p$ und $g=\sum\limits_{p=1}^{k+1}(k+1-p)*y_p$, also auch $y_{k+1}\ge z_C-g$. Gilt $y_{k+1}\ge 1$, können die k + 1 größten Teile aus $\{g+1,\dots,m\}$ in einer abgesonderten Variante geschnitten werden, und die Abtrennung dieser Variante ändert die Lücke Δ nicht. Unter Umständen findet man anstelle dieser eine zulässige (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 der (2,3)-Instanz

$E_3:=(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)$

gilt 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 $2{\mathbf e}^6+{\mathbf e}^7$ und ${\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 g < z_C, und nun kann die Variante ${\mathbf e}^6+2{\mathbf e}^7$ einmal abgetrennt werden. (Teil 5 war schon verbraucht.) Das führt auf die Instanz

$E_4:=(10;8195;(3073,2817,2753,2737,2731,2729,2721,2689,2561,2049)^\top;(2,5,5,5,36,5,5,5,5,5)^\top)$

mit z_C(E₄) = 26 und g = 17, so dass noch neunmal die Variante $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, Δ(E₄) = 0 und z_D(E₁) = 38.

A priori-Zulässigkeit von Varianten

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

• $p_q\le g&amp;amp;lt;p_{q+1}\land y_{k+1-q}&amp;amp;gt;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}$
• $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}&amp;amp;gt;k*m$

Bei m = (k + 1) * z_C gilt auch $y_1\ge g-(k-1)*z_C$. Gemäß den Reduktionen im vorigen Abschnitt kann dies erzwungen werden, auch $z_C\in\mathbb N$ und y_{k + 1} < 1. Dies wird im folgenden vorausgesetzt, wenn obige sehr technische Aussagen auf (2,3)-Instanzen angewandt werden. Dann gilt auch y₁ = g − z_C + y₃.

Unter den oben angegebenen Voraussetzungen ist in einer (2,3)-Instanz die Variante ${\mathbf e}^{p_1}+{\mathbf e}^{p_2}+{\mathbf e}^{p_3}$ zulässig, kurz (p₁,p₂,p₃) geschrieben, wenn eine der folgenden Bedingungen zutrifft:

(a) $p_1\le p_2\le g&amp;amp;lt;p_3\land(p_1+p_2+2p_3&amp;amp;gt;2g+6z_C-2y_1$ oder $p_1+p_2+2p_3\ge 8z_C+1)$

(b) $p_1\le g&amp;amp;lt;p_2\le p_3\land(p_1+2p_3&amp;amp;gt;g+6z_C-2y_1$ oder $p_1+2p_3\ge 8z_C-g+1)$

(c) $p_1\le g&amp;amp;lt;p_2\le p_3\land 2p_1+p_2+p_3&amp;amp;gt;6z_C+4y_1$ (erfordert Fallunterscheidung bezüglich y₁)

(d) $2p_1+p_2+3p_3\ge 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 $p_2\le g$ auch (a)-Variante ist und die (a)-Varianten die (b)-Varianten dominieren. Bedingung (a) ist aber bei p₂ > g nicht anwendbar. (a)-Varianten sind bei g = 2z_C am günstigsten, (c)-Varianten bei g = z_C, weil y₁ < 1 wird.

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

Nun seien z_C = 2, m = 6 und g = 4 gegeben. Dann gilt y₁ = 2 und y₂ = y₃ = 0, so dass es die (a)-Varianten (1,4,6), (2,3,6) und (3,4,5) gibt. Wäre 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 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 (k,k + 1)-Instanzen $(m;L;{\mathbf l};{\mathbf e})$ mit $l_1\ge\cdots\ge l_m$, in denen die obigen Reduktionen vorgenommen wurden, wo also auch m = (k + 1) * z_C und $z_C\in\mathbb N$ gilt. Alleine von g, k und z_C abhängige Abschätzungen für z_D werden angegeben.

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

• $\Delta\le\frac{t-1}{k*(k+1)}+1$
• $t\le g-k*\min\{\lfloor\frac{g}{k}\rfloor,\lceil\frac{1+g-(k-1)*z_C}{s}-1\rceil\}$ mit $s=\sum\limits_{i=1}^k\frac{1}{i}$
• $t\le(k+1)*(z_C+1-\lceil(k+1)*(z_C+\frac{1}{2})/(\frac{k*(k+3)}{2}-\sum\limits_{i=3}^{k+1}\frac{k+1}{i})\rceil)$, speziell $t\le 3*\lceil\frac{z_C-1}{4}\rceil$ bei k = 2.

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

Aussagen zum allgemeinen Fall

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

Aus der Betrachtung residualer Instanzen folgt die fast triviale Aussage

$\Delta&amp;amp;lt;\max\{1,\,m-1\}$.

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

$\Delta&amp;amp;lt;\max\{2,\frac{z_M+2}{3}\}$ und $\Delta&amp;amp;lt;\max\{2,\,\frac{m+2}{4}\}$

sowie der Nachweis der Ganzzahl-Aufrundungseigenschaft $z_D=\lceil z_C\rceil$ für alle Instanzen mit $z_M\le 7/4$.^[12] Dagegen ist es eine leichte Übung, Δ < 1 nachzuweisen, falls $\frac{1}{\lceil z_C\rceil}*\mathbf b$ ganzzahlig ist.

Ferner konnte MIRUP, also $z_D\le\lceil z_C\rceil+1$, für folgende Fälle bewiesen werden:^[8]

• $z_M\le 4{,}75\lor 5&amp;amp;lt;z_M\le 5{,}5\lor 6&amp;amp;lt;z_M\le 6{,}25$
• z_C < 11, wenn außerdem alle Teile größer als ein Viertel des Ausgangsmaterials sind.

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

Lemma: Über die Instanz $E:=(m;L;{\mathbf l};{\mathbf b})$ werden b_i > 0 für alle $i\in I$, ferner $l_1&amp;amp;gt;\cdots&amp;amp;gt;l_m$ sowie 2l₁ > L und l₁ + 2l_m > L vorausgesetzt. Gilt l₁ + l_m > L, so sei ${\mathbf a}:={\mathbf e}^1$, andernfalls $t:=\min\{i\in I: l_1+l_i\le L\}$ und ${\mathbf a}:={\mathbf e}^1+{\mathbf e}^t$. Dann besitzen die Instanzen E und $(m;L;{\mathbf l};{\mathbf b}-{\mathbf a})$ die gleiche Lücke Δ, d. h. beim einmaligen Zuschneiden des größten Teils und des ggf. größten dazu passenden Teils ändert sich unter den angegebenen Voraussetzungen die Lücke nicht.

Keine der Voraussetzungen kann weggelassen werden, wie die Gegenbeispiele $E_1:=(4;18;(10,9,6,4)^\top;(1,1,2,1)^\top)$ und $E_2:=(2;6;(3,2)^\top;(1,4)^\top)$ mit Δ(E₁) = 1 und Δ(E₂) = 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 Δ = z_D − z_C.^[15]

Die größte bisher (Stand 2007) erreichte Lücke beträgt 6 / 5.^[8] Eine Instanz mit z_C = z_M = 12,8 und z_D = 14 ist diese: (34;2700;(2180,2176,2174,1640,1632,1628,1392,1384,1380,912,904,900,898,896,894,892,664,660,658,656,654,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})$ Der Nachweis, dass die Ganzzahl-Aufrundungseigenschaft nicht gilt, erfolgte mit Schnittebenenverfahren.^[16]

Sollte Δ für $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 Δ zu vorgegebener oberer Schranke für die Anzahl m verschiedener Teile.

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

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

Erster Konstruktionssatz: Die Instanz $E=(m;L;{\mathbf l};{\mathbf b})$ mit rationalen Längen $L&amp;amp;gt;l_1&amp;amp;gt;\cdots&amp;amp;gt;l_m&amp;amp;gt;0$ weise die Lücke $\Delta(E)\ge 1$ auf. Sei $p\in{\mathbb N}, p\ge 2$. Ferner sei $q\ge 2/l_m$ so gewählt, dass für jeden Vektor ${\mathbf u}\in{\mathbb Z}_+^m$ mit ${\mathbf u}^\top{\mathbf l}&amp;amp;gt;L$ und ${\mathbf u}\le{\mathbf b}$ auch $q*({\mathbf u}^\top{\mathbf l}-L)&amp;amp;gt;1$ gilt. Dann besitzt die Instanz $(m+3;p*(qL+1);(p+(p-1)qL,qL+1,q(L-l_m)+2,ql_1,\dots,ql_m)^\top;(\lceil z_C(E)\rceil,p-1,1,b_1,\dots,b_m)^\top)$ eine Lücke größer oder gleich $1+(\lceil z_C(E)\rceil-z_C(E))/p\ge 1$.^[10]

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

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

Spezielle parametrisierte Instanzen mit Lücke Δ = 1 sind die folgenden:

• $(5;75+3t;(29+t,28+t,25+t,23+t,19+t)^\top;(1,1,2,1,1)^\top),t&amp;amp;gt;-17\lor t\in(-19,-18)$
• $(7;75+3t;(35+t,31+t,29+t,25+t,23+t,22+t,21+t,20+t,19+t)^\top;{\mathbf e}),t&amp;amp;gt;-19,t\notin\{-18,-17,-15\}$
• $E_0(p,q):=(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}),0\le p\le q$
• $E_1(p,q):=(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),0\le p\le 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 L / 3 für $t\to\infty$, während in der dritten Instanz das vierte bis neunte Teil relativ klein sind. Für beliebige $r,s\in\mathbb R$ mit $0\le r&amp;amp;lt;s\le 1/4$ gibt es natürliche Zahlen p, q, so dass $rL&amp;amp;lt;l_i\le sL$ für $i\in\{4,\dots,9\}$ zutrifft. Analoges gilt für E₁.

Zweiter Konstruktionssatz: In der Instanz $E=(m;L;{\mathbf l};{\mathbf b})$ mit $l_1&amp;amp;gt;\cdots&amp;amp;gt;l_{m-1}&amp;amp;gt;2l_m$ und $L/4\ge l_m$ ist ausdrücklich auch b_m = 0 erlaubt. Erhöht man b_m um 1, so nehme der optimale Zielfunktionswert z_D der ganzzahligen Aufgabe (2)–(4) zu. Dann gibt es natürliche Zahlen p, q mit $p\le q$, so dass die zusammengesetzte Instanzen $E\oplus E_0(p,q)$ und $E\oplus E_1(p,q)$ die Lücke 1 + Δ(E) aufweisen.^[8], vgl. auch ^[12]

Beispiel: Die Instanz $E:=(3;132;(44,33,12)^\top;(2,3,5)^\top)$ erfüllt die Voraussetzungen, denn in keiner Optimallösung des Problems (2)–(4) findet sich eine Zuschnittvariante mit mindestens zwölf Einheiten Verschnitt. Mit $E_0(73,668)\oplus E$ entsteht die Instanz $(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)$ mit Lücke 149 / 132.

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

$E_M:=(5;45;(27,23,15,11,9)^\top;(3,3,9,6,10)^\top)$

mit der Zusatzbedingung, dass die gemäß 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 E_M wird der Gesamtverschnitt von neun Längeneinheiten in 3 + 2 + 4 oder 3 + 1 + 1 + 4 aufgeteilt, und wegen 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 Δ > 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 6 / 5 aufgebaut werden; mit dem ersten wurden es $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 E₁ aus E₀ 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 $(9;L;{\mathbf l};{\mathbf e})$ mit z_D > 3 seien die Zuschnittvarianten ${\mathbf e}^1+2{\mathbf e}^4$, ${\mathbf e}^2+2{\mathbf e}^5$, ${\mathbf e}^3+2{\mathbf e}^6$, ${\mathbf e}^1+{\mathbf e}^8+{\mathbf e}^9$, ${\mathbf e}^2+{\mathbf e}^7+{\mathbf e}^9$ und ${\mathbf e}^3+{\mathbf e}^7+{\mathbf e}^8$ zulässig. Dann gilt $l_1\ne l_2$, $l_4\ne l_5$, $l_5\ne l_7$, $l_6\ne l_7$, $l_7\ne l_8$. Gilt außerdem l₄ = l₇, so folgt $l_5\ne l_8$, $l_6\ne l_9$, l₁ + l₅ + l₆ > L, 2l₁ > l₂ + l₃ und 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 $(m;L;{\mathbf l};{\mathbf b})$ mit $\Delta\ge 1$ immer noch verschieden verstanden werden:

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

Online-Optimierung

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

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

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

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

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

Um ein besseres asymptotisches Verhalten zu gewährleisten, braucht man folglich Heuristiken, die beliebig viele Varianten offen halten 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 $R_A^\infty&amp;amp;lt;8/5$ erzielt werden, jedoch existiert kein Online-Algorithmus mit $R_A^\infty&amp;amp;lt;1{,}540$. Bessere Verhältnisse können erzielt werden, wenn die zu packenden Teile relativ klein gegenüber 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 $z_A\le z_D*11/9+1$. Die absolute Güteeinschätzung ist hier 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 $\varepsilon&amp;amp;gt;0$ gibt es Approximationsalgorithmen mit $R_A^\infty&amp;amp;lt;1+\varepsilon$. Darüber hinaus existieren Approximationsalgorithmen mit polynomialer Komplexität und $R_A^\infty=1$. Allerdings wächst die absolute Differenz 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 $L_1,\dots,L_M$ und Preisen $p_1,\dots,p_M$ gegeben sind, sind anstelle des Spaltengenerierungsproblems (7) mehrere Rucksackprobleme zu lösen, nämlich mit Rucksackkapazität L_k für $k=1,\dots,M$. Eine Verbesserung des Zielfunktionswertes der stetigen Relaxation ist möglich, wenn ${\mathbf g}^\top{\mathbf a}&amp;amp;gt;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 kann umgekehrt gefragt werden, welche Vorräte verschieden langen Ausgangsmaterials gekauft werden müssen, um mehrere Zuschnittaufträge möglichst billig erledigen zu können. Dabei wird angenommen, dass längere Stücke Material stets teurer sind als kürzere und aus organisatorischen Gründen die Zuschnittaufträge nicht vermischt werden dürfen. Das heißt, aus einem Stück Material dürfen Teile immer nur für einen Auftrag geschnitten werden. Dieses Sortimentsproblem wird einschließlich numerischer Experimente in der Habilitationsschrift ^[21] behandelt.

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

Das Streifenpackproblem stellt eine weitere aus Planungsproblemen entstehende Verallgemeinerung des eindimensionalen Zuschnittproblems dar. Die Aufgabe besteht darin, in ein Rechteck der Abmessungen $L\times W$ mit fester Breite L und möglichst kleiner Höhe 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 k < m verschiedene Teilesorten in Bearbeitung sind, wobei die positive ganze Zahl k fest vorgegeben ist. Bevor also die (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 eine Vielzahl weiterer Pack- und Zuschnittprobleme, für die das eindimensionale Problem (2)–(4) auch als Relaxation dienen kann, wird unter anderem in ^[22] gegeben.

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 $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 $\Delta=z_D-z_C\ge 1$ geben müsse.^[23] 1986 veröffentlichte Frau Marcotte ein konkretes Beispiel.^[24] 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 $(3;30;(15,10,6)^\top;(1,2,4)^\top)$ angab ^[25], 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 Δ > 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.^[26] Inzwischen wurde das Verfahren weiterentwickelt zu Branch and price and cut.

Einige noch offene Fragen

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

• Bezeichnet P(m) die Menge aller Instanzen des eindimensionalen Zuschnittproblems mit höchstens m verschiedenen Teilelängen, fragen wir nach $g(m):=\sup\limits_{E\in P(m)}\{z_D(E)-z_C(E)\}$. Wie kann 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 k > 1 mit $L/k\ge l_i&amp;amp;gt;L/(k+2)$ für alle $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. ${\mathbf e}^\top{\mathbf b}=5$, kann man ausrechnen, dass von allen diesen Instanzen der Anteil der Instanzen mit Lücke $\Delta\ge 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 z_D − z_C aufweisen als die zugehörigen residualen Instanzen?
• Für welche minimalen L bei durchgängig ganzzahligen Daten kann $\Delta\ge 1$ werden? Sind für m = 3,4,5 kleinere 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. ↑ ^{a b c d e f} J. Rietz: Untersuchungen zu MIRUP für Vektorpackprobleme. Dissertation, TU Bergakademie Freiberg, 2003.
9. ↑ V. Nica: A general counterexample to the Integer Round-Up property. (Unveröffentlichtes) Manuskript, Abteilung für ökonomische Kybernetik, Ökonomische Akademie, Bukarest 1994.
10. ↑ ^{a b c} J. Rietz, G. Scheithauer, J. Terno: Families of non-IRUP instances of the one-dimensional cutting stock problem. Discrete Applied Mathematics 121 (2002) 229–245.
11. ↑ P. C. Gilmore, R. E. Gomory: A linear programming approach to the cutting-stock problem (Part I). Oper. Res. 9 (1961) 849–859.
12. ↑ ^{a b c d} J. Rietz, G. Scheithauer, J. Terno: Tighter bounds for the gap and non-IRUP constructions in the one-dimensional cutting stock problem. Optimization 51 (2002) 927–963.
13. ↑ A. A. Farley: A note on bounding a class of linear programming problems. Operations Research Vol. 38, Nr. 5, Sept./Okt. 1990, S. 922f.
14. ↑ C. Nitsche, G. Scheithauer, J. Terno: New cases of the cutting stock problem having MIRUP. Math. Meth. Oper. Res. 48 (1998) 105–115.
15. ↑ G. Scheithauer, J. Terno: The Modified Integer Round-Up Property of the One-Dimensional Cutting Stock Problem. European Journal of Operational Research 84 (1995) 562–571.
16. ↑ G. Scheithauer, J. Terno, A. Müller, G. Belov: Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm. Journal of the Operational Research Society 52 (2001) 1390–1401.
17. ↑ ^{a b} J. Rietz, S. Dempe: Large gaps in one-dimensional cutting stock problems. Discrete Applied Mathematics, Vol. 156, Issue 10 (Mai 2008), 1929–1935.
18. ↑ E. G. Coffman jr., M. R. Garey, D. S. Johnson: Approximation algorithms for bin packing: A survey. in: Approximation Algorithms for NP-Hard Problems, D. Hochbaum (ed.), PWS Publishing, Boston 1996, 46–93.
19. ↑ D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, R. L. Graham: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. Vol. 3, No. 4, December 1974, 299–325.
20. ↑ J. Terno, R. Lindemann, G. Scheithauer: Zuschnittprobleme und ihre praktische Lösung. VEB Fachbuchverlag, Leipzig 1987.
21. ↑ O. Holthaus: Kostenorientierte Zuschneideplanung. Entwurf und experimentelle Analyse von Lösungsverfahren für eindimensionale Zuschneide- und Sortimentsprobleme. Shaker Verlag, Aachen 2002. ISBN 3-8322-0087-8
22. ↑ H. Dyckhoff, G. Scheithauer, J. Terno: Cutting and Packing. in: Annotated Bibliographies in Combinatorial Optimization, herausgegeben von M. Dell'Amico, F. Maffioli und S. Martello, John Wiley & Sons Ltd., 1997, S. 393–412.
23. ↑ O. Marcotte: The cutting stock problem and integer rounding. Mathematical Programming 33 (1985) 82–92.
24. ↑ 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.
25. ↑ M. Fieldhouse. The duality gap in trim problems. SICUP-Bulletin No. 5, 1990.
26. ↑ 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.