This Lab has an upper limit on the number of participants. If you want to participate, please write an informal application e-mail to Daniel Faber (dfaber@uni-bonn.de) until the 16th of March. Please mention your experiences with graph algorithms and linear/integer optimization and a list of the algorithmics-related courses you attended.

In this lab, we will look at algorithms for political districting problems. The task is to partition a state into a predefined number of valid electoral districts. In almost all cases, electoral districts are by law required to be spatial contiguous as well as similar in population size. Additionally, an important concern in political districting is the prevention of gerrymandering, which is why districts should also be geometrically compact.

All these requirements make the problem computationally challenging, and in fact almost all relevant variants of political districting are NP-hard. Political districting problems are strongly related to connected graph partitioning problems, a class of problems that also have a wide range of applications in other areas.

In this Lab, we will mainly focus on high-quality heuristics as well as ILP-based exact optimization for political districting problems. We will look at various heuristics, which may include heuristics based on local search, discrete voronoi diagrams or divide-and-conquer schemes. On the ILP side, we will look at different models, such as compact flow models, branch-and-cut algorithms and shortest-path-tree ILPs.

If time permits, we may also look at further topics such as prefixing variables for ILPs or different problem variants.

The algorithms in this lab will be implemented in C++.

Students are expected to have a solid foundation in graph algorithms and programming in C++. Knowledge about Integer Optimization will be helpful.

At the end of the semester, you will need to hold a presentation and hand in a lab report on your topic, algorithm(s) and implementation. Both will be graded.

Surveys:

• Political Districting

ILP models:

• Imposing Contiguity Constraints in Political Districting Models
• Political districting to minimize cut edges

Flip and ReCom heuristics:

• Redistricting optimization with recombination: A local search case study

Multi-Level partitioning

• Multi-Objective Optimization for Politically Fair Districting: A Scalable Multilevel Approach