Combining metaheuristics and integer programming for solving cutting and packing problems

Abstract

Thema der vorliegenden Dissertation ist die Kombination von Metaheuristiken und Algorithmen aus der ganzzahligen Programmierung (Integer Programming IP) zum Lösen von zwei verschiedenen NP-schweren Pack- und Verschnittproblemen: Das aus der Glaserzeugung kommende zweidimensionale Bin Packing Problem (2BP) und das mehrdimensionale Rucksackproblem (Multidimensional Knapsack Problem MKP), welches erstmals im Zusammenhang mit Investitionsplanung in der Literatur Erwähnung fand.<br />Zu Beginn werden Metaheuristiken, im Besonderen evolutionäre Algorithmen und variable Nachbarschaftssuche sowie ganzzahlige Programmierung eingeführt.<br />Metaheuristiken und IP können als komplementär angesehen werden, wenn man die Vor- und Nachteile beider Methoden betrachtet. Daher scheint es umso natürlicher zu sein diese verschiedenen Ansätze zu leistungsfähigeren Lösungstrategien zu vereinen. In der vorliegenden Arbeit werden wir verschiedene moderne Ansätze zur Kombination von exakten Verfahren und Metaheuristiken überblicksmäßig besprechen. Eine Klassifikation der behandelten Ansätze in integrative und kollaborative Kombinationen der oben genannten Verfahren wird vorgestellt. Die Ergebnisse der besprochenen Verfahren sind in den meisten Fällen sehr vielversprechend.<br />Wir wenden uns dann dem 2BP zu. Es werden neue IP-Formulierungen vorgestellt:<br />Ein Modell für eine eingeschränkte Version und eines für das ursprüngliche Problem. Beide Modelle benötigen nur eine polynomielle Anzahl von Variablen und Nebenbedingungen und können Symmetrien vermeiden. Diese Modelle werden mit dem allgemeinen IP-Löser CPLEX gelöst. Außerdem entwickeln wir einen Branch-and-Price (B\&P) Algorithmus der auf eine set-covering Formulierung des Problems angewandt wird. Die Spaltengenerierung wird mittels dual-optimalen Ungleichungen stabilisiert. Die Erzeugung der Spalten wird mittels einer aus vier Methoden bestehenden hierarchischen Strategie gelöst: (a) einer schnellen Heuristik, (b) eines evolutionären Algorithmus, (c) des Lösens einer eingeschränkten Version des Pricing-Problems mittels CPLEX und schließlich (d) des Lösens des gesamten Pricing-Problems mittel CPLEX. Die durchgeführten Experimente dokumentieren die Vorteile unseres Ansatzes: Die eingeschränkte Version ermöglicht es rasch hochqualitative Lösungen zu berechnen. Das Lösen des Modells der uneingeschränkten Version benötigt wesentlich mehr Rechenaufwand. Mithilfe der Spaltengenerierung können aber in akzeptabler Zeit sehr gute untere Schranken erreicht werden. Das vorgestellte B\&P-Verfahren mit Stabilisierung und der vierstufigen hierarchischen Pricing-Strategie erzielt die besten Ergebnisse in Hinblick auf die benötigten Laufzeiten, die Lösungsgüte und die Anzahl der optimal gelösten Instanzen in limitierter Laufzeit.<br />Weiters betrachten wir das MKP, dessen Struktur wir theoretisch und empirisch analysieren. Wir stellen auch verschiedene IP-basierte und metaheuristische Verfahren sowie Kombinationen dieser Verfahren vor. Zuerst analysieren wir die Distanzen zwischen optimalen ganzzahligen Lösungen und optimalen Lösungen der LP-Relaxierung des MKP. Dazu benutzen wir die kleineren der üblicherweise verwendeten Benchmark-Instanzen. Danach führen wir das Core-Konzept für das MKP ein und unterziehen es einer ausgiebigen theoretischen und empirischen Analyse.<br />Daraus werden neue, erfolgreiche Ansätze zum Lösen des MKP entwickelt. Wir stellen dann die neue relaxierungsgesteuerte variable Nachbarschaftssuche (Relaxation Guided Variable Neighborhood Search) für allgemeine kombinatorische Optimierungsprobleme und ihre Implemetierung für das MKP vor.<br />Schließlich werden verschiedene kollaborative Kombinationen der vorgestellten Verfahren diskutiert und evaluiert. Die durchgeführten Experimente zeigen, dass unsere Verfahren die besten bisher bekannten Lösungen berechnen können, wobei die Laufzeiten deutlich unter jenen der besten aus der Literatur bekannten Ansätze liegen.<br />Zusammenfassend lässt sich feststellen, dass die Kombination der Vorteile von IP-basierten Verfahren und Metaheuristiken uns ermöglichen, bessere Problemlösungsstrategien für spezielle kombinatorische Optimierungsprobleme zu entwickeln. Ausserdem sind die Erfolge unserer Ansätze ein weiterer Anhaltspunkt dafür, dass derartige Kombinationen einen vielversprechenden Forschungszweig darstellen.<br />

