Combinatorial Optimization & Graph Algorithms

Computational Integer Programming

Integer programming has a fascinating theory. On top of that, when it comes to actually solving large scale integer programs to optimality, usually a lot of mathematical engineering is necessary. This may include sophisticated relaxation techniques, cutting plane algorithms, problem decomposition, the use of problem adequate heuristics, and many more.

The development and implementation of models and algorithms is the world of computational (mixed) integer programming. In our research we aim at

• solving large scale (industrial) problem instances optimally or near optimally
• developing efficient algorithms for the many subproblems arising at different levels of an overall solution approach
• using integer programs to detect, observe (and possibly prove) phenomena in areas in which integer programming is not a traditional or obvious idea. One such area is optimization in computational geometry.

Methodology

• Column generation for linear and integer programs
• Lagrangian relaxation
• Polyhedral theory and cutting planes
• Linear programming based approximation algorithms

Applications

• Rail car shunting
• Line planning
• Route guidance
• Traffic Signal Optimization