1 Electoral Districts in Elections to the German Bundestag

every four years. The 299 electoral districts play an important role in those elections. In fact, the voters of each district elect one representative into parliament ensuring that each part of the country is represented. These elected representatives make up half of the members of the Bundestag. The allocation of electoral districts needs regular updates due to an ever-changing population distribution and is subject to a variety of legal requirements as listed in the following. In order to comply with the principle of electoral equality as anchored in the German constitution, the differences in population between the districts have to be preferably small. The law defines a tolerance limit, saying that the amount of de-viation from the average district population should not exceed 15%. Moreover, an amount of deviation beyond 25 % is illegal. Every district should be a contiguous area and it is prefered that its allocation aligns with existing administrative bound-aries. In addition to that, the law demands that the districts strictly comply with the borders of the German federal states. The law specifies that the Sainte-Laguë method [7] has to be used to distribute the 299 districts among the 16 states. The electoral districts ought to be visually compact counteracting the suspicion of ap-plying Gerrymandering [6, 9, 11]. In the context of setting electoral districts, Ger-rymandering is a practice that attempts to create an advantage or disadvantage for a certain political party or candidate by manipulating district boundaries. In this contribution, which is an extended abstract of the author’s master’s the-sis, the problem of dividing a country into electoral districts is defined as a multi-criteria graph partition problem. To solve this regularly current practical problem, an optimization-based multi-stage heuristic is introduced and successfully applie