Extended formulations for higher order polytopes in combinatorial optimization
Creators: name: Friesen, Mirjam
Publisher: name: Universitäts- und Landesbibliothek Sachsen-Anhalt
Year: 2019
Subjects: subject: Kombinatorik
subject: Graphentheorie
subject: 519.64

description: bei denen y ein Monom in x ist. Diese Vektoren können als charakteristische Vektoren höherer Ordnung kombinatorischer Strukturen betrachtet werden. Wir nennen diese Polytope entsprechend Polytope höherer Ordnung. Mit Hilfe von linearer Optimierung über diese Art von Polytopen können polynomielle Optimierungsprobleme wie zum Beispiel das quadratische minimale Spannbaumproblem (QMST-Problem) gelöst werden. Diese Probleme sind häufig NP-schwer und in der Regel sind keine vollständigen Beschreibungen der zugehörigen Polytope höherer Ordnung in Form von Gleichungen und Ungleichungen bekannt. Es gibt Beschreibungen für Matroidpolytope höherer Ordnung, allerdings nur für sehr spezielle Mengen von Monomen [15] [16]. Diese Beschreibungen brauchen exponentiell (in der Größe der Grundmenge) viele Ungleichungen. In dieser Arbeit erforschen wir erweiterte Formulierungen. Um Monome zu modellieren, nutzen wir kleine erweiterte Formulierungen des Spannbaumpolytops. Mit klein meinen wir Formulierungen, welche nur polynomiell (in der Anzahl der Graphknoten) viele Ungleichungen haben. Die erweiterten Formulierungen beinhalten zusätzliche strukturelle Informationen, mit deren Hilfe wir kleine erweiterte Formulierungen derWaldpolytope höherer Ordnung mit verschachtelten Monomen, welche Bäumen entsprechen, und mit verschachtelten Monomen vom maximalen Grad 3 modellieren. Das beinhaltet den Fall von einem Monom vom Grad 2 oder 3 und impliziert Formulierungen für die zugehörigen Spannbaumpolytope höherer Ordnung. Der Fall mit einem Monom vom Grad 2 ist durch seine Verbindung zum QMST-Problem besonders interessant. Indem wir die Beschreibung der Spannbaumpolytope mit einem Monom vom Grad 2 für alle möglichen grad-2 Monome kombinieren, erhalten wir eine Relaxierung des quadratischen Spannbaumpolytopes. Nutzen wir als Beschreibungen unsere erweiterten Formulierungen, modellieren wir auf implizierte Weise eine zusätzliche Beziehung zwischen den Monomen und verbessern die Relaxierung im Vergleich zu jener, welche wir mit den Beschreibungen im Originalraum erhalten. Als Nebenresultat finden wir neue Facetten des adjazenten quadratischen Waldpolytopes und des adjazenten quadratischen Spannbaumpolytopes. Mit Hilfe von Computerexperimenten veranschaulichen wir den Grad der Verbesserung in den Relaxierungen. Bezüglich gerichteter Graphen wissen wir von keiner vollständigen Beschreibung für Arboreszenzpolytope höherer Ordnung, solange die Monommenge nichtleer ist. Wir vergleichen zwei erweiterte Formulierungen des Arboreszenzpolytopes bezüglich der Möglichkeiten einzelne grad-2 Monome zu modellieren. Die erweiterten Formulierungen projizieren auf neue Relaxierungen der zugehörigen Arboreszenzpolytope höherer Ordnung.
description: We are interested in the convex hull of vectors (x, y) 2 f0, 1gn, where y is a monomial in x. Those vectors can be considered as higher order characteristic vectors of combinatorial structures. Accordingly, we call those polytopes higher order polytopes. Linear optimization over those polytopes solves polynomial combinatorial optimization problems like for example the quadratic minimum spanning tree problem (QMST-problem). Those problems are often NPhard and complete descriptions of the corresponding higher order polytopes in terms of equations and inequalities are usually unknown. There are descriptions of higher order matroid polytopes, but only for special sets of monomials [15] [16]. Those descriptions have exponentially (in the size of the ground set) many inequalities. In this work, we investigate extended formulations. To model monomials, we use small extended formulations for the spanning tree polytope. By small we mean formulations that do only have polynomially (in the number of graph nodes) many inequalities. The extended formulations provide additional structural information, which we use to model small extended formulations for higher order forest polytopes with nested monomials that are trees and with nested monomials up to degreethree. This includes the cases of one degree-two or degree-three monomial and implies formulations for the corresponding higher order spanning tree polytopes. The degree-two case is of special interest due to its relation to the QMST-problem. Combining the descriptions of higher order spanning tree polytopes with one degree-two monomial for all possible degreetwo monomials, we obtain a relaxation of the quadratic spanning tree polytope. Doing this with our extended formulations for one degreetwo monomial we model in an implicit way a further relation between the monomials and improve the relaxation compared to those we obtain using the descriptions in the original space. As a side effect, we find new facets of the adjacent quadratic forest polytope and the adjacent quadratic spanning tree polytope. Via computational experiments we visualize the amount of improvement of the relaxations. Considering directed graphs we do not know a complete description of higher order arborescence polytopes for any nonempty set of monomials. We compare two extended formulations for the arborescence polytope regarding their ability to model degree-two monomials. The extended formulations project onto new relaxations of the corresponding higher order arborescence polytopes.