Eindimensionales Zuschnittproblem

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

Problemstellung und grundlegende Definitionen

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} }\leq L

(1)

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

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

Eine zulässige Zuschnittvariante $\mathbf {a}$ heißt eigentlich, wenn ${\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 ${\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 ${\mathcal {N}}P$ -vollständig. Gemäß ist das eindimensionale Bin-Pack-Problem sogar stark ${\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 $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:

{\displaystyle \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:

{\displaystyle \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

x_{j}=0

, falls

{\mathbf {a} }^{j}\not \leq \mathbf {b}

(6)

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

{\displaystyle \Delta

.

Es stellt sich heraus, dass es ${\mathcal {N}}P$ schwer ist, $\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 $\mathbf {a}$ höchstens $\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

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 $\Delta =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 $\Delta =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}}:=\left({\bar {m}};{\bar {L}};{\bar {\mathbf {l} }};{\bar {\mathbf {b} }}\right)$ 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 >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} }<\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:=\left(2;9;(5,3)^{\top };{\mathbf {b} }\right)$ , ${\bar {E}}:=\left(2;10;(5,3)^{\top };{\mathbf {b} }\right)$ zeigt.

Beispiel zur Äquivalenz: Thomas Gau fand bei Testrechnungen die Instanz $\left(5;10\,000;(5000,3750,3250,3001,2000)^{\top };(1,1,1,1,2)^{\top }\right)$ mit Lücke $16/15$ . 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 $\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 $3/4$ und geeignetes Runden, nämlich $\left(5;60;(30,22,20,19,12)^{\top };(1,1,1,1,2)^{\top }\right)$ .

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

$l_{i}\geq l_{i+1}$ für $i\in I\setminus \{m\}$ aufgrund der Sortierung
$L-{\mathbf {a} }^{\top }{\mathbf {l} }\geq 0$ für jede maximale Variante $\mathbf {a}$
${\mathbf {u} }^{\top }{\mathbf {l} }-L\geq 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: Gesucht werden alle zur Instanz $\left(4;210;(105,70,42,30)^{\top };{\mathbf {b} }\right)$ äquivalenten Instanzen mit durchgängig ganzzahligen Längen, wobei $b_{i}>0$ für alle $i\in I$ gilt. Offensichtlich ist $\max \left\{2l_{1},3l_{2},5l_{3},7l_{4}\right\}\leq L$ zu fordern. Neben den Unzulässigkeitsbedingungen $l_{1}+l_{2}+l_{3}>L$ und $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 $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}&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 $u_{1}$ nicht beliebig unabhängig von den anderen erhöht werden. Tauscht man $u_{1}$ gegen $z_{1}$ , geht die Ganzzahligkeit von $l_{1}$ 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}\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 $l_{1}=l_{2}=l_{3}=5$ und $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 $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\leq 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 $\Delta =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 $\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 $z_{D}\leq \lceil z_{C}\rceil +1$ gilt. Die Vermutung, jede Instanz des eindimensionalen Zuschnittproblems (2)–(4) besitze MIRUP, konnte bisher (Stand 2007) nur in Spezialfällen nachgewiesen werden, zum Beispiel für den Teilbarkeitsfall. Ein einfacherer Beweis von Guntram Scheithauer und Johannes Terno wurde in der Dissertation von Jürgen Rietz noch verschärft. Es gilt folgender

Satz: Für jede Instanz $E$ des Teilbarkeitsfalls gilt $\Delta (E)=z_{D}(E)-z_{C}(E)<7/5$ . Sind sämtliche Teile größer als $1/19$ des Ausgangsmaterials, gilt sogar $\Delta (E)<5/4$ .

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

Seien $k_{1},k_{2},\dots ,k_{m-1}$ paarweise teilerfremde ganze Zahlen mit $1<k_{1}<\cdots <k_{m-1},m\geq 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}:=\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 $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}}}*\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$ .
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 $\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 $\Delta >1$ .
Sei $p\in {\mathbb {N} }\setminus \{0\}$ beliebig und $L:=(6p+2)*(6p+3)*(6p+5)$ . Dann gilt $\Delta >1$ für die Instanz $\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)$ .

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.

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} }<0$ existiert. Für diese Spaltengenerierung ist somit jeweils ein Rucksackproblem

