Spelling suggestions: "subject:"randpunktmethode"" "subject:"transzendenzmethode""
1 |
Relaxations and solutions for the minimum graph bisection problem /Fügenschuh, Marzena. January 2007 (has links)
Zugl.: Darmstadt, Techn. University, Diss., 2007.
|
2 |
Multiple postmen problems fundamentals and new algorithmsAhr, Dino January 2004 (has links)
Zugl.: Heidelberg, Univ., Diss., 2004. - Hergestellt on demand
|
3 |
Struktur von Projektplanungsproblemen aus polyedertheoretischer Sicht /Hagmayer, Steffen. January 2006 (has links)
Zugl.: Karlsruhe, University, Diss., 2006.
|
4 |
Protein folding and self-avoiding walks polyhedral studies and solutions /Dittel, Agnes. January 2008 (has links)
Zugl.: Darmstadt, Techn. University, Diss., 2008.
|
5 |
Branch-and-Cut for a Semidefinite Relaxation of Large-scale Minimum Bisection ProblemsArmbruster, Michael 22 June 2007 (has links) (PDF)
This thesis deals with the exact solution of large-scale minimum bisection problems via a semidefinite relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope a study of new facet-defining inequalities is presented. They are derived from the known knapsack tree inequalities. We investigate strengthenings based on the new cluster weight polytope and present polynomial separation algorithms for special cases. The dual of the semidefinite relaxation of the minimum bisection problem is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Implementational details regarding primal heuristics, branching rules, so-called support extensions for cutting planes and warm start are presented. We conclude with a computational study in which we show that our approach is competetive to state-of-the-art implementations using linear programming or semidefinite programming relaxations. / Diese Dissertation befasst sich mit der exakten Lösung großer Minimum Bisection Probleme über eine semidefinite Relaxierung in einem Branch-and-Cut Zugang. Nachdem bekannte Resultate zum zugrundeliegenden Bisection Cut Polytop dargestellt wurden, wird eine Studie neuer facettendefinierender Ungleichungen präsentiert. Diese werden von den bekannten Knapsack Tree Ungleichungen abgeleitet. Wir untersuchen Verstärkungen basierend auf dem neuen Cluster Weight Polytop und zeigen polynomiale Separierungsalgorithmen für Spezialfälle. Die Duale der semidefiniten Relaxierung des Minumum Bisection Problems wird in ihrer äquivalenten Form als Eigenwertoptimierungsproblem mit dem Spektralen Bündelverfahren bearbeitet. Details der Implementierung bezüglich primaler Heuristiken, Branchingregeln, sogenannter Supporterweiterungen für die Schnittebenen und Warmstart werden präsentiert. Wir beenden die Arbeit mit einer numerischen Studie, in der wir zeigen, dass unser Zugang konkurrenzfähig zu aktuellen Implementationen basierend auf linearen und semidefiniten Relaxierungen ist.
|
6 |
A polyhedral approach to sequence alignment problemsReinert, Knut. Unknown Date (has links) (PDF)
University, Diss., 1999--Saarbrücken.
|
7 |
Branch-and-Cut for a Semidefinite Relaxation of Large-scale Minimum Bisection ProblemsArmbruster, Michael 14 June 2007 (has links)
This thesis deals with the exact solution of large-scale minimum bisection problems via a semidefinite relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope a study of new facet-defining inequalities is presented. They are derived from the known knapsack tree inequalities. We investigate strengthenings based on the new cluster weight polytope and present polynomial separation algorithms for special cases. The dual of the semidefinite relaxation of the minimum bisection problem is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Implementational details regarding primal heuristics, branching rules, so-called support extensions for cutting planes and warm start are presented. We conclude with a computational study in which we show that our approach is competetive to state-of-the-art implementations using linear programming or semidefinite programming relaxations. / Diese Dissertation befasst sich mit der exakten Lösung großer Minimum Bisection Probleme über eine semidefinite Relaxierung in einem Branch-and-Cut Zugang. Nachdem bekannte Resultate zum zugrundeliegenden Bisection Cut Polytop dargestellt wurden, wird eine Studie neuer facettendefinierender Ungleichungen präsentiert. Diese werden von den bekannten Knapsack Tree Ungleichungen abgeleitet. Wir untersuchen Verstärkungen basierend auf dem neuen Cluster Weight Polytop und zeigen polynomiale Separierungsalgorithmen für Spezialfälle. Die Duale der semidefiniten Relaxierung des Minumum Bisection Problems wird in ihrer äquivalenten Form als Eigenwertoptimierungsproblem mit dem Spektralen Bündelverfahren bearbeitet. Details der Implementierung bezüglich primaler Heuristiken, Branchingregeln, sogenannter Supporterweiterungen für die Schnittebenen und Warmstart werden präsentiert. Wir beenden die Arbeit mit einer numerischen Studie, in der wir zeigen, dass unser Zugang konkurrenzfähig zu aktuellen Implementationen basierend auf linearen und semidefiniten Relaxierungen ist.
|
8 |
Probleme der TourenbildungKämpf, Michael 24 November 2006 (has links) (PDF)
Die Tourenbildung beschäftigt sich mit der Konstruktion kostengünstiger
Transportrouten zur Belieferung von Verbrauchern. Sie ist eine der weitreichensten
Erfolgsgeschichten des Operations Research. Das starke Interesse
an diesen Problemen durch Industrie und Forschung liegt zum einen am
wirtschaftlichen Potenzial der Tourenbildung und -optimierung, zum anderen
macht ihr Reichtum an Struktur sie zu einem faszinierenden Forschungsgebiet.
In der vorliegenden Arbeit soll ein Überblick über einige, u. a. auch neuere
mathematische Modell- und Lösungsansätze gegeben werden. Auf Grund der
hohen Anzahl der Veröffentlichungen auf diesem Gebiet wird nicht zwingend
ein Anspruch auf die vollständige Darlegung aller möglichen Problemstellungen
im Zusammenhang mit dem TSP sowie dem VRP und deren Lösungsansätze
erhoben. An den gegebenen Stellen wird statt dessen auf weiterführende Literatur
verwiesen.
|
9 |
Probleme der TourenbildungKämpf, Michael 24 November 2006 (has links)
Die Tourenbildung beschäftigt sich mit der Konstruktion kostengünstiger
Transportrouten zur Belieferung von Verbrauchern. Sie ist eine der weitreichensten
Erfolgsgeschichten des Operations Research. Das starke Interesse
an diesen Problemen durch Industrie und Forschung liegt zum einen am
wirtschaftlichen Potenzial der Tourenbildung und -optimierung, zum anderen
macht ihr Reichtum an Struktur sie zu einem faszinierenden Forschungsgebiet.
In der vorliegenden Arbeit soll ein Überblick über einige, u. a. auch neuere
mathematische Modell- und Lösungsansätze gegeben werden. Auf Grund der
hohen Anzahl der Veröffentlichungen auf diesem Gebiet wird nicht zwingend
ein Anspruch auf die vollständige Darlegung aller möglichen Problemstellungen
im Zusammenhang mit dem TSP sowie dem VRP und deren Lösungsansätze
erhoben. An den gegebenen Stellen wird statt dessen auf weiterführende Literatur
verwiesen.
|
10 |
Exact Approaches for Higher-Dimensional Orthogonal Packing and Related Problems / Zugänge für die exakte Lösung höherdimensionaler orthogonaler Packungsprobleme und verwandter AufgabenMesyagutov, Marat 24 March 2014 (has links) (PDF)
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.
|
Page generated in 0.0969 seconds