Combinatorial optimization with one quadratic term

Abstract

Diese Arbeit befasst sich mit einer neuen Herangehensweise für binäre kombinatorische Optimierungsprobleme. Die wesentliche Idee hierbei ist, die Anzahl der quadratischen Terme in der Zielfunktion auf einen einzigen zu beschränken, und das durch eine Linearisierung entstehende Polyeder zu analysieren. Für diesen Ansatz gibt es mehrere Motivationsgründe. Im Allgemeinen ist das ursprüngliche Problem mit beliebig vielen quadratischen Termen NP-schwer. Doch obwohl eine gute polyedrische Beschreibung mit schnellen Separierungsroutinen die Optimierung in einem Branch-and-Cut-Verfahren signifikant beschleunigen könnte, gibt es bislang nur wenige Erkenntnisse zur polyedrischen Struktur des binären quadratischen Optimierungsproblems. Betrachtet man das reduzierte Problem mit einem quadratischen Term, dann ist eine effiziente Optimierung möglich, falls die zugrundeliegende lineare Version effizient lösbar ist. Somit können hier auch die facettendefinierenden Ungleichungen effizient separiert werden. Darüberhinaus bleiben alle zulässigen Ungleichungen des reduzierten Problems zulässig für das ursprüngliche Problem. In Kombination bedeutet dies, dass Erkenntnisse zur Facettenstruktur des Problems mit einem quadratischen Term direkt zu einer verbesserten polyedrische Beschreibung des Ursprungsproblems führen. Für eine praktische Anwendung dieses theoretischen Ansatzes betrachten wir verschiedene konkrete Optimierungsprobleme mit einem quadratischen Term und analysieren deren jeweilige polyedrische Struktur, die sich nach der Linearisierung ergibt. Konkret betrachten wir das Minimale Spannwald- und das Minimale Spannbaumproblem, das Minimale Branching- und das Minimale Arboreszenzproblem, das Minimale Assignmentproblem und das Maximale Matchingproblem. Für jedes dieser Optimierungsprobleme leiten wir neue Klassen von facettendefinierenden Ungleichungen her. Außerdem präsentieren wir für das Minimale Spannwald- und das Minimale Spannbaumproblem eine vollständige Beschreibung der jeweiligen Polytope. Für die verwandten gerichteten Probleme, das Minimale Branching- und das Minimale Arboreszenzproblem, zeigen wir zwar einerseits einige Gemeinsamkeiten mit den ungerichteten Problemen, andererseits aber auch, dass sich die polyedrischen Strukturen im gerichteten Fall durch die zusätzlichen Gradbedingungen deutlich verkomplizieren. Bei der Untersuchung des Minimalen Assignmentproblems mit einem quadratischen Term stellen wir nicht nur die Vermutung über die vollständige polyedrische Beschreibung auf, sondern kommen insbesondere zu der überraschenden Erkenntnis, dass bereits ein einziger quadratischer Term genügen kann, um die Anzahl der Facetten von polynomiell auf exponentiell zu erhöhen. Die größte Vielfalt an Facettenklassen leiten wir für das Polyeder des Maximalen Matchingproblems mit einem quadratischen Term her. Wir zeigen jedoch auch, dass diese noch nicht genügen, um die vollständige Beschreibung des Polyeders zu erhalten. Da die meisten der hergeleiteten Facettenklassen von exponentieller Größe sind, leiten wir verschiedene Routinen für eine polynomielle Separierung her. Unsere exemplarischen Rechenergebnisse für das quadratische Minimale Spannwald- und das quadratische Minimale Spannbaumproblem zeigen die praktische Relevanz unseres Ansatzes.