{\displaystyle {\mathbf {g} }^{\top }{\mathbf {a} }\to \max

bei

{\mathbf {l} }^{\top }{\mathbf {a} }\leq 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. 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 $\mathbf {a}$ abgespeichert wurde, für die ${\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 $2:2:1$ . Die Materialausnutzung ist zu maximieren. Das bedeutet, hier ist eine Optimallösung der stetigen Relaxation (5) von der Instanz $\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 ${\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}&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}}$

 ${\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_{1}$ (und nicht $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 $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 $\Delta$ hilft folgendes

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

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

.

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}\left(E^{(r)}\right)\leq m$ und somit

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

.

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

Stets gilt $\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 $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:=\left(4;924;(308,231,132,84)^{\top };(2,3,7,6)^{\top }\right)$ hat eine eindeutige Optimallösung der Relaxation (5), nämlich $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 $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-{\frac {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}\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 $\Delta =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:

Löse die Relaxation (6) und trenne den ganzzahligen Anteil ab.
Es verbleibe eine residuale Instanz $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 $\mathbf {a}$ .
Bei ${\mathbf {a} }\not \leq {\mathbf {b} }^{(r)}$ streiche überzählige Teile aus $\mathbf {a}$ .
Ergänze, wenn möglich, weitere noch zuzuschneidende Teile in $\mathbf {a}$ .
Falls $\mathbf {a}$ der Nullvektor ist, ist nichts mehr zu schneiden, halt.
Solange es möglich ist, ersetze in $\mathbf {a}$ jeweils ein Teil durch ein größeres noch zu schneidendes.
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, die auf der Dualitätstheorie der linearen Optimierung beruht.

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

{\displaystyle {\mathbf {b} }^{\top }{\mathbf {u} }\to \max

bei

{\mathbf {a} }^{\top }{\mathbf {u} }\leq 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} }}\leq 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}\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 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:=\left(3;11;(6,4,1)^{\top };(2,2,1)^{\top }\right)$ wurden oben die berechneten Simplexschemata angegeben. Vor dem ersten Austausch galten $z={\frac {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}={\frac {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 ${\frac {5}{3}}<{\frac {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 Austauschzyklen, 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)<l_{i}\leq 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 $\Delta =z_{D}-z_{C}$ . Umfangreiche Untersuchungen enthält die Dissertation von Jürgen Rietz, während die diesbezüglichen Beiträge von Rietz et al. Vorläufer darstellen.

Unter einer $p$ -Teile-Variante verstehen wir eine beliebige zulässige Zuschnittvariante $\mathbf {a}$ , mit der genau $p$ Teile zugeschnitten werden ( $p\leq k+1$ ), d. h. ${\mathbf {e} }^{\top }{\mathbf {a} }=p$ , wobei ${\mathbf {e} }\in {\mathbb {R} }^{m}$ für den aus lauter Einsen bestehenden Einsvektor 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\geq 2$ ändert sich die Situation jedoch grundlegend. Ist $t\geq \max \left\{3k^{3}-k^{2}-3k;3k^{2}+3k+1\right\}$ , ergibt sich $z_{M}=z_{C}=3$ und $z_{D}=4$ für die Instanz

\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 ${\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$ : $\left(5;75;(29,28,25,23,19)^{\top };(1,1,2,1,1)^{\top }\right)$
$k=3$ : $\left(5;94;(29,28,25,23,19)^{\top };(1,1,2,1,3)^{\top }\right)$
$k\geq 4$ : $\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 $z_{M}=z_{C}=2<z_{D}$ . Dagegen gilt $z_{M}=z_{C}=2$ und $z_{D}=3$ für die Instanzen

$\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 $3\leq k\leq 7$
$\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 $k\geq 8$ .

Komplementäre Instanzen

Zuerst betrachten wir (2,3)-Instanzen $(m;L;{\mathbf {l} };{\mathbf {b} })$ mit ${\frac {5}{12}}L>\ell _{1}\geq \cdots \geq l_{m}>{\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':=\left(m;L;{\mathbf {l} }';{\mathbf {b} }\right)$ mit ${\frac {L}{4}}<l_{1}'\leq \cdots \leq l_{m}'<{\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}\geq \cdots \geq 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):=\left(m;L+(k+1)*t;{\mathbf {l} }+t{\mathbf {e} };{\mathbf {e} }\right)

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>\max \left\{L-(k+2)*l_{m},\;k*l_{1}-L\right\}

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

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 $E'(t)$ nicht notwendig $(k,k+1)$ -Instanz zu sein. Hat die Instanz $E$ eine Lücke $\Delta \geq 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):=\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 $t>-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>\max\{51-4*13,\;2*23-51\}=-1$ ist $E(t)$ eine (2,3)-Instanz. Die zugehörige komplementäre Instanz lautet $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 $t>-11,t\neq -10$ ebenfalls die Lücke 1. Für $t>\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 $\Delta >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_{1}:=(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

\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 $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 {{\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 $p\geq 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:

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

$\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)$ , $z_{C}=6-1/96$
$\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)$ , $z_{C}=7-5/384$
$\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)$ , $z_{C}=8-7/512$
$\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)$ , $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 $\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 $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}\geq y_{C}$ . Gilt $q:=k*\lceil y_{C}\rceil <m$ , können die $q$ größten Teile in $k$ -Teile-Varianten zugeschnitten werden, und nach deren Abtrennung verbleibt eine Instanz $E'=\left(m';L;{\mathbf {l} }';{\mathbf {b} }'\right)$ mit $\Delta (E)\geq \Delta \left(E'\right)>\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}\left(E'\right)\in \mathbb {N}$ , $z_{C}\left(E'\right)<z_{C}(E)$ und $\Delta (E)-1<\Delta \left(E'\right)<\Delta (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}\leq 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}:=\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 $z_{C}\approx 37{,}2217$ und $y_{C}\approx 1{,}6650$ , also $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 $E_{2}$ gilt $y_{C}\left(E_{2}\right)=0$ und $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 $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}\geq \cdots \geq 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}\geq z_{C}-g$ . Gilt $y_{k+1}\geq 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 $\Delta$ 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}:=\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 $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}:=\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 $z_{C}\left(E_{4}\right)=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, $\Delta \left(E_{4}\right)=0$ und $z_{D}\left(E_{1}\right)=38$ .

