MOMIP: Multi-objective (mixed) integer programming

Wir leben in einer Welt voller Kompromisse und oft wissen wir relativ wenig über sie. In fast allen Problemsituationen ist es schwierig ein einziges Ziel zu definieren, das erreicht werden soll, im Besonderen wenn mehr als ein Entscheidungsträger oder mehrere Interessengruppen involviert sind. Daher besitzen fast alle praktischen Problemstellungen unterschiedliche, oft widersprüchliche Ziele. Prominente Beispiele sind Umweltschutz versus Kosten oder Kundenzufriedenheit versus Profit. Unsere Forschungsschwerpunkte sind in den Bereichen Transport, Logistik und Supply Chain Management verankert und viele Probleme aus diesem Bereich können als gemischtganzzahlige (oder mixed integer) lineare Programme modelliert werden. Dies bedeutet, dass relativ einfache, lineare Beziehungen zwischen Inputgrößen und Entscheidungsvariablen bestehen und manche Variablen nur ganzzahlige Werte annehmen können (z.B. die Entscheidung ob ein Verteilerzentrum gebaut wird oder nicht kann nur entweder 1 (ja) oder 0 (nein) sein, aber nicht 0,2). Obwohl diese Problemstellungen oft vergleichsweise einfach formuliert werden können, sind sie häufig sehr schwierig zu lösen. Wenn widersprüchliche Ziele gleichzeitig verfolgt werden, ist es zusätzlich meistens nicht möglich eine einzige, beste Lösung zu identifizieren, sondern es existiert eine Menge von Lösungen, die besser sind als die übrigen Lösungen, aber untereinander nicht vergleichbar. Jede dieser Lösungen stellt einen möglichen Kompromiss zwischen den verfolgten Zielen dar. Die Berechnung dieser optimalen Menge von Kompromisslösungen ist eine komplexe Aufgabe. Alle existierenden exakten Verfahren sind für gemischtganzzahlige Probleme nur begrenzt einsetzbar. Entweder können sie nur Probleme mit maximal zwei Zielen lösen oder sie können nicht die komplette Menge von Kompromisslösungen darstellen. Kern des Projekts ist die Entwicklung von effizienten generischen Algorithmen, die das Prinzip des Branch-and-Bound so anwenden, dass der multikriterielle Charakter der Problemstellungen genützt wird, und dadurch diese Lücke für gemischtganzzahlige Probleme mit bis zu drei Zielen zu schließen. Um die Anwendung unserer Verfahren zu illustrieren, planen wir sie zur Lösung von praktischen Problemstellungen aus dem nachhaltigen Supply Chain Management, der Distributionsplanung von Hilfsgütern und der emissionsbewussten Tourenplanung einzusetzen. Entscheidungsträger erhalten so zusätzliche Informationen über das Kompromissverhältnis der verschiedenen Ziele, die Möglichkeit unterschiedliche Lösungen zu vergleichen und schließlich aus der Menge von optimalen Kompromisslösungen die in der jeweiligen Situation passende zu wählen.

In der Praxis ist es häufig nicht möglich, sich auf einziges Ziel festzulegen, das optimiert werden soll, insbesondere dann, wenn mehrere Entscheidungsträger oder Stakeholder involviert sind. Prominente Beispiele sind Umweltschutz versus Kosten oder Kundenzufriedenheit versus Profit. In den Bereichen Transport, Logistik, Produktion und Supply Chain Management können viele wichtige praktische Optimierungsprobleme als ganzzahlige oder gemischtganzzahlige (mixed integer) lineare Programme modelliert werden. Während für Problemstellungen mit nur einer Zielfunktion ein ganzes Bündel an ausgereiften kommerziellen Softwareprodukten und auch Open-Source-Tools existiert, ist dies für Probleme mit mehreren Zielen - trotz ihrer hohen praktischen Relevanz - bisher nicht der Fall. Wenn widersprüchliche Ziele gleichzeitig verfolgt werden, existiert normalerweise nicht eine einzige Lösung, die alle Ziele gleichzeitig optimiert, sondern es existiert eine Menge von Lösungen, die "besser" sind als die übrigen Lösungen, aber untereinander nicht vergleichbar. Jede dieser Lösungen stellt einen möglichen Kompromiss zwischen den verfolgten Zielen dar. Die Berechnung dieser optimalen Menge von Kompromisslösungen ist eine komplexe Aufgabe, insbesondere dann, wenn mehr als zwei Ziele oder sowohl ganzzahlige als auch kontinuierliche Entscheidungsvariablen zur Modellierung der Problemstellung nötig sind. Dieses Projekt war der Entwicklung von generischen Branch-and-Bound-Algorithmen gewidmet, die das bewiesenermaßen optimale Set an Kompromisslösungen für Probleme mit mehr als zwei Zielen und ganzzahligen Entscheidungsvariablen sowie für Probleme mit zwei Zielen und gemischten - ganzzahligen und kontinuierlichen - Entscheidungsvariablen berechnen können. Branch-and-Bound-Algorithmen sind die Basis fast aller erfolgreichen Tools, wenn nur ein Ziel verfolgt wird. Sie bauen eine Baumstruktur auf, wobei in jeder Iteration der Lösungsraum in immer kleinere Suchräume unterteilt wird, für die man jeweils einen sognannten Bound berechnet. Dieser gibt an, wie gut im besten Fall eine Lösung im jeweiligen Suchraum sein kann. Dadurch können nicht interessante Teile des Suchraums identifiziert und entfernt werden. Im Bereich der Mehrzieloptimierung ist dieser Bound nicht ein einziger Wert, sondern eine Menge, ein sogenanntes Bound Set. Im vorliegenden Projekt wurden neue effiziente Algorithmen, unter anderem, für die Berechnung von Bound Sets, für das Erstellen von Bündeln an gültigen Lösungen ausgehend von Bound Sets und für das frühzeitigen Erkennen von uninteressanten Suchräumen sowie für das Verkleinern von Suchräumen entwickelt. Dem Ziel eines effizienten generischen Tools für jene bedeutende Klasse von Mehrzieloptimierungsproblemen, die als gemischtganzzahlige lineare Programme modelliert werden können, konnte so einen großen Schritt nähergekommen werden. Darüber hinaus wurden im Rahmen des Projekts auch maßgeschneiderte Optimierungsalgorithmen für Anwendungen in der Standortplanung unter Unsicherheit im Bereich humanitäre Logistik, im Design von Lieferkettennetzwerken und im Car-Sharing entwickelt, die noch zusätzlich die Relevanz von Methoden, die mehrere Ziele gleichzeitig optimieren können, unterstreichen.