![](https://csdnimg.cn/release/download_crawler_static/18077606/bga.jpg)
3 LÖSUNG
BILP zu den NP-schweren Problemen gehören ([7], Seite 3 5) und daher nicht effizient
lösbar sind. Im Kapitel Aussicht auf Seite 41 werden wir das nochmal ansprechen, da die
Annahme, Teilbäume seien schneller zu lösen als der entsprechende ganze Ba um, nicht
zwingend richtig ist. Der Branch-and-Bound-Algorithmus kann auch schlimmstenfalls so
lange bei 250 Projekten brauchen, wie die Erde alt ist.
Eine Erweiterung des Branch-and-Bound ist der Bra nch-and-Cut-Algorithmus. Beim
Branch-and-Cut werden ebenfalls obere Grenzen betrachtet, allerdings werden die Zwei-
ge, an denen die Teilbäume hängen, nicht durch ein Vorbelegung von Projekten, sondern
durch das Hinzufügen von Schnittebenen (engl.: cutting planes) gebildet. Es handelt sich
dabei um zusätzlich Bedingungen, die mit Hilfe von Heuristiken erzeugt werden
4
. Das Ge-
biet der Heuristiken reicht sehr weit. In einer sehr ausführlichen Arbeit [4] von 2011 wird
deutlich, dass nicht zwingend eine Heuristik optimal ist, um zusätzliche Bedingungen als
Schnittebenen zu erzeugen. So werden häufig mehrere Heuristiken parallel angewendet,
die dann
5
durch Meta-Heuristiken [10] ausgewertet werden. Meta-Heuristiken entscheiden,
welche Heuristik zur Laufzeit aktuell am besten den Lösungsraum einschränkt, und weißt
dieser Heuristik z.B. mehr CPU-Ressourcen zu. In der glpk-Dokumentation wird auch
davon gesprochen, dass die in glpk implementierte Heuristik die hinzugefügten Schnit-
tebenen bewertet und ggf. wieder entfernt. Heuristiken suchen z.B. möglichst schnell eine
Lösung, die alle Bedingungen erfüllt, und nehmen diese als untere Grenze, oder sie bilden
das duale Problem, welches durch eine Transponierung der Matrix aus Bedingungen und
Zielfunktion ein Minimierungs-Problem macht. Eine gültige Lösung des dualen Problems
(Minimierung der Budgets) stellt automatisch eine obere Grenzen des ursprünglichen pri-
malen Problems (Maximierung des Gewinns) dar
6
. Auf diese Weise lässt sich auch eine
obere Grenze finden, die als neue Bedingung hinzugefügt wird.
3.1 glpk
Das GNU Linear Programming Kit – kurz: glpk – bietet eine Vielzahl von Routinen und
Konfigurations-Möglichkeiten, um eine breite Palette unterschiedlicher Probleme der LP
zu lösen, deren Lösungsverlauf zu b eobachten und in die zugrunde liegenden Algorith-
men einzugreifen. glpk kann gleichzeitig mit jedem Variablentyp (binär, integer, reell)
in Zielfunktion und Bedingungen umgehen. Das wird auch allgemein als Mixed Integer
Linear Programming (MILP oder kurz: MIP) genannt. Zu Anfang hatten wir die Über-
legung, in den Open-Source-Code von glpk direkt ein zu greifen, um eine Parallelisierung
auf mehrere Kerne (multithreading) und später eine Verteilung im Netzwerk zu ermög-
lichen. Als Vorlage für diese Idee hatten wir ein Patch für ein glpk-Plugin [13], welches
2010 von der NASA entwickelt wurde, in Augenschein genommen. Dieses Patch sollte
eine Multithreaded-Fähigkeit von glpk erlauben. Es war jedoch für eine deutlich ältere
Version von glpk gedacht, die in keinster Weise mit der aktuellen Version 4.55 aus dem
Jahr 2014 vergleichbar ist. Daher entschieden wir uns statt mehrere Threads mehrere
Prozesse auf einem Rechner laufen zu lassen. Für die Verteilung der Rechenleistung auf
die Kerne ist somit das Scheduling des Betriebssystems zuständig. Außerdem würde ein
4
Das Simplex-Verfahren ermöglicht das Hinzufügen von weiteren Bedingungen.
5
das macht aber glpk nicht!
6
schwacher Dualitätssatz [1], Seite 146
10