Universiẗat, Diss., 2000--Dortmund. / Dateiformat: PDF.

Techn. University, Diss., 2007--Darmstadt.

Heidelberg, Univ., Diss., 2006.

Universiẗat, Diss., 2002--Bonn.

In der Dissertation werden Aufgaben der Zwei-Ebenen-Optimierung mit diskreter unterer und stetiger oberer Ebene betrachtet. Es werden die Struktur dieser Aufgaben analysiert und Optimalitätsbedingungen angegeben. Dies erfolgt sowohl für den optimistischen und den pessimistischen Lösungszugang als auch für einen Lösungszugang mittels Auswahlfunktionen. Anschließend werden die theoretischen Ergebnisse auf drei verschiedene Aufgabenklassen angewendet.

In der Dissertation werden Aufgaben der Zwei-Ebenen-Optimierung mit diskreter unterer und stetiger oberer Ebene betrachtet. Es werden die Struktur dieser Aufgaben analysiert und Optimalitätsbedingungen angegeben. Dies erfolgt sowohl für den optimistischen und den pessimistischen Lösungszugang als auch für einen Lösungszugang mittels Auswahlfunktionen. Anschließend werden die theoretischen Ergebnisse auf drei verschiedene Aufgabenklassen angewendet.

Einem Konsumenten werden in verschiedensten Situationen Rabatte angeboten. In dieser Dissertation wird die Frage untersucht, wie solche Rabattsituationen aus konsumentensicht formalisiert werden können und wie Kaufentscheidungen getroffen werden können. Um diese Frage zu beantworten, wird ein formaler Rahmen für Rabattsituationen angegeben und zur Analyse einer neuen Gruppe von acht Problemen, die auf alltäglichen Erfahrungen mit Rabattaktionen basieren, angewendet. Diese Probleme werden hinsichtlich der Rabattgrundlage (Stempel / Punkte), dem Kartentyp (Einzelkarte, Gruppenkarte) und der Frage, ob Stempel/Punkte für Käufe mit Rabatt gesammelt werden, unterschieden. Der inhärenten Planungsunsicherheit für Konsumentenentscheidungen wird explizit durch die Betrachtung jedes Problems als eine Onlinesituation Rechnung getragen. Für die Onlineprobleme wird eine zugeschnittene Methode zur Güteabschätzung präsentiert. Jedes der acht Probleme wird als Entscheidungs-, Optimierungs- und Onlineproblem analysiert. Für alle Entscheidungsprobleme wird NP-Vollständigkeit nachgewiesen. Jedes Optimierungsproblem wird mit ganzzahliger linearer Programmierung und einige stempelbasierte Probleme zusätzlich mit dynamischer Programmierung gelöst. Für die Onlineprobleme wird jeweils eine untere Güteschranke gezeigt und für drei Gruppen von Onlinealgorithmen die Güte abgeschätzt.:1. Einleitung 2. Vorbetrachtungen 3. Problemformulierung und Analysemethodik 4. Die Probleme im Detail 5. Zusammenfassung 6. Ausblick A. Implementationen / A consumer is offered discounts in a variety of situations. The central question investigated in this dissertation is how to formalize such discount situations from a consumer perspective and what methods for deducing purchase decisions are possible. To answer this question a formal framework for discount situations is established and used to explore a new group of eight discount problems based on everyday experience with loyalty programs. These problems are distinguished by discount basis (stamps / points), card type (single / group) and whether stamps/-points are collectable if a discount is granted. The inherent uncertainty in consumer decisions is explicitly taken into account by considering each of these problems as an online situation as well. Regarding the online problems, a method for competitive analysis is presented. Each of the eight problems is examined as a decision, an optimization and an online problem. For all decision problems N P-completeness is shown. Each optimization problem is solved via linear integer programming and some stamp based optimization problems are furthermore solved with dynamic programming. For each online problem a lower bound on the competitive ratio is presented together with three groups of online algorithms and the respective bounds on the competitive ratio.:1. Einleitung 2. Vorbetrachtungen 3. Problemformulierung und Analysemethodik 4. Die Probleme im Detail 5. Zusammenfassung 6. Ausblick A. Implementationen

