Decomposition algorithms for multistage optimization problem

多阶段优化问题的分解算法

• 批准号: 260447518
• 负责人: Professor Dr. Marco Lübbecke
• 金额: --
• 依托单位: Lehrstuhl für Operations Research (OR)
• 依托单位国家: 德国
• 项目类别: Research Units
• 财政年份: 2015
• 资助国家: 德国
• 起止时间: 2014-12-31 至 2019-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/260447518?language=en
• 关键词: Decomposition; algorithms; 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.

多阶段优化问题发生在当最好的可能的决策是在一段时间内，后来的决定取决于早期的。例如，飞行计划的创建，批量问题，或多阶段随机优化。分解算法依赖于整数规划的重新表述，利用潜在的问题结构。这些算法最成功地应用于丰富的实际情况下，特别是在规划阶段的公共交通规划过程。最近的研究结果表明，多个阶段本身就构成了一个可利用的结构。一个普遍适用的实施这些结果需要基础研究，这是这个项目的主题。这个项目的总体目标是调查的结构在多级优化问题，他们在建模中使用这样的问题，通过整数规划，以及开发和实验评估的分解算法的精确解。通常较长的规划期会带来数据不确定性和误差传播;因此，鲁棒性问题是一个特别令人关注的问题。在这个项目中开发的模型和方法的原型用例是公共交通的规划过程，包括线路规划，调度，车辆和机组人员调度。以此来论证本课题所研究的理论和算法的实用性。