NP-hard problems of higher-dimensional orthogonal packing are considered. We look closer at their logical structure and show that they can be decomposed into problems of a smaller dimension with a special contiguous structure. This decomposition influences the modeling of the packing process, which results in three new solution approaches.
Keeping this decomposition in mind, we model the smaller-dimensional problems in a single position-indexed formulation with non-overlapping inequalities serving as binding constraints. Thus, we come up with a new integer linear programming model, which we subject to polyhedral analysis. Furthermore, we establish general non-overlapping and density inequalities and prove under appropriate assumptions their facet-defining property for the convex hull of the integer solutions. Based on the proposed model and the strong inequalities, we develop a new branch-and-cut algorithm.
Being a relaxation of the higher-dimensional problem, each of the smaller-dimensional problems is also relevant for different areas, e.g. for scheduling. To tackle any of these smaller-dimensional problems, we use a Gilmore-Gomory model, which is a Dantzig-Wolfe decomposition of the position-indexed formulation. In order to obtain a contiguous structure for the optimal solution, its basis matrix must have a consecutive 1's property. For construction of such matrices, we develop new branch-and-price algorithms which are distinguished by various strategies for the enumeration of partial solutions. We also prove some characteristics of partial solutions, which tighten the slave problem of column generation.
For a nonlinear modeling of the higher-dimensional packing problems, we investigate state-of-the-art constraint programming approaches, modify them, and propose new dichotomy and intersection branching strategies. To tighten the constraint propagation, we introduce new pruning rules. For that, we apply 1D relaxation with intervals and forbidden pairs, an advanced bar relaxation, 2D slice relaxation, and 1D slice-bar relaxation with forbidden pairs. The new rules are based on the relaxation by the smaller-dimensional problems which, in turn, are replaced by a linear programming relaxation of the Gilmore-Gomory model.
We conclude with a discussion of implementation issues and numerical studies of all proposed approaches. / Es werden NP-schwere höherdimensionale orthogonale Packungsprobleme betrachtet. Wir untersuchen ihre logische Struktur genauer und zeigen, dass sie sich in Probleme kleinerer Dimension mit einer speziellen Nachbarschaftsstruktur zerlegen lassen. Dies beeinflusst die Modellierung des Packungsprozesses, die ihreseits zu drei neuen Lösungsansätzen führt.
Unter Beachtung dieser Zerlegung modellieren wir die Probleme kleinerer Dimension in einer einzigen positionsindizierten Formulierung mit Nichtüberlappungsungleichungen, die als Bindungsbedingungen dienen. Damit entwickeln wir ein neues Modell der ganzzahligen linearen Optimierung und unterziehen dies einer Polyederanalyse. Weiterhin geben wir allgemeine Nichtüberlappungs- und Dichtheitsungleichungen an und beweisen unter geeigneten Annahmen ihre facettendefinierende Eigenschaft für die konvexe Hülle der ganzzahligen Lösungen. Basierend auf dem vorgeschlagenen Modell und den starken Ungleichungen entwickeln wir einen neuen Branch-and-Cut-Algorithmus.
Jedes Problem kleinerer Dimension ist eine Relaxation des höherdimensionalen Problems. Darüber hinaus besitzt es Anwendungen in verschiedenen Bereichen, wie zum Beispiel im Scheduling. Für die Behandlung der Probleme kleinerer Dimension setzen wir das Gilmore-Gomory-Modell ein, das eine Dantzig-Wolfe-Dekomposition der positionsindizierten Formulierung ist. Um eine Nachbarschaftsstruktur zu erhalten, muss die Basismatrix der optimalen Lösung die consecutive-1’s-Eigenschaft erfüllen. Für die Konstruktion solcher Matrizen entwickeln wir neue Branch-and-Price-Algorithmen, die sich durch Strategien zur Enumeration von partiellen Lösungen unterscheiden. Wir beweisen auch einige Charakteristiken von partiellen Lösungen, die das Hilfsproblem der Spaltengenerierung verschärfen.
Für die nichtlineare Modellierung der höherdimensionalen Packungsprobleme untersuchen wir moderne Ansätze des Constraint Programming, modifizieren diese und schlagen neue Dichotomie- und Überschneidungsstrategien für die Verzweigung vor. Für die Verstärkung der Constraint Propagation stellen wir neue Ablehnungskriterien vor. Wir nutzen dabei 1D Relaxationen mit Intervallen und verbotenen Paaren, erweiterte Streifen-Relaxation, 2D Scheiben-Relaxation und 1D Scheiben-Streifen-Relaxation mit verbotenen Paaren. Alle vorgestellten Kriterien basieren auf Relaxationen durch Probleme kleinerer Dimension, die wir weiter durch die LP-Relaxation des Gilmore-Gomory-Modells abschwächen.
Wir schließen mit Umsetzungsfragen und numerischen Experimenten aller vorgeschlagenen Ansätze.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:27750 |
| Date | 12 February 2014 |
| Creators | Mesyagutov, Marat |
| Contributors | Fischer, Andreas, Scheithauer, Guntram, Clautiaux, François, Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0017 seconds