Within such disciplines as Management Science, Information and Computer Science, Engineering, Mathematics and Operations Research, problems of cutting and packing (C&P) of concrete and abstract objects appear under various specifications (cutting problems, knapsack problems, container and vehicle loading problems, pallet loading, bin packing, assembly line balancing, capital budgeting, changing coins, etc.), although they all have essentially the same logical structure. In cutting problems, a large object must be divided into smaller pieces; in packing problems, small items must be combined to large objects. Most of these problems are NP-hard. Since the pioneer work of L.V. Kantorovich in 1939, which first appeared in the West in 1960, there has been a steadily growing number of contributions in this research area. In 1961, P. Gilmore and R. Gomory presented a linear programming relaxation of the one-dimensional cutting stock problem. The best-performing algorithms today are based on their relaxation. It was, however, more than three decades before the first `optimum? algorithms appeared in the literature and they even proved to perform better than heuristics. They were of two main kinds: enumerative algorithms working by separation of the feasible set and cutting plane algorithms which cut off infeasible solutions. For many other combinatorial problems, these two approaches have been successfully combined. In this thesis we do it for one-dimensional stock cutting and two-dimensional two-stage constrained cutting. For the two-dimensional problem, the combined scheme provides mostly better solutions than other methods, especially on large-scale instances, in little time. For the one-dimensional problem, the integration of cuts into the enumerative scheme improves the results of the latter only in exceptional cases. While the main optimization goal is to minimize material input or trim loss (waste), in a real-life cutting process there are some further criteria, e.g., the number of different cutting patterns (setups) and open stacks. Some new methods and models are proposed. Then, an approach combining both objectives will be presented, to our knowledge, for the first time. We believe this approach will be highly relevant for industry.

Diskrete Optimierung beschäftigt sich mit dem Identifizieren einer Kombination oder Permutation von Elementen, die im Hinblick auf ein gegebenes quantitatives Kriterium optimal ist. Anwendungen dafür entstehen aus Problemen in der Wirtschaft, der industriellen Fertigung, den Ingenieursdisziplinen, der Mathematik und Informatik. Dazu gehören unter anderem maschinelles Lernen, die Planung der Reihenfolge und Terminierung von Fertigungsprozessen oder das Layout von integrierten Schaltkreisen. Häufig sind diskrete Optimierungsprobleme NP-hart. Dadurch kommt der Erforschung effizienter, heuristischer Suchalgorithmen eine große Bedeutung zu, um für mittlere und große Probleminstanzen überhaupt gute Lösungen finden zu können. Dabei wird die Entwicklung von Algorithmen dadurch erschwert, dass Eigenschaften der Probleminstanzen aufgrund von deren Größe und Komplexität häufig schwer zu identifizieren sind. Ebenso herausfordernd ist die Analyse und Evaluierung von gegebenen Algorithmen, da das Suchverhalten häufig schwer zu charakterisieren ist. Das trifft besonders im Fall von emergentem Verhalten zu, wie es in der Forschung der Schwarmintelligenz vorkommt. Visualisierung zielt auf das Nutzen des menschlichen Sehens zur Datenverarbeitung ab. Das Gehirn hat enorme Fähigkeiten optische Reize von den Sehnerven zu analysieren, Formen und Muster darin zu erkennen, ihnen Bedeutung zu verleihen und dadurch ein intuitives Verstehen des Gesehenen zu ermöglichen. Diese Fähigkeit kann im Speziellen genutzt werden, um Hypothesen über komplexe Daten zu generieren, indem man sie in einem Bild repräsentiert und so dem visuellen System des Betrachters zugänglich macht. Bisher wurde Visualisierung kaum genutzt um speziell die Forschung in diskreter Optimierung zu unterstützen. Mit dieser Dissertation soll ein Ausgangspunkt geschaffen werden, um den vermehrten Einsatz von Visualisierung bei der Entwicklung von Suchheuristiken zu ermöglichen. Dazu werden zunächst die zentralen Fragen in der Algorithmenentwicklung diskutiert und daraus folgende Anforderungen an Visualisierungssysteme abgeleitet. Mögliche Forschungsrichtungen in der Visualisierung, die konkreten Nutzen für die Forschung in der Optimierung ergeben, werden vorgestellt. Darauf aufbauend werden drei Visualisierungssysteme und eine Analysemethode für die Erforschung diskreter Suche vorgestellt. Drei wichtige Aufgaben von Algorithmendesignern werden dabei adressiert. Zunächst wird ein System für den detaillierten Vergleich von Algorithmen vorgestellt. Auf der Basis von Zwischenergebnissen der Algorithmen auf einer Probleminstanz wird der Suchverlauf der Algorithmen dargestellt. Der Fokus liegt dabei dem Verlauf der Qualität der Lösungen über die Zeit, wobei die Darstellung durch den Experten mit zusätzlichem Wissen oder Klassifizierungen angereichert werden kann. Als zweites wird ein System für die Analyse von Suchlandschaften vorgestellt. Auf Basis von Pfaden und Abständen in der Landschaft wird eine Karte der Probleminstanz gezeichnet, die strukturelle Merkmale intuitiv erfassbar macht. Der zweite Teil der Dissertation beschäftigt sich mit der topologischen Analyse von Suchlandschaften, aufbauend auf einer Schwellwertanalyse. Ein Visualisierungssystem wird vorgestellt, dass ein topologisch equivalentes Höhenprofil der Suchlandschaft darstellt, um die topologische Struktur begreifbar zu machen. Dieses System ermöglicht zudem, den Suchverlauf eines Algorithmus direkt in der Suchlandschaft zu beobachten, was insbesondere bei der Untersuchung von Schwarmintelligenzalgorithmen interessant ist. Die Berechnung der topologischen Struktur setzt eine vollständige Aufzählung aller Lösungen voraus, was aufgrund der Größe der Suchlandschaften im allgemeinen nicht möglich ist. Um eine Anwendbarkeit der Analyse auf größere Probleminstanzen zu ermöglichen, wird eine Methode zur Abschätzung der Topologie vorgestellt. Die Methode erlaubt eine schrittweise Verfeinerung der topologischen Struktur und lässt sich heuristisch steuern. Dadurch können Wissen und Hypothesen des Experten einfließen um eine möglichst hohe Qualität der Annäherung zu erreichen bei gleichzeitig überschaubarem Berechnungsaufwand. / Discrete optimization deals with the identification of combinations or permutations of elements that are optimal with regard to a specific, quantitative criterion. Applications arise from problems in economy, manufacturing, engineering, mathematics and computer sciences. Among them are machine learning, scheduling of production processes, and the layout of integrated electrical circuits. Typically, discrete optimization problems are NP hard. Thus, the investigation of efficient, heuristic search algorithms is of high relevance in order to find good solutions for medium- and large-sized problem instances, at all. The development of such algorithms is complicated, because the properties of problem instances are often hard to identify due to the size and complexity of the instances. Likewise, the analysis and evaluation of given algorithms is challenging, because the search behavior of an algorithm is hard to characterize, especially in case of emergent behavior as investigated in swarm intelligence research. Visualization targets taking advantage of human vision in order to do data processing. The visual brain possesses tremendous capabilities to analyse optical stimulation through the visual nerves, perceive shapes and patterns, assign meaning to them and thus facilitate an intuitive understanding of the seen. In particular, this can be used to generate hypotheses about complex data by representing them in a well-designed depiction and making it accessible to the visual system of the viewer. So far, there is only little use of visualization to support the discrete optimization research. This thesis is meant as a starting point to allow for an increased application of visualization throughout the process of developing discrete search heuristics. For this, we discuss the central questions that arise from the development of heuristics as well as the resulting requirements on visualization systems. Possible directions of research for visualization are described that yield a specific benefit for optimization research. Based on this, three visualization systems and one analysis method are presented. These address three important tasks of algorithm designers. First, a system for the fine-grained comparison of algorithms is introduced. Based on the intermediate results of algorithm runs on a given problem instance the search process is visualized. The focus is on the progress of the solution quality over time while allowing the algorithm expert to augment the depiction with additional domain knowledge and classification of individual solutions. Second, a system for the analysis of search landscapes is presented. Based on paths and distances in the landscape, a map of the problem instance is drawn that facilitates an intuitive cognition of structural properties. The second part of this thesis focuses on the topological analysis of search landscapes, based on barriers. A visualization system is presented that shows a topological equivalent height profile of the search landscape. Further, the system facilitates to observe the search process of an algorithm directly within the search landscape. This is of particular interest when researching swarm intelligence algorithms. The computation of topological structure requires a complete enumeration of all solutions which is not possible in the general case due to the size of the search landscapes. In order to enable an application to larger problem instances, we introduce a method to approximate the topological structure. The method allows for an incremental refinement of the topological approximation that can be controlled using a heuristic. Thus, the domain expert can introduce her knowledge and also hypotheses about the problem instance into the analysis so that an approximation of good quality is achieved with reasonable computational effort.

Within such disciplines as Management Science, Information and Computer Science, Engineering, Mathematics and Operations Research, problems of cutting and packing (C&P) of concrete and abstract objects appear under various specifications (cutting problems, knapsack problems, container and vehicle loading problems, pallet loading, bin packing, assembly line balancing, capital budgeting, changing coins, etc.), although they all have essentially the same logical structure. In cutting problems, a large object must be divided into smaller pieces; in packing problems, small items must be combined to large objects. Most of these problems are NP-hard. Since the pioneer work of L.V. Kantorovich in 1939, which first appeared in the West in 1960, there has been a steadily growing number of contributions in this research area. In 1961, P. Gilmore and R. Gomory presented a linear programming relaxation of the one-dimensional cutting stock problem. The best-performing algorithms today are based on their relaxation. It was, however, more than three decades before the first `optimum? algorithms appeared in the literature and they even proved to perform better than heuristics. They were of two main kinds: enumerative algorithms working by separation of the feasible set and cutting plane algorithms which cut off infeasible solutions. For many other combinatorial problems, these two approaches have been successfully combined. In this thesis we do it for one-dimensional stock cutting and two-dimensional two-stage constrained cutting. For the two-dimensional problem, the combined scheme provides mostly better solutions than other methods, especially on large-scale instances, in little time. For the one-dimensional problem, the integration of cuts into the enumerative scheme improves the results of the latter only in exceptional cases. While the main optimization goal is to minimize material input or trim loss (waste), in a real-life cutting process there are some further criteria, e.g., the number of different cutting patterns (setups) and open stacks. Some new methods and models are proposed. Then, an approach combining both objectives will be presented, to our knowledge, for the first time. We believe this approach will be highly relevant for industry.