Decomposition algorithms for multistage optimization problem

• Applicant: Professor Dr. Marco Lübbecke
• Subject Area: Traffic and Transport Systems, Intelligent and Automated Traffic ; Mathematics
• Term: from 2015 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 238487308

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.

• DFG Programme: Research Units
• Subproject of: FOR 2083: Integrated Planning for Public Transportation