Mathematik Die beste Wahl

Ein Optimierungsproblem umfasst die Aufgabe, unter allen zulässigen Lösungen eine beste zu finden. Zulässig ist eine Lösung, wenn sie alle strikt zu erfüllenden Bedingungen einhält. So muss laut Gesetz ein Wahl­kreis aus einem zusammen­hängenden Gebiet bestehen und soll sich an bestehenden Verwaltungs­einheiten wie zum Beispiel Land­kreisen, Groß­städten und Gemeinden orientieren. Die Menschen eines Wahl­kreises sollen also nicht nur eine numerische Größe sein, sondern auch geografisch „ein zusammen­gehöriges und abgerundetes Ganzes“ bilden, wie das Bundes­verfassungs­gericht unterstrich. Außer­dem sollen in jedem Wahl­kreis mindestens 185.000 und höchstens 305.000 Deutsche leben.

Alle Lösungen, die diese Bedingungen erfüllen, sind zulässig. Welche nun die beste ist, bestimmen die Optimierungs­kriterien. Diese bewerten jede zulässige Lösung, dies erstellt eine Rang­liste. An der Spitze des Rankings findet man eine Optimal­lösung. Eine solche zu ermitteln, ist das Ziel der Optimierung.

Unter diesen Voraussetzungen wollten wir nun eine optimale Einteilung der Wahl­kreise für die Bundes­tags­wahl berechnen – natürlich optimal nach Recht und Gesetz und nicht zur Verbesserung einer Wahl­chance. Im ersten Schritt galt es, die im Wahl­gesetz genannten Vorgaben in die Sprache der Mathematik zu überführen. Rein mathematisch kann dieses Gebiets­­planungs­problem als eine Zerlegungs­aufgabe einer abstrakten Struktur aus der „Graphen­theorie“ interpretiert werden: Ein Graph repräsentiert eine Menge von Objekten und bestehende Verbindungen zwischen diesen. Die Objekte werden als Knoten bezeichnet, Verbindungen ­zwischen je zwei Knoten werden Kanten genannt. Unseren Graphen entwickeln wir ausgehend von einer Land­karte Deutschlands. Dies kann man grafisch veranschaulichen. Alle Städte werden in ihren Zentren mit einem Punkt markiert, das sind unsere Knoten des Graphen. Außerdem verbinden wir zwei Knoten mit einer Kante in Form einer geraden Linie, falls die zwei zugehörigen Gebiete benachbart sind. Nun lautet die abstrahierte Aufgaben­stellung: Entferne Kanten des Graphen und zerlege so den Graphen in 299 Teil­graphen. Jeder Teil­graph wird anhand der Land­karte als einer der 299 Wahl­kreise interpretiert.

Eine große, in der Forschung bisher unberücksichtigte Heraus­forderung hierbei war die Orientierung der Wahl­kreise an bestehenden administrativen Grenzen. Um diese zu meistern, war Knobel­arbeit angesagt. Wir skizzierten immer wieder neue Ideen und kon­struierten Variablen und Gleichungen, mit deren Hilfe wir am Ende die Kriterien aus dem Gesetz in ein mathematisches Modell aus Entscheidungs­variablen, Nebenbedingungen und einer Ziel­funktion über­führen konnten.

Im nächsten Schritt galt es, ein Verfahren zu ent­wickeln, das eine optimale Wahl­kreis­einteilung identi­fiziert, also unser aufgestelltes Optimierungs­problem löst. Auf den ersten Blick könnte man alle möglichen Graph­zerlegungen der Reihe nach durch­gehen, auf Zulässigkeit prüfen und auf diese Weise Stück für Stück eine Rangliste erstellen. Doch das ist selbst mit den leistungs­stärksten Computern un­möglich, weil es für die Zerlegung des Graphen in Teil­graphen unvorstellbar viele Kombinationen gibt – nämlich mehr, als es Atome im Universum gibt. Und das sind immerhin etwa 10⁸⁵ Stück.

