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

用于求解量化混合整数线性程序的高级算法和启发式方法

• 批准号: 399489083
• 负责人: Professor Dr. Ulf Lorenz
• 金额: --
• 依托单位: Lehrstuhl für Technologiemanagement
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2018
• 资助国家: 德国
• 起止时间: 2017-12-31 至 2020-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/399489083?language=en
• 关键词: Advanced; algorithms; heuristics; solving; quantified

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.

传统上，它是假设优化问题的输入是预定义的，众所周知的规划时间。然而，在规划过程中考虑到不确定性是一项重要的资产。在文献中有各种各样的方法来处理这些不确定性，一种可能性是使用量化的混合整数线性规划，量化的混合整数线性规划是变量存在量化或泛量化的混合整数线性规划。它们可以被解释为一方是存在者和普遍参与者之间的两人零和博弈，另一方是不确定性下的多阶段优化问题。量化程序的解决方案是所谓的获胜策略的存在球员，指定如何对通用球员的移动反应-普遍量化变量的某些固定-肯定赢得比赛。我们努力的长期目标是开发一个工具，用于解决量化的混合整数线性规划和它的介绍给公众，只是在Cplex，Guesthouse或Scip的精神。在追求这一目标，我们开发，完善和充实的量化混合整数线性规划的强大的建模工具的解决方案程序，以便将其应用于实践相关的任务。朝着这个方向迈出的一步是发布求解器Yasol，只要它已经存在。我们希望并期望该项目的结果将对研究以及实际优化应用产生深远的影响。作为进一步的重要建模扩展，我们将允许不确定性集的主动干扰。