Decomposition algorithms for multistage optimization problem

当要在一段时间内做出可能的最佳决策时，就会出现多阶段优化问题，而以后的决策取决于前面的决策。例如创建飞行计划、批量问题或多阶段随机优化。分解算法依赖于对整数规划的重新表述，利用潜在的问题结构。这些算法最成功地应用于大量的实际情况，特别是在公共交通规划过程的规划阶段。最近的研究结果表明，多个阶段本身构成了一个可开发的结构。这些结果的普遍应用需要基础研究，这是本项目的主题。本项目的总体目标是研究多阶段优化问题中的结构，它们在整数规划建模中的应用，以及为其精确解开发和实验评估分解算法。通常较长的规划范围会带来数据不确定性和错误传播；因此，稳健性问题是一个特别令人担忧的问题。本项目中要开发的模型和方法的典型用例是公共交通中的计划过程，包括线路计划、时刻表以及车辆和乘务调度。用来验证本课题研究的理论和算法的实用性。

Multistage optimization problems occur when best possible decisions are to be taken over the course of time, and later decisions depend on earlier ones. Examples are the creation of flight plans, lot sizing problems, or multistage stochastic optimization.Decomposition algorithms rely on a reformulation of integer programs, exploiting underlying problem structure. These algorithms are most successfully applied to a wealth of practical situations, in particular in planning stages of the public transportation planning process. Recent research results suggest that multiple stages themselves constitute an exploitable structure. A generally applicable implementation of these results requires fundamental research which is the topic of this project.Overall goal of this project is the investigation of structures in multistage optimization problems, their use in modeling such problems via integer programs, and the development and experimental evaluation of decomposition algorithms for their exact solution. The typically long planning horizons entail data uncertainties and error propagation; thus robustness issues are a particular concern. Prototypical use case for the models and methods to be developed in this project is the planning process in public transportation, consisting of line planning, timetabling, and vehicle and crew scheduling. This is used to demonstrate the practicability of theory and algorithms resulting from the research in this project.