Mathematik im Alltag Das optimieren wir jetzt mal

Zu viele Konferenzteilnehmer pro Raum? Zu weite Wege zwischen den Veranstaltungsorten? Rechenkünstler lösen solche Probleme mittels mathematischer Optimierung. Wie man den Alltag damit leichter machen kann, demonstriert gerade eine Fachkonferenz in Berlin.

dapd

Von


Berlin im August 2012. Die Sonne brennt unerbittlich und bringt selbst gestandene Mathematiker ins Grübeln. Wie bewege ich mich am besten über das Gelände der TU Berlin, um möglichst wenig zu schwitzen? Gehe ich besser langsam, bin dabei aber länger in der sengenden Hitze unterwegs? Oder lieber schweißtreibend schnell, um das kühle Uni-Hauptgebäude früher zu erreichen?

Es sind Probleme wie diese, die 2000 Forscher aus aller Welt auf dem 21. Kongress für mathematische Optimierung (ISMP 2012) in Berlin beschäftigten. Was die Hitze betrifft, haben einige Teilnehmer zumindest schon mal ihre Kleidung optimiert: Sie kamen in kurzen Hosen und T-Shirt.

Formfragen waren nebensächlich, was zählte, sind clevere Lösungsansätze - nicht nur im Alltag, sondern auch bei der Arbeit der Mathematiker, die Leerlaufzeiten von Maschinen oder Computerchips ebenso minimieren wie den Verschnitt edler Stoffe in der Textilbranche.

"Die Welt wird immer komplexer", sagt Martin Skutella von der TU Berlin, Cheforganisator der Tagung. "Und die Probleme, die wir lösen müssen, werden immer schwieriger." Mathematische Optimierung - das heißt mittlerweile fast immer, dass der Computer hilft, eine möglichst gute Lösung zu finden.

Beispiel öffentlicher Nahverkehr: Den Fahrplan der U-Bahn in Berlin haben TU-Mathematiker schon vor Jahren so optimiert, dass Fahrgäste abends und nachts beim Umsteigen von Linie zu Linie möglichst wenig warten müssen - natürlich mit Softwarehilfe. Skutella und seine Kollegen aber wollen mehr: "Wir könnten auch das gesamte System in Berlin optimieren - also das Zusammenspiel von U-Bahn, S-Bahn, Straßenbahn und Bussen." Doch dieses Problem sei deutlich komplexer als die zehn U-Bahn-Linien für sich. Selbst Supercomputer stoßen da an ihre Grenzen - noch.

Ein Paradebeispiel für mathematische Optimierung ist der Kongress an der TU Berlin selbst. Mathematiker vom Berliner Zuse-Institut haben das Tagungsprogramm nämlich so gestaltet, dass die Teilnehmer kurze Wege haben und die Veranstaltungsräume möglichst immer groß genug für alle Interessenten sind. Keine leichte Aufgabe: 1700 Einzelvorträge mussten die Forscher auf fünf Tage verteilen, 40 Sessions finden von Montag bis Freitag parallel statt.

Ich kann nur am Mittwoch!

Erschwerend hinzu kamen Hunderte Nebenbedingungen - man könnte auch sagen: Sonderwünsche. Ein Vortragender hat nur am Mittwochnachmittag Zeit, andere halten mehrere Vorträge in verschiedenen Themengebieten, einige Sessions sollten in einer bestimmten logischen Reihenfolge aufeinander folgen. "Wenn Sie versuchen, das alles mit der Hand zu machen, verlieren Sie ganz schnell die Übersicht", sagt Ralf Borndörfer vom Zuse-Institut Berlin.

Gemeinsam mit seinem Kollegen Alexander Tesch hat der Mathematiker das sogenannte Conference Scheduling Problem mit Optimierungssoftware gelöst. "Wir wollten auch, dass thematisch ähnliche Vorträge möglichst in benachbarten Hörsälen stattfinden, damit man schnell wechseln kann", sagt er. Und nicht zuletzt ging es darum, ein Programm aufzustellen, das an jedem Tag attraktiv ist. Bekannte Redner und populäre Themen sollten also keinesfalls alle auf denselben Tag gelegt werden.

"Wir haben zuerst mit den Daten vom letzten Kongress aus dem Jahr 2009 gespielt", sagt Borndörfer. So wussten die Forscher, welche Themen besonders viele Zuhörer gefunden hatten. Diese Vorträge sollten in Berlin dann in möglichst großen Hörsälen laufen. "Bei der Anmeldung konnten die Teilnehmer zudem drei Sessions angeben, die sie unbedingt besuchen wollen." Dies habe bei der Abschätzung geholfen, mit wie vielen Teilnehmern man bei jeder einzelnen Session rechnen müsse.

Wie häufig bei Optimierungen, vereinfachten die Mathematiker das Problem zunächst rigoros. Statt die konkreten Räumlichkeiten der TU zu berücksichtigten, arbeiteten sie nur mit zwei Raumtypen: großen und kleinen. Über diese verteilte die Software dann die Sessions - unter Berücksichtigung aller Wünsche von Vortragenden und sonstigen Restriktionen. Bei mehreren Durchläufen fand die Software immer wieder denselben Ablaufplan - und mit dem wurde der Kongress dann auch geplant.

Rechenaufwand steigt exponentiell

