[Back]

F. Leberl:
"Column Generation at Strip Level for the K-Staged Two-Dimensional Cutting Stock Problem";
Supervisor: G. Raidl; Institut für Computergraphik und Algorithmen, 2016; final examination: 2016-03-22.

Several industrial applications exist for packing non overlapping objects, called elements,
into larger objects, called bins, such that the total number of used bins is minimal.
Examples are wood, metal and glass industries, where the customers´ orders must be cut
from larger pieces of stock material. Particularly when high volumes of stock material are
used, even small improvements can directly increase profitability. Assuming both elements
and bins are rectangular, the problem is called the 2-dimensional bin packing problem
(2BP) or cutting stock problem (2CS), both of which are NP-hard. Only guillotine cuts
are allowed, which are orthogonal cuts from one side to another. This leads to a further
specification of the 2CS, which is the number of stages it allows, denoted by K. A stage
is a series of parallel cuts. The aim of this thesis is to present an efficient implementation
of a new strip-based column generation approach for the 2-staged and 3-staged 2CS with
guillotine cuts.
First, the problem and column generation are introduced and formally defined. This is
followed by a study of relevant literature concerning the 2CS and 2BP. Literature for the
knapsack problem is also studied, as this is a relevant subproblem of column generation.
This includes variants of dynamic programming both for the unbounded and bounded
knapsack problem (UKP and BKP). After that, the Stage Shifted Column Generation
(SSCG) is presented. This entails both definitions for the master problem and the
relevant pricing problems for K = 2 and K = 3. The master problem is formulated as
a set covering problem, while the pricing problems are variants of knapsack problems.
EDUK is an efficient implementation for the UKP, while a new algorithm is developed
for the BKP, called BKP-Generator. It essentially processes the entire knapsack element
by element. For K = 3, BKP-Generator is adapted, and called DP-Generator. Two
heuristic algorithms are also presented, which rely on randomizing DP-Generator. Finally,
an integrality heuristic is introduced, as the master problem offers possibly fractional
results. The different pricing problems are experimentally tested and compared to an
insertion heuristic and a dynamic programming implementation. The results show good
LP relaxed solutions, and integral results are competitive with previous implementations.

Viele industrielle Anwendungen existieren für das Packen von kleineren Objekten in
größere Behälter, so-genannte Bins, sodass die Anzahl der verwendeten Bins minimal ist.
Beispiele sind die Holz, Metall oder Glass Industrien, in der die Kundenbestellungen aus
größeren Stücken Lagermaterial zugeschnitten werden müssen.Wenn sowohl Bins, als auch
die kleineren Objekte, so-genannte Elements, rechteckig sind, ist vom 2-dimensionalem
Bin Packing Problem (2BP) bzw. dem 2-dimensionalem Cutting Stock Problem (2CS)
die Rede. In dieser Diplomarbeit werden weiters nur so-genannte Guillotinenschnitte
erlaubt, was orthogonale Schnitte von einer Seite des Bins zur anderen sind. Diese Schnitte
haben zur Folge, dass man das 2CS weiters über ihre Anzahl an Stages definieren kann,
die mit K bezeichnet wird. Ein Stage ist hier eine Reihe paralleler Schnitte. Das Ziel
dieser Diplomarbeit ist es, eine neue Variante von Column Generation für das 2-staged
und 3-staged 2CS zu präsentieren, die auf der Generation von so-genannten Strips
basiert.
Zuerst wird das Problem formal definiert, und das Prinzip der Column Generation genauer
erläutert. Darauf folgt eine Untersuchung der Litertur über das 2CS. Literatur zu dem
Knapsack Problem wird auch vorgestellt, da es sich dabei um ein relevantes Subproblem
der Column Generation handelt. Dies beinhaltet Varianten für das Unbounded als
auch für das Bounded Knapsack Problem (UKP und BKP). Danach wird das Stage
Shifted Column Generation (SSCG) präsentiert. Dazu gehören Definitionen für das
Master Problem als auch für die relevanten Pricing Probleme für den Fall K = 2
und K = 3. Das Master Problem wird als ILP formuliert, genauer einem Set Covering
Problem, während die Pricing Probleme Varianten eines Knapsack Problems darstellen.
Für das UKP wird der effiziente algorithmus EDUK implementiert, während für das
BKP ein neuer Algorithmus vorgestellt wird, der den gesamten Knapsack immer Element
für Element bearbeitet, und BKP-Generator heißt. Für K = 3 wird BKP-Generator
adaptiert, und DP-Generator genannt. Zwei Heuristiken, die auf der Randomisierung von
DP-Generator beruhen, werden ebenfalls vorgestellt. Es wird außerdem eine Integrality
Heuristic vorgestellt, da die Ergebnisse des Master Problems meist nicht integral sind.
Die verschiedenen Pricing Probleme werden experimentell miteinander, und mit einer
Insertion Heuristic als auch einer Dynamic Programming Implementation verglichen.
Die Resultate zeigen gute Lösungen für die LP Relaxierung, und auch die integralen
Lösungen können teils besser als die vorherigen Implementationen sein.

http://publik.tuwien.ac.at/files/publik_254591.pdf