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

点击翻译按钮获取中文摘要

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.