Computational complexity of problems in robust, bilevel and online optimization

Grüne, Christoph Manfred; Goerigk, Marc; Rossmanith, Peter

doi:HT031326300

Computational complexity of problems in robust, bilevel and online optimization

Grüne, Christoph Manfred^RWTH*

2025

Verantwortlichkeitsangabevorgelegt von Christoph Manfred Grüne, Master of Science

ImpressumAachen : RWTH Aachen University 2025

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2025

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak09

Hauptberichter/Gutachter
Rossmanith, Peter (Thesis advisor)^RWTH* ; Goerigk, Marc (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2025-10-07

Online
DOI: 10.18154/RWTH-2025-09741
URL: https://publications.rwth-aachen.de/record/1021909/files/1021909.pdf

Einrichtungen

Projekte

GRK 2236 - GRK 2236: Unsicherheit und Randomisierung in Algorithmen, Verifikation und Logik. (282652900) (282652900)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Diese Arbeit befasst sich mit der Komplexität von robuster, zweistufiger und Echtzeit-Optimierung. In diesen Gebieten beschäftigen wir uns mit min-max (beziehungsweise mehrstufigen) Problemen aus den beliebten Themenbereichen von Netzwerk-Untersagung, Wichtigste-Knoten-Probleme, Min-Max-Bedauern-Optimierung, Zwei-Phasen-Anpassbarkeit-Optimierung, wiederherstellbar-robuster Optimierung und Echtzeit-Optimierung. Obwohl diese Gebiete seit mehr als zwei Jahrzehnten erforscht werden und man natürlicherweise die meisten der Probleme als vollständig für die unteren Stufen der polynomiellen Hierarchie oder polynomiellen Platz einschätzt, sind kaum exakte Vollständigkeitsresultate bekannt. Wir adressieren diese Lücke, indem wir zwei Reduktionsrahmenstrukturen entwickeln, um die gemeinsamen Strukturen von kombinatorischen Problemen zu analysieren, die eine Art von Unsicherheit enthalten, die wiederum ein ähnliches Verhalten in ihrer Komplexität induzieren. Die Reduktionsrahmenstrukturen funktionieren wie folgt. Zuerst definieren wir kombinatorische Probleme im Allgemeinen, diese nennen wir auch nominale Probleme. Basierend auf dieser Definition des nominalen Problems können wir Definitionen für die allgemeineren Varianten ableiten, die bestimmte Arten von Unsicherheiten modellieren. Die übergeordnete Idee ist nun, die Reduktionen zwischen den nominalen Problemen auf gemeinsame Eigenschaften zu untersuchen, die uns helfen, Reduktionen zwischen den allgemeineren Varianten herzuleiten. Demzufolge definieren wir solch eine Art von Reduktion und zeigen, dass diese Eigenschaften bereits von existierenden Reduktionen oder geringen Modifikationen dieser erfüllt werden. Wir wenden die Rahmenstrukturen auf $\mathsf{NP}$-vollständige nominale Probleme an und leiten Komplexitätsresultate für die Vollständigkeit in der polynomiellen Hierarchie oder der Komplexitätsklasse $\mathsf{PSPACE}$ ab. Die erste Rahmenstruktur beschäftigt sich mit Teilmengensuchproblemen (abgekürzt TSP), wir nennen die Rahmenstruktur daher TSP-Rahmenstruktur. Ein Teilmengensuchproblem ist ein kombinatorisches Problem, das aus Instanzen $\mathcal{I}$ besteht, die wiederum ein Universum $\mathcal{U}$ zusammen mit weiteren Informationen enthalten. Eine Lösung $S \in \mathcal{S}$ ist eine Teilmenge des Universums, d.h. $S \subseteq \mathcal{U}$.Die entsprechenden TSP-Reduktionen sind gewöhnliche Reduktionen zusammen mit einer zusätzlichen injektiven Funktion, die das Universum des einen Problems in das des anderen Problems abbilden. Tatsächlich erfüllen viele existierende Reduktionen auf der $\mathsf{NP}$-Ebene genau diese TSP-Eigenschaft. Basierend auf diesem Begriff können wir die TSP-Reduktionen zwischen den nominalen Probleme zu Reduktionen zwischen den Problemversionen im Gebiet von robuster und zweistufiger Optimierung aufrüsten. Wir wenden diese Rahmenstruktur konkret auf die Gebiete von Untersagung, Min-Max-Bedauern-Optimierung, Zwei-Phasen-Anpassbarkeit-Optimierung, und wiederherstellbar-robuster Optimierung an und zeigen $\Sigma^p_2$- und $\Sigma^p_3$-Vollständigkeit für die entsprechenden Probleme, wenn das nominale Problem $\mathsf{NP}$-vollständig ist.In der zweiten Rahmenstruktur geht es um kombinatorische Probleme, die mit einem unterliegenden Universum und verschachtelten Relationen über dem Universum beschrieben werden können. Die entsprechende Reduktion nennen wir Universum-Apparat-Reduktion. Die besondere Eigenschaft einer Universum-Apparat-Reduktion von einem Problem $A$ zu einem Problem $B$ ist, dass ein Apparat für jedes Universumselement und jedes Relationselement des Problems $A$ erzeugt wird. Diese Apparate bestehen aus den Universums- und Relationselementen des Problems $B$ und sind disjunkt. Basierend auf dieser Reduktion sind wir fähig, $\Sigma^p_3$-Vollständigkeit für Variationen von wiederherstellbar-robuste Problemen und $\mathsf{PSPACE}$-Vollständigkeit von Echtzeit-Graph-Problemen mit einer Karte zu zeigen.

This thesis deals with the complexity of robust, bilevel, and online optimization. In these areas, we are concerned with min-max (respectively multi-stage) problems from the popular areas of network interdiction, most vital vertex problems, min-max regret optimization, two-stage adjustable problems, recoverable robustness, and online optimization. Although these areas have been well-researched for more than two decades, and one would naturally expect most of the problems to be complete for lower levels of the polynomial hierarchy or polynomial space, almost no hardness results are known. We address this issue by designing two reduction frameworks with the goal of analyzing the common substructure of combinatorial problems that include some form of uncertainty, which induces similar complexity behavior. The reduction frameworks work as follows. We first provide a general definition of a combinatorial problem, which is also called the nominal problem. Based on this definition of a nominal problem, we are able to derive definitions for more general variations of that problem that additionally model some kind of uncertainty. The general idea is now to examine the reductions between the nominal problems and determine if additional properties hold that help us to directly derive reductions for the more general variations. Accordingly, we provide a definition of such a reduction and show that these properties are already fulfilled by existing reductions or slight modifications of them. We apply these frameworks to nominal problems that are $\mathsf{NP}$-complete and derive complexity results for completeness in the polynomial hierarchy and in $\mathsf{PSPACE}$.The first framework is concerned with subset search problems (or in short SSP), thus it is named SSP framework. A subset search problem is a combinatorial problem that consists of instances $\mathcal{I}$ that contain a universe $\mathcal{U}$ together with additional information. A solution $S \in \mathcal{S}$ is a subset of the universe, i.e. $S \subseteq \mathcal{U}$.The corresponding SSP reductions are usual reductions with an additional injective function that maps the universe of the one problem into that of the other. Indeed, many existing reductions on the $\mathsf{NP}$-level fulfill this SSP property. Based on this notion, we are able to "upgrade" the SSP reductions between the nominal problems to reductions between the problem versions in the areas of robust and bilevel optimization. Concretely, we apply this framework to the areas of interdiction, min-max regret optimization, two-stage adjustable robustness, and recoverable robustness, and prove $\Sigma^p_2$- and $\Sigma^p_3$-completeness for the corresponding problems if the nominal problem is $\mathsf{NP}$-complete. The second framework considers combinatorial problems, which can be described by an underlying universe $U$ and nested relations $R$ over the universe. The corresponding reduction is termed universe gadget reduction. The special property of a universe gadget reduction from problem $A$ to $B$ is that a gadget is created for every universe element and every relational element from any of the relations of problem $A$. These gadgets consist of the universe and relation elements of the problem $B$ and are disjoint. Based on this reduction, we are able to show $\Sigma^p_3$-completeness for variations of recoverable robust problems and $\mathsf{PSPACE}$-completeness for several online graph problems with a map.

OpenAccess:
PDF
(additional files)