Die Kunst guter Modellierung

In diesem Kapitel wird die Modellierung verschiedener spezieller Konstrukte vorgestellt, die in praktischen Problemen auftreten. Dazu zählen logische Relationen, die sich mit Hilfe von Binärvariablen beschreiben lassen, aber auch bestimmte nichtlineare Strukturen, die in gemischt-ganzzahlige Formulierungen transformiert werden können. Zudem werden Methoden behandelt, mit denen sich die Rechenzeit ganzzahliger Probleme erheblich reduzieren lässt. Hierzu zählen eine gute Modellbildung, die Verwendung spezieller Verzweigungstechniken und eine Kontrolle der Branch&Bound-Strategien. Während sich bei der linearen Programmierung die Modellbildung zwar auch positiv auf die Rechenzeit auswirkt, ist bei den meisten praktischen gemischt-ganzzahligen Problemen eine gute Modellbildung für die Lösung geradezu notwendig. Bei MILP-Problemen kann die Qualität und Güte eines Modells anhand der LP-Relaxierung und der konvexen Hülle entschieden werden. Neben einigen Aspekten effizienter Modellbildung, die vom Modellentwickler beeinflusst werden können, werden in diesem Kapitel automatische Reformulierungsverfahren für Optimierungsprobleme mit binären Variablen und

Preprocessing

-Techniken behandelt, die zu schärferen Modellformulierungen führen.