Der Zeitplan stand damit - nun ging es nur noch darum, die Sessions über die tatsächlich vorhandenen Seminarräume und Hörsäle der TU zu verteilen. "Wir dachten, wir können das mal eben per Hand machen", berichtet Borndörfer. Doch die Raumzuteilung erwies sich als äußerst knifflig. Schließlich sollten thematisch benachbarte Sessions auch nah beieinander stattfinden. Und besonders beliebte Themen in einem großen Hörsaal. Der Kongress nutzt Räume in zwei Gebäuden - und dort auch jeweils auf mehreren Etagen. Auch bei der Raumzuteilung musste schließlich der Computer helfen.

Viel größer als die Optimierungstagung ISMP in Berlin hätte der Kongress allerdings nicht sein dürfen. Das Problem der Kongressplanung ist nämlich ein sogenanntes NP-schweres Problem. Das bedeutet, es gibt wahrscheinlich kein Lösungsverfahren, um es schnell zu lösen. Vielmehr muss man am Computer im schlimmsten Fall alle Optionen durchprobieren. Und der Rechenaufwand dafür steigt exponentiell mit der Anzahl der Variablen.

Um den Rechenaufwand zu begrenzen, nutzen die Forscher Tricks: So versuchen sie, möglichst viele Kongressvarianten in einem frühen Stadium der Berechnung auszuschließen, wenn diese keine optimale Lösung sein können.

Die Optimierung des Tagungsprogramms ist kein isoliertes Problem: Jedes Jahr stehen Schulen bundsweit vor dem Problem, die Stundenpläne so zu gestalten, dass Lehrer und Schüler möglichst wenig Freistunden und kurze Wege haben. Mancher Direktor verteilt Lehrer, Räume und Klassen noch per Hand, doch inzwischen wird auch Software dafür eingesetzt, wenngleich diese nicht so raffiniert arbeitet wie die Lösung der Optimierer aus Berlin.

Ralf Borndörfer und Martin Skutella können nun bewundern, was der Computer berechnet hat. Bis auf eine überfüllte Session am ersten Tag scheint alles zu passen. Und sogar dem heißen Wetter können sie Positives abgewinnen. "Die Stadt Berlin ist bei Sonne und blauem Himmel noch schöner", sagt Skutella. "Das schätzen die vielen internationalen Teilnehmer besonders."

Forum - Diskutieren Sie über diesen Artikel
insgesamt 7 Beiträge
Alle Kommentare öffnen
Seite 1
seldon-x 23.08.2012
1. Raumauslastung
Zitat von sysopdapdZu viele Konferenzteilnehmer pro Raum? Zu weite Wege zwischen den Veranstaltungsorten? Rechenkünstler lösen solche Probleme mittels mathematischer Optimierung. Wie man den Alltag damit leichter machen kann, wird gerade auf einer Fachkonferenz in Berlin demonstriert. http://www.spiegel.de/wissenschaft/mensch/0,1518,851157,00.html
"Für eine Raumauslastung von 90% verantworte ich alles!" ;o) Zwei schräge Vögel (http://de.wikipedia.org/wiki/Zwei_schr%C3%A4ge_V%C3%B6gel)
Stäffelesrutscher 23.08.2012
2.
»Die Sonne brennt unerbittlich und bringt selbst gestandene Mathematiker ins Grübeln. Wie bewege ich mich am besten über das Gelände der TU Berlin, um möglichst wenig zu schwitzen? Gehe ich besser langsam, bin dabei aber länger in der sengenden Hitze unterwegs? Oder lieber schweißtreibend schnell, um das kühle Uni-Hauptgebäude früher zu erreichen?« Garantiert supotimal wäre es, in der prallen Sonne zu grübeln oder ein Computerprogramm zu schreiben. ;-)
querulant_99 23.08.2012
3.
Zitat von Stäffelesrutscher»Die Sonne brennt unerbittlich und bringt selbst gestandene Mathematiker ins Grübeln. Wie bewege ich mich am besten über das Gelände der TU Berlin, um möglichst wenig zu schwitzen? Gehe ich besser langsam, bin dabei aber länger in der sengenden Hitze unterwegs? Oder lieber schweißtreibend schnell, um das kühle Uni-Hauptgebäude früher zu erreichen?« Garantiert supotimal wäre es, in der prallen Sonne zu grübeln oder ein Computerprogramm zu schreiben. ;-)
Mathematiker sind auch nicht mehr das, was sie einmal waren. Ich würde einfach den Hausmeister nach einem unterirdischen Verbindungsgang fragen.
irobot2 24.08.2012
4. Das leidige Thema...
Mathematik scheint für viele Menschen ein Schreckgespennst zu sein. Das ist schade, ist doch Mathematik nicht nur ein sehr spannendes und unterhaltsames Thema, Mathematik ist auch ein hervorragendes Mittel, um Dinge vorherzusagen oder zu gestalten: http://www.der-prozess.de/Mathebuch.htm Macht Spass, darin zu lesen. Grüsse Ein Mathematik-Begeisterter ----------------------------------------------- In der Mathematik gibt es keine Autoritäten. Das einzige Argument für die Wahrheit ist der Beweis. K. Urbanik
Jens Schuetz 24.08.2012
5. Danke
Zitat von seldon-x"Für eine Raumauslastung von 90% verantworte ich alles!" ;o) Zwei schräge Vögel (http://de.wikipedia.org/wiki/Zwei_schr%C3%A4ge_V%C3%B6gel)
Cooler Film. Hab ihn mir gerade angesehen. Danke, ohne sie haette ich von dem nie erfahren.
Alle Kommentare öffnen
Seite 1

© SPIEGEL ONLINE 2012
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH


TOP
Die Homepage wurde aktualisiert. Jetzt aufrufen.
Hinweis nicht mehr anzeigen.