Thema der Dissertation:
Optimal Graph Coverings with Connected Subgraphs Thema der Disputation:
Mathematical Models for Districting Problems
Optimal Graph Coverings with Connected Subgraphs Thema der Disputation:
Mathematical Models for Districting Problems
Abstract: Districting problems are concerned with dividing a given area into a number of districts that are contiguous, of similar ``size'', and usually ``round-shaped''. Formally, the problem is modeled as a graph partitioning problem with according constraints on the covering subgraphs. In this talk, we will follow this modeling process and present two integer programming formulations for districting.
While one model is compact and assigns each vertex to a subgraph, the other model leads to a column generation approach where promising subgraphs for the partitioning are generated dynamically. We will dive into the pricing problem, which has strong relations to the Maximum Weight Connected Subgraph Problem, and explore preprocessing techniques and LP strengthening cuts that facilitate this pricing. Finally, we show the strength of this model by employing it to districting instances from the literature.
While one model is compact and assigns each vertex to a subgraph, the other model leads to a column generation approach where promising subgraphs for the partitioning are generated dynamically. We will dive into the pricing problem, which has strong relations to the Maximum Weight Connected Subgraph Problem, and explore preprocessing techniques and LP strengthening cuts that facilitate this pricing. Finally, we show the strength of this model by employing it to districting instances from the literature.
Zeit & Ort
29.03.2023 | 10:15
Seminarraum 031
(Fachbereich Mathematik und Informatik, Arnimallee 6, 14195 Berlin)