A-priori-Zulässigkeit von Varianten

Seien $k,p_{1},\dots ,p_{k+1},q\in \mathbb {N} \setminus \{0\}$ , $k\geq 2$ , $q\leq k$ und $p_{1}\leq \cdots \leq p_{k+1}\leq m$ . In der $(k,k+1)$ -Instanz $E=(m;L;{\mathbf {l} };{\mathbf {e} })$ mit $l_{1}\geq \cdots \geq 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}\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}}$
$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 $m=(k+1)*z_{C}$ gilt auch $y_{1}\geq 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_{1}=g-z_{C}+y_{3}$ .

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 $\left(p_{1},p_{2},p_{3}\right)$ geschrieben, wenn eine der folgenden Bedingungen zutrifft:

(a)

p_{1}\leq p_{2}\leq g<p_{3}\land (p_{1}+p_{2}+2p_{3}>2g+6z_{C}-2y_{1}

oder

p_{1}+p_{2}+2p_{3}\geq 8z_{C}+1)

(b)

p_{1}\leq g<p_{2}\leq p_{3}\land (p_{1}+2p_{3}>g+6z_{C}-2y_{1}

oder

p_{1}+2p_{3}\geq 8z_{C}-g+1)

(c)

p_{1}\leq g<p_{2}\leq p_{3}\land 2p_{1}+p_{2}+p_{3}>6z_{C}+4y_{1}

(erfordert Fallunterscheidung bezüglich

y_{1}

)

(d)

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 $p_{2}\leq g$ auch (a)-Variante ist und die (a)-Varianten die (b)-Varianten dominieren. Bedingung (a) ist aber bei $p_{2}>g$ nicht anwendbar. (a)-Varianten sind bei $g=2z_{C}$ am günstigsten, (c)-Varianten bei $g=z_{C}$ , weil $y_{1}<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\leq 16\leq 17<26\land 5+16+2*26=73\geq 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\geq 8*9+1$ . Wegen $18>g$ durfte (a) nicht benutzt werden. Bei $g=9$ findet man wegen $9+9+2*27=72\leq 8*9$ keine (a)- und (b)-Varianten. Eine (d)-Variante ist (9,10,27), denn $2*9+10+3*27=109\geq 12*9+1$ . Wegen $y_{3}<1$ (gemäß Reduktionen) und $y_{1}=g-z_{C}+y_{3}$ ist $y_{1}<1$ und daher (9,19,21) eine (c)-Variante, denn $2*9+19+21=58>6*9+4y_{1}$ und $9\leq g<19\leq 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_{1}=2$ und $y_{2}=y_{3}=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}\geq \cdots \geq 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 \leq {\frac {t-1}{k*(k+1)}}+1$
$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 $s=\sum \limits _{i=1}^{k}{\frac {1}{i}}$
$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 $t\leq 3*\left\lceil {\frac {z_{C}-1}{4}}\right\rceil$ bei $k=2$ .

