Aachen, Techn. Univ., Diss., 2003. / Computerdatei im Fernzugriff.

Aachen, Techn. Univ., Diss., 2003. / Computerdatei im Fernzugriff.

Zugl.: Darmstadt, Techn. Univ., Diss., 2009

Zugl.: Berlin, Humboldt-Univ., Diss., 2006 u.d.T.: Decker, Torsten: Die Charakterisierung des verallgemeinerten Dale-Polytops und ihre Verwendung in linearen Programmen zur Lösung von Austrittszeit-, Stopp- und anderen Optimierungsproblemen

Techn. University, Diss., 2003--Aachen.

A cosmological polytope of an undirected connected graph is a lattice polytope which when the graph is interpreted as a feynman diagram can be used to calculate the contribution of that feynman diagram to the wavefunction of some cosmological models. This contribution can be calculated using the canonical form of the cosmological polytope, which can be computed by taking the sum of the canonical forms of the facets of a subdivision of the cosmological polytope. Juhnke-Kubitzke, Solus and Venturello showed that the cosmological polytope of any undirected connected graph has a regular unimodular triangulation. They characterized the facets of such triangulations for trees and cycles to yield combinatorial formula for the desired canonical forms. Here we characterize the facets of such a triangulation of the cosmological polytope of the complete bipartite graph K_{2,n} and use that characterization to calculate the normalized volume. / Ett kosmologiskt polytop av en oriktad sammanhängande graf är ett gitterpolytop, vilket när grafen tolkas som ett feynman diagram kan användas för att beräkna bidraget av feynman diagrammet till vågfunktionen av vissa kosmologiska modeller. Detta bidrag can beräknas genom att använda den kanoniska formen av det kosmologiska polytopet, som kan beräknas genom att ta summan av de kanoniska formerna av facetterna av en uppdelning av det kosmologiska polytopet. Juhnke-Kubitzke, Solus och Venturello visade att det kosmologiska polytopet av en oriktad sammanhängande graf har en reguljär unimodulär triangulering. De karaktäriserar facetterna av sådana trianguleringar av träd och cykliska grafer, vilket ger en kombinatorisk formel för de kanoniska formerna av intresse. Här karaktäriserar vi facetterna av en sådan trianguleraing för det kosmologiska polytopet av den kompletta bipartita grafen K_{2,n} och använder denna karaktärisering för att beräkna den normaliserade volymen.

Techn. University, Diss., 2004--Berlin.

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.

Thesis (doctoral)--Universität Karlsruhe, 2002.

Techn. University, Diss., 2005--Berlin.