The main topic of this thesis is the combination of metaheuristics and integer programming based algorithms for solving two different cutting and packing problems, belonging to the class of NP-hard combinatorial optimization problems: A problem originating from the glass cutting industry, three-stage two-dimensional bin packing (2BP), and a problem first mentioned in the context of capital budgeting, the multidimensional knapsack problem (MKP).<br />We begin by introducing metaheuristics, in particular evolutionary algorithms and variable neighborhood search, and integer programming (IP) based methods.<br />IP and metaheuristic approaches each have their particular advantages and disadvantages. In fact, looking at the assets and drawbacks, the approaches can be seen as complementary. It therefore appears to be natural to combine techniques of these two distinct streams into more powerful problem solving strategies. We discuss different state-of-the-art approaches of combining exact algorithms and metaheuristics to solve combinatorial optimization problems. Some of these hybrids mainly aim at providing optimal solutions in shorter time, while others focus primarily on obtaining better heuristic solutions. The two main categories into which we divide the approaches are collaborative versus integrative combinations. We further classify the different techniques in a hierarchical way. As a whole, the work on combinations of exact algorithms and metaheuristics surveyed, documents the usefulness and strong potential of this research direction. As first application we present an integrative combination for solving three-stage 2BP. New integer linear programming formulations are developed:<br />models for a restricted version and the original version of the problem are given. Both only involve polynomial numbers of variables and constraints and effectively avoid symmetries. These models are solved using the general-purpose IP-solver CPLEX. Furthermore, a branch-and-price (B\&P) algorithm is presented for a set covering formulation of the unrestricted problem. We consider column generation stabilization in the B\&P algorithm using dual-optimal inequalities. Fast column generation is performed by applying a hierarchy of four methods: (a) a fast greedy heuristic, (b) an evolutionary algorithm, (c) solving a restricted form of the pricing problem using CPLEX, and finally (d) solving the complete pricing problem using CPLEX.<br />Computational experiments on standard benchmark instances document the benefits of the new approaches: The restricted version of the integer linear programming model can be used to obtain near-optimal solutions quickly. The unrestricted version is computationally more expensive. Column generation provides a strong lower bound for 3-stage 2BP. The combination of all four pricing algorithms and column generation stabilization in the proposed B\&P framework yields the best results in terms of the average objective value, the average run-time, and the number of instances solved to proven optimality.<br />We then study the MKP, present some theoretical and empirical results about its structure, and evaluate different ILP-based, metaheuristic, and collaborative approaches for it. A short introduction to the multidimensional knapsack problem is followed by an empirical analysis of widely used benchmark instances. First the distances between optimal solutions to the LP-relaxation and the original problem are studied. Second we introduce the new core concept for the MKP and conduct an extensive study of it. The empirical analysis is then used to develop new concepts for solving the MKP using ILP-based and memetic algorithms. We then describe the newly developed Relaxation Guided Variable Neighborhood Search in general, and its implementation for the MKP in particular. Different collaborative combinations of the algorithms presented are discussed and evaluated. Further computational experiments with longer run-times are also performed in order to compare the solutions of our approaches to the best known solutions for the MKP. Several of the collaborative and core based approaches were able to reach many of the best known results from the literature in substantially shorter times.<br />In summary, we can note that using the advantages of IP-based methods and metaheuristics by combining them in different ways improves our problem solving capacities for specific problems. The successful results of our approaches suggest, that these types of combinations point to a promising research direction for the solution of NP-hard combinatorial optimization problems.