Daraus folgt für (2,3)-Instanzen mit $z_{C}\leq 9$ sofort MIRUP, also $\Delta <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}\geq 11$ nicht mehr bewiesen werden.

Aussagen zum allgemeinen Fall

Inwieweit die Lücke $\Delta =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 $\Delta$ durch eine Konstante beschränkt ist oder linear mit $m$ wachsen kann oder etwa eine Abschätzung der Art $\Delta <1+C*\ln m$ mit einer Konstante $C>0$ für alle Instanzen des eindimensionalen Zuschnittproblems zutrifft.

Aus der Betrachtung residualer Instanzen folgt die fast triviale Aussage

\Delta <\max\{1,\,m-1\}

.

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

\Delta <\max \left\{2,{\frac {z_{M}+2}{3}}\right\}

und

\Delta <\max \left\{2,\,{\frac {m+2}{4}}\right\}

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

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

$z_{M}\leq 4{,}75\lor 5<z_{M}\leq 5{,}5\lor 6<z_{M}\leq 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 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}>\cdots >l_{m}$ sowie $2l_{1}>L$ und $l_{1}+2l_{m}>L$ vorausgesetzt. Gilt $l_{1}+l_{m}>L$ , so sei ${\mathbf {a} }:={\mathbf {e} }^{1}$ , andernfalls $t:=\min \left\{i\in I:l_{1}+l_{i}\leq L\right\}$ 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 $\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 $E_{1}:=\left(4;18;(10,9,6,4)^{\top };(1,1,2,1)^{\top }\right)$ und $E_{2}:=\left(2;6;(3,2)^{\top };(1,4)^{\top }\right)$ mit $\Delta \left(E_{1}\right)=1$ und $\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 $\Delta =z_{D}-z_{C}$ .

Die größte bisher (Stand 2007) erreichte Lücke beträgt $6/5$ .

Eine Instanz mit $z_{C}=z_{M}=12{,}8$ und $z_{D}=14$ ist diese: ${\big (}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}{\big )}$

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

Sollte $\Delta$ 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 $\Delta$ 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 $\Delta$ gefunden werden:

{\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 $E=(m;L;{\mathbf {l} };{\mathbf {b} })$ mit rationalen Längen $L>l_{1}>\cdots >l_{m}>0$ weise die Lücke $\Delta (E)\geq 1$ auf. Sei $p\in {\mathbb {N} },p\geq 2$ . Ferner sei $q\geq 2/l_{m}$ so gewählt, dass für jeden Vektor ${\mathbf {u} }\in {\mathbb {Z} }_{+}^{m}$ mit ${\mathbf {u} }^{\top }{\mathbf {l} }>L$ und ${\mathbf {u} }\leq {\mathbf {b} }$ auch $q*({\mathbf {u} }^{\top }{\mathbf {l} }-L)>1$ gilt. Dann besitzt die Instanz $\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 $1+\left(\left\lceil z_{C}(E)\right\rceil -z_{C}(E)\right)/p\geq 1$ .

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 $\left(3;30;(15,10,6)^{\top };(1,2,4)^{\top }\right)$ , $\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 $31/30$ , $16/15$ bzw. $11/10$ aufweisen, ergibt die Instanzen $\left(6;122;(62,61,50,30,20,12)^{\top };(2,1,1,1,2,4)^{\top }\right)$ , $\left(8;242;(122,121,98,60,44,40,38,12)^{\top };(2,1,1,1,1,1,1,2)^{\top }\right)$ und $\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 $38/35$ , $10/9$ und $39/35$ .

Vor weiteren Konstruktionen für Instanzen mit großer Lücke $\Delta$ erklären wir zusammengesetzte Instanzen. Für zwei Instanzen $E_{1}=\left(m_{1};L_{1};{\mathbf {l} }^{1};{\mathbf {b} }^{1}\right)$ und $E_{2}=\left(m_{2};L_{2};{\mathbf {l} }^{2};{\mathbf {b} }^{2}\right)$ gelte zunächst $L_{1}=L_{2}$ . In diesem Fall bedeutet die zusammengesetzte Instanz $E:=E_{1}\oplus E_{2}$ den Auftrag, alle Teile aus $E_{1}$ und $E_{2}$ in den jeweils geforderten Stückzahlen aus dem einheitlichen Material der Länge $L:=L_{1}=L_{2}$ zuzuschneiden. In der Situation $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: $\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 $\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 $\Delta =1$ sind die folgenden:

$\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)$
$\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\}$
$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$
$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 $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\leq r<s\leq 1/4$ gibt es natürliche Zahlen $p$ , $q$ , so dass $rL<l_{i}\leq sL$ für $i\in \{4,\dots ,9\}$ zutrifft. Analoges gilt für $E_{1}$ .

