Advanced algorithms and heuristics for solving quantified mixed - integer linear programs

传统上，优化问题的输入是预定义的，并且在规划时是众所周知的。然而，考虑到规划过程中的不确定性是一项重要的资产。在文献中有多种方法来处理这些不确定性，一种可能是使用量化的混合整数线性规划，量化的混合整数线性规划是变量存在或普遍量化的混合整数线性规划。它们可以被解释为一方是存在主义者和万能者之间的两人零和博弈，另一方是不确定条件下的多阶段优化问题。量化规划的解决方案是存在主义玩家的所谓制胜策略，它规定了如何对通用玩家的动作做出反应--对普遍量化变量的某些注视--以确保游戏的胜利。我们努力的长期目标是开发一种工具，用于解决量化混合整数线性规划，并将其呈现给公众，只是本着Cplex、Gurobi或SCIP的精神。为了实现这一目标，我们开发、提炼和充实了量化混合整数线性规划这一强大的建模工具的求解过程，以便将其应用于实际相关任务。朝这个方向迈出的一步是发布解算器Yasol，只要它已经存在。我们希望并期待该项目的成果将对研究以及实际优化应用产生深远的影响。作为另一个重要的建模扩展，我们将允许不确定性集合的主动干扰。

Traditionally, it is assumed that the inputs of optimization problems are predefined and well known at planning time. However, considering uncertainty in the planning process is an essential asset. There are various approaches in the literature, how to deal with these uncertainties, one possibility is the use of quantified mixed-integer linear programs.Quantified mixed-integer linear programs are mixed integer linear programs with variables being either existentially or universally quantified. They can be interpreted as two-person zero- sum games between an existential and a universal player on the one side, or multistage optimization problems under uncertainty on the other side. Solutions of quantified programs are so called winning strategies for the existential player that specify how to react on moves of the universal player – certain fixations of universally quantified variables – to certainly win the game.Long-term goal of our efforts is the development of a tool for solving quantified mixed-integer linear programs and its presentation to the the public, just in the spirit of Cplex, Gurobi or Scip. In the pursuit of this objective, we develop, refine and substantiate solution procedures for the mighty modeling tool of quantified mixed-integer linear programs, in order to apply it for practice relevant tasks. One step in this direction was to publish the solver Yasol, as far as it exists already. We hope and expect that the results of this project will have far-reaching impact for research, as well as for practical optimization applications. As a further significant modeling extension, we will allow the active interference of the uncertainty set.