Bei einer derartigen kombinatorischen Explosion kann die „Theorie der gemischt-ganz­zahligen linearen Optimierung“ helfen. Bei dieser algorithmischen Suche nach einer Optimal­lösung wird der Lösungs­raum abschnitts­weise durch­forstet. Dieser Raum umfasst alle durch das mathematische Modell beschriebenen Lösungen. Das Geheimnis: Es können Schritt für Schritt Teile des Lösungs­raumes ausgeschlossen werden, ohne die enthaltenen Lösungen im Einzelnen anschauen zu müssen. Vor Betreten eines neuen Teil­raumes kann abgeschätzt werden, wie gut eine beste Lösung in diesem Abschnitt sein kann. Hat der Algorithmus zuvor, in einem anderen Abschnitt, schon eine bessere Lösung gefunden, kann dieser Teil­raum ignoriert werden. Schluss­endlich müssen auf diese Weise nur vergleichs­weise wenige zulässige Lösungen genauer betrachtet werden.

Die Erkenntnis unserer Arbeit: Die rechtlichen Krite­rien lassen sich mithilfe unseres Modells besser ­erfüllen, als es bis jetzt der Fall war. In der Praxis werden Wahlkreise für die Bundes­tags­wahl bisher per Hand eingeteilt, wobei ausgeglichenen Bevölkerungs­zahlen zwischen den Wahl­kreisen eine eher unter­­geordnete Rolle beigemessen wird. Die teilweise hohen Abweichungen wurden sogar schon von inter­natio­na­len Wahl­beobachterinnen und -beobachtern der Orga­nisation für Sicherheit und Zusammen­arbeit in Europa (OSZE) kritisiert. Den Entscheidungs­trägerinnen und -trägern im Deutschen Bundes­tag ist indes wichtiger, dass sich Wahlkreise an Verwaltungs­grenzen von Land­kreisen, Groß­städten und Ähnliches orientieren. Dieses Ziel erfüllen die gegen­wärtigen Wahl­-kreise sehr gut. Unsere Forschung zeigt aber, dass sich darüber hinaus auch das Ziel ähnlich bevölkerter Wahlkreise erreichen lässt, und zwar ohne Qualitäts­einbußen im Ziel der Verwaltungs­grenzen hinnehmen zu müssen. Beide Bewertungs­kriterien können ­gleich­zeitig sehr gut erfüllt werden.

Dass die derzeit geltenden Wahlkreise keine Optimal­lösung bilden, ist natürlich nicht Ausdruck gezielter Manipulationen, sondern ergibt sich aus der Komplexität des Problems, das per Hand schlichtweg nicht optimal lösbar ist. Der Bundes­wahl­leiter setzt daher gerade jetzt auf unsere Ergebnisse. Denn es gilt, ein akutes Problem zu bewältigen: die Größe des Bundes­tages. Der wächst von Wahl zu Wahl und muss mittlerweile 709 Abgeordnetinnen und Abgeordneten Platz bieten – weit mehr als die im Gesetz genannte Soll-Mitglieder­zahl von 598. Im Auftrag des Wahlleiters haben wir daher auf der Basis unserer Forschung Karten mit 270, 250, 200 und 125 möglichst fairen Wahl­kreisen erstellt. „Die optimierungs­basierten Wahl­kreis­einteilungen sind“, so Bundes­wahl­leiter Georg Thiel, „ein essenzieller Bestandteil der Bemühungen um eine Wahl­rechts­reform.“

Von Politikerinnen und Politikern werden unsere Wahl­kreise hingegen teils kritisch begutachtet. Immerhin ändert eine große Reform der Wahl­kreis­grenzen deren politische Heimat und womöglich ihre Chancen auf eine Wieder­wahl. Im Fall einer Reduktion der Wahl­kreis­anzahl kann ein Argument unserer Arbeit allerdings schwer übertroffen werden: Die Wahl­kreise werden objektiv und nur anhand der Vorgaben aus Recht und Gesetz mathematisch optimal berechnet sein.