Zweiter Konstruktionssatz: In der Instanz $E=(m;L;{\mathbf {l} };{\mathbf {b} })$ mit $l_{1}>\cdots >l_{m-1}>2l_{m}$ und $L/4\geq 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\leq q$ , so dass die zusammengesetzten Instanzen $E\oplus E_{0}(p,q)$ und $E\oplus E_{1}(p,q)$ die Lücke $1+\Delta (E)$ aufweisen (vgl. auch Rietz et al.).

Beispiel: Die Instanz $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 $E_{0}(73,668)\oplus E$ entsteht die Instanz $\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 $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 \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 $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}:=\left(5;45;(27,23,15,11,9)^{\top };(3,3,9,6,10)^{\top }\right)

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 $\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 $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_{1}$ aus $E_{0}$ im Wesentlichen dadurch, dass gleiche Teilelängen erzwungen wurden. Dies stößt jedoch auf Hindernisse, wie folgendes Lemma aus 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}\neq l_{2}$ , $l_{4}\neq l_{5}$ , $l_{5}\neq l_{7}$ , $l_{6}\neq l_{7}$ , $l_{7}\neq l_{8}$ . Gilt außerdem $l_{4}=l_{7}$ , so folgt $l_{5}\neq l_{8}$ , $l_{6}\neq l_{9}$ , $l_{1}+l_{5}+l_{6}>L$ , $2l_{1}>l_{2}+l_{3}$ 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 \geq 1$ immer noch verschieden verstanden werden:

minimale Anzahl $m$ verschiedener Teilelängen: $\left(3;30;(15,10,6)^{\top };(1,2,4)^{\top }\right)$ mit $\Delta =31/30$ ist so eine Instanz. Wegen $\Delta <\max\{1,\,m-1\}$ musste $m>2$ sein.
minimale Länge $L$ des Ausgangsmaterials: Bisher (Stand 2007) ist hier nur $\left(5;16;(10,8,7,3,2)^{\top };(1,1,1,1,2)^{\top }\right)$ mit $z_{C}=2$ bekannt; bei der Zusatzforderung $m\leq 4$ wäre zum Beispiel $\left(4;18;(9,7,6,4)^{\top };(1,1,2,2)^{\top }\right)$ 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\geq 18$ wird. Entsprechende Instanzen sind $\left(4;18;(10,9,6,4)^{\top };(1,1,2,1)^{\top }\right)$ und $\left(5;18;(12,9,7,4,3)^{\top };{\mathbf {e} }\right)$ , 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. 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}\left\{z_{A}(E)/z_{D}(E)\right\}$ . 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 >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 mit $z_{D}(E)\leq 10N+1,N\in \mathbb {N}$ (beliebig) und $z_{FF}(E)=z_{BF}(E)=17N$ . Da gleichzeitig gemäß jenem Artikel $z_{FF}(E)\leq z_{D}*17/10+2$ und $z_{BF}(E)\leq 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 }\geq 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 }>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 $R_{A}^{\infty }<8/5$ erzielt werden, jedoch existiert kein Online-Algorithmus mit $R_{A}^{\infty }<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}\leq 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 >0$ gibt es Approximationsalgorithmen mit $R_{A}^{\infty }<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} }>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.

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 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 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 $c$ die Kosten für ein Stück Rohmaterial sowie $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 gilt seit den 1960er Jahren als ungelöst. Die Artikel befassen sich mit dem Problem, indem sie die nicht stetige Funktion (8) durch stetige Funktionen approximieren und 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 $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}\geq 1$ geben müsse. 1986 veröffentlichte Frau Marcotte ein konkretes Beispiel. 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 $\left(3;30;(15,10,6)^{\top };(1,2,4)^{\top }\right)$ angab, 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 $\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. 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)}\left\{z_{D}(E)-z_{C}(E)\right\}$ . 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\geq l_{i}>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 \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 $z_{D}-z_{C}$ aufweisen als die zugehörigen residualen Instanzen?
Für welche minimalen $L$ bei durchgängig ganzzahligen Daten kann $\Delta \geq 1$ werden? Sind für $m=3,4,5$ kleinere $L$ als 30, 18 und 16 möglich?

Quellenangaben

