312440 Dynamic Programming Models in Combinatorial Optimization (S) (WiSe 2022/2023)

The goal of this course is to explore various ways in which Dynamic Programming (DP) models can be used to solve Combinatorial Optimization (CO) problems. The most obvious use of DP in CO is to view DP as an algorithmic framework or a family of (exact) algorithmic schemes that, by exploiting the recursive structure of a given CO problem, avoids redundant computations that would arise in naive enumeration-based approaches. In order to apply such a DP algorithm to a CO problem, however, we need a problem representation that involves aspects such as states, actions/decisions/controls and state transitions. In this course, we refer to such a repesentation as a DP model.

Throughout the course, we will see that DP models

- can not only be solved by in exact DP algorithms, but can also be used as the starting point for designing heuristic solution approaches and approximation algorithms as well as for employing Reinforcement Learning approaches
- form the basis of using so-called Decision Diagrams (DDs) for solving CO problems. In particular, DDs provide a generic way of obtaining (combinatorial) relaxations of CO problems that can be used to derive exact solution approaches such as Branch-and-Bound schemes.
- can be used in the context Mixed-Integer Linear Programming (MILP) in order to obtain formulations that in some cases can be solved much more efficiently than standard "compact" MILP formulations and can often be a relatively easy-to-implement alternative to highly complex decompostion approaches such as Branch-and-Price.

A key objective of the course is to provide you with a set of models and solution approaches that you may at some point use in your own research. Therefore, the majority of the models and approaches discussed in the course will not only be discussed in theory, but also be implemented in Python.