Fortgeschrittene Algorithmen und Heuristiken zur Lösung quantifizierter gemischt - ganzzahliger linearer Programme
Zusammenfassung der Projektergebnisse
The domain of our research addresses extensions of mixed integer linear programs and quantified linear integer programs. A new mathematical object allows us to restrict the uncertainty set, given in form of universal variables, to integer points of a polytope or even allow this polytope to be changed by assignments of existentially quantified variables, making it suitable to model robust multistage optimization problems with polyhedral and even decision-dependent uncertainty. Two complementary goals and research branches are followed in this long-time project which began at 2008 and is still not at its end. One branch regards the software Yasol, which is a model&run solver for optimization under uncertainty. To compare it with other existing optimization packages, one might say it is a kind of “Cbc for PSPACE”. The other branch regards the technology behind the software. Because the input description targets at a PSPACE complete problem, it is to be expected that the main algorithm cannot run in polynomial time and thus consists in its heart of a tree search with exponential time behaviour. Nonetheless, similar as for the MIP problem, there are many opportunities to shorten the computations heuristically. The focus is to exploit the tree structure of the search process. However, these heuristics are, although simple in its doing, often very tricky to control and it is non-trivial to guarantee correctness and that the optimal solution is not lost. The major achievements are as follows. A suitable coherent mathematical description has been developed for the new problem and first problem definitions are presented to give an impression of its modelling power. Numerical experiments give an idea how far the model&run concept can carry. - A software for this problem has been developed. Technically, this solver can be seen as a hybrid between a MIP solver and a game playing program where two players interact. - We found heuristics which abbreviate the search process in a way that tree like strategies can be identified without traversing them explicitly. We could, moreover, adapt many wellknown techniques from MIP programming and QBF solving in order to find dual bounds, i.e. ensure the quality of the found strategies. - Clear is that all PSPACE complete problems can be reduced to each other in polynomial time. Nonetheless, we got a surprising insight, how a problem with interdependent domains of two players can be reduced to an intuitively simpler structured problem without interdependent domains. - We had to learn that even seemingly simplest heuristics which do a nice job in the MIP world, are surprisingly nasty to transfer, and many efforts to transfer knowledge to the new problem domain demand sophisticated thoughts and formal proofs. An example for a simple search space reducing technique, which has to be handled cautiously, is the concept of dominating columns. Compared with traditional multi-stage optimization under uncertainty, there is no longer the need for tedious reformulation and dualization procedures that turn out to be in vain as soon as parts of the model change. Using the example of the so called multilevel critical node problem, we showcased that our solver provides a solid baseline while only having to state the problem in the most straightforward manner. Another major advantage of our search-based approach is the possibility to retrieve incumbent solutions, rather than bounds from a row-and-column generation approach.
Projektbezogene Publikationen (Auswahl)
-
A general model-and-run solver for multistage robust discrete linear optimization
Hartisch, Michael & Hartisch, Ulf Lorenz
-
Mastering Uncertainty: Towards Robust Multistage Optimization with Decision Dependent Uncertainty. Lecture Notes in Computer Science, 446-458. Springer International Publishing.
Hartisch, Michael & Lorenz, Ulf
-
A Novel Application for Game Tree Search - Exploiting Pruning Mechanisms for Quantified Integer Programs. Lecture Notes in Computer Science, 66-78. Springer International Publishing.
Hartisch, Michael & Lorenz, Ulf
-
Quantified integer programming with polyhedral and decisiondependent uncertainty. PhD-Thesis, University of Siegen, Germany (2020)
Hartisch, Michael
-
Adaptive Relaxations for Multistage Robust Optimization. Lecture Notes in Computer Science, 485-499. Springer International Publishing.
Hartisch, Michael
-
Multistage robust discrete optimization via quantified integer programming. Computers & Operations Research, 135, 105434.
Goerigk, Marc & Hartisch, Michael
-
Robust Topology Optimization of Truss-Like Space Structures. Lecture Notes in Mechanical Engineering, 296-306. Springer International Publishing.
Hartisch, Michael; Reintjes, Christian; Marx, Tobias & Lorenz, Ulf