↑ G. Scheithauer: Zuschnitt- und Packungsoptimierung – Problemstellungen, Modellierungstechniken, Lösungsmethoden. Vieweg + Teubner 2008, S. 59f. ISBN 978-3-8351-0215-6
↑ 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.
↑ G. Wäscher, T. Gau: Heuristics for the Integer One-dimensional Cutting Stock Problem: a computational study. OR Spektrum 18 (1996) 131–144.
↑ 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.
↑ 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.
↑ O. Marcotte: Topics in combinatorial packing and covering. Forschungsbericht 568, School of Oper. Res. and Ind. Eng., Cornell University (Ithaca, NY) 1982.
↑ 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.
1 2 3 4 5 6 Jürgen Rietz: Untersuchungen zu MIRUP für Vektorpackprobleme. Technische Universität Bergakademie Freiberg, Freiberg (Sachsen) 2003, DNB 970170505 (Dissertation).
↑ V. Nica: A general counterexample to the Integer Round-Up property. (Unveröffentlichtes) Manuskript, Abteilung für ökonomische Kybernetik, Ökonomische Akademie, Bukarest 1994.
1 2 3 Jürgen Rietz, Guntram Scheithauer, Johannes Terno: Families of non-IRUP instances of the one-dimensional cutting stock problem. In: Discrete Applied Mathematics. Band 121, September 2002, S. 229–245, doi:10.1016/S0166-218X(01)00361-4 (englisch, Download [PDF; 165 kB; abgerufen am 14. April 2023]).
↑ P. C. Gilmore, R. E. Gomory: A linear programming approach to the cutting-stock problem (Part I). Oper. Res. 9 (1961) 849–859.
1 2 3 4 Jürgen Rietz, Guntram Scheithauer, Johannes Terno: Tighter bounds for the gap and non-IRUP constructions in the one-dimensional cutting stock problem. In: Optimization. Band 51, Nr. 6, 2002, S. 927–963, doi:10.1080/0233193021000066545.
↑ A. A. Farley: A note on bounding a class of linear programming problems. Operations Research Vol. 38, Nr. 5, Sept./Okt. 1990, S. 922f.
↑ C. Nitsche, G. Scheithauer, J. Terno: New cases of the cutting stock problem having MIRUP. Math. Meth. Oper. Res. 48 (1998) 105–115.
↑ 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.
↑ 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.
1 2 J. Rietz, S. Dempe: Large gaps in one-dimensional cutting stock problems. Discrete Applied Mathematics, Vol. 156, Issue 10 (Mai 2008), 1929–1935.
↑ 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.
↑ 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.
↑ J. Terno, R. Lindemann, G. Scheithauer: Zuschnittprobleme und ihre praktische Lösung. VEB Fachbuchverlag, Leipzig 1987.
↑ 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
↑ 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.
↑ 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.
↑ 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.
↑ O. Marcotte: The cutting stock problem and integer rounding. Mathematical Programming 33 (1985) 82–92.
↑ 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.
↑ M. Fieldhouse. The duality gap in trim problems. SICUP-Bulletin No. 5, 1990.
↑ 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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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

[Rie03-8] 1 2 3 4 5 6 Jürgen Rietz: Untersuchungen zu MIRUP für Vektorpackprobleme. Technische Universität Bergakademie Freiberg, Freiberg (Sachsen) 2003, DNB 970170505 (Dissertation).

[9] V. Nica: A general counterexample to the Integer Round-Up property. (Unveröffentlichtes) Manuskript, Abteilung für ökonomische Kybernetik, Ökonomische Akademie, Bukarest 1994.

[RST02a-10] 1 2 3 Jürgen Rietz, Guntram Scheithauer, Johannes Terno: Families of non-IRUP instances of the one-dimensional cutting stock problem. In: Discrete Applied Mathematics. Band 121, September 2002, S. 229–245, doi:10.1016/S0166-218X(01)00361-4 (englisch, Download [PDF; 165 kB; abgerufen am 14. April 2023]).

[11] P. C. Gilmore, R. E. Gomory: A linear programming approach to the cutting-stock problem (Part I). Oper. Res. 9 (1961) 849–859.

[RST02b-12] 1 2 3 4 Jürgen Rietz, Guntram Scheithauer, Johannes Terno: Tighter bounds for the gap and non-IRUP constructions in the one-dimensional cutting stock problem. In: Optimization. Band 51, Nr. 6, 2002, S. 927–963, doi:10.1080/0233193021000066545.

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

[RD08-17] 1 2 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.

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

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