Benutzerspezifische Werkzeuge

Ganzzahlige Optimierung

Viele praktische Probleme sind nur mit ganzzahligen Variablen sinnvoll, da eine Teilbarkeit von Ressourcen oft nicht gegeben ist. Rein-ganzzahlige oder gemischt-ganzzahlige lineare Optimierung unterscheidet sich von der (kontinuierlichen) linearen Optimierung durch zusätzliche Bedingungen, wonach einige oder alle Variablen der Ganzzahligkeitsbedingung unterliegen.

Anwendungen

Oft ist es notwendig, Menschen, Fahrzeuge oder Maschinen in ganzzahligen Mengen bestimmten konkurrierenden Möglichkeiten zuzuordnen. Hier ist es sinnlos, dass die Variablen beliebige reelle Werte annehmen können. Typische Anwendungsfelder sind Transportplanung mit alternativen Routen, Umlauf- und Dienstplanung sowie Supply Chain Management, Personaleinsatzplanung, Investitionsplanung und Projektmanagement.

Durch die Darstellung von Entscheidungen mit Hilfe von binären (0/1-) Indikatorvariablen sind viele Möglichkeiten gegeben, unterschiedliche Entscheidungssituationen in einem gemischt-ganzzahligen Optimierungsmodell darzustellen. Beispiele sind das Anschaffen einer Maschine, Bauen einer Produktionslinie oder Einschalten eines Kraftwerkes.

 

Modelle und Lösungsmethoden

Das (lineare) gemischt-ganzzahlige Optimierungsmodell (Mixed Integer Program, MIP) kann formal dargestellt werden als

          Min cx + hy,

          Ax + Gy <= b

          lx <= x <= ux,

          ly <= y <= uy und ganzzahlig.

wobei x eine nx1-Vektor der kontinuierlichen Entscheidungsvariablen, c ein 1xn-Vektor der Zielfunktionskoeffizienten, y eine px1-Vektor der ganzzahligen Entscheidungsvariablen und h eine 1xp-Vektor der Zielfunktionskoeffizienten ist. A und G sind entsprechende Koeffizientenmatrizen und b die rechte Seite (beispielsweise zur Darstellung von Obergrenzen der Restriktionen). Die Vektoren lx und ly stellen die Untergrenzen sowie ux und uy die Obergrenzen der Variablen dar.

Wenn n=0 ist, handelt es sich um ein reines ganzzahliges Modell (Integer Program, IP). Ein kombinatorisches Optimierungsmodell beinhaltet nur 0/1-Variablen. Die wichtigste Modellklasse in der Praxis sind gemsichte 0/1-Modelle. Eine Vielzahl von Model­lie­rungs­techniken, unter anderem auch für Nichtlinea­ritä­ten und logische Verknüpfungen von Entscheidun­gen über 0-1-Variablen, erlauben es, fast jedes deterministi­sche Entscheidungsproblem in einem MIP-Modell ab­zubilden. Bekannte spezielle IP- oder MIP-Modelle sind u.a. das Knapsack-Modell, das Traveling-Salesman-Problem, das Zuordnungsmodell, Set-Packing- und Set-Covering-Modelle (s. Abb. 1 und [Kallrath 2002]).

 

MIP-Modelle

Abb. 1: Spezielle LP-, MIP- und IP-Modelle (s. [Nemhauser/Wolsey 1999])

 

Im Unterschied zu LP-Modellen gehören IP- und MIP-Modelle bis auf spezielle Ausnahmen ma­thematisch zur Klasse der NP-harten Probleme, für die keine effizienten Algorithmen bekannt sind. Es gibt relativ kleine Modelle, die bereits sehr schwierig zu lösen sind. Weiterhin kann die Art der Modellierung bei IP-Modellen über deren Lösbarkeit entscheiden.

Der wichtigste allgemeine Lösungsalgorithmus ist Branch-and-Bound. Nach dem LP-Preprocessing des IP-Modells wird das zugehörige Anfangs-LP gelöst. Danach erfolgt ein erstes IP-Preprocessing (Supernode Processing), um eine möglichst strenge LP-Relaxation des IP-Modells zu erreichen. Optional kann dann eine Heuristik zur Bestimmung einer ganzzahligen Anfangslösung ausgeführt werden. Danach wird das IP-Modell mit einem Branch-and-Bound- (oder speziell Branch-and-Cut-) Algorithmus optimiert. Dies ist eine Suchmethode, die über Branching-Schritte im Lösungsbaum gesteuert wird, so dass implizit alle Teile des Baumes untersucht werden, um schließlich eine optimale ganzzahlige Lösung zu finden. Im Branch-and-Cut-Verfahren werden im Laufe der Suche zusätzliche Schnittebenen generiert, um eine optimale Lösung schnell zu lokalisieren.

 

Softwaresysteme

Alle Softwaresysteme zur Lösung von IP-Modellen basieren auf Branch-and-Bound/Cut-Algorithmen. Es sind sehr komplexe Softwarepakete, die einen LP-Solver als Unterprogramm aufrufen. Obwohl MIP-Modelle NP-hart sind, können viele große Praxismodelle (nahezu) optimal gelöst werden. Abb. 2 zeigt typischen Ablauf des Lösungsalgorithmus [MOPS 2008].

Optimierungsablauf

 

Der Marktführer bei der Software für MIP ist heute ILOG CPLEX (http://www.ilog.com/products/cplex/. Weitere leistungsfähige Solver sind u.a. XPRESS-MP (http://www.dashoptimization.com/ und MOPS (http://www.mops-optimizer.com/). Beispiele von Open-Source-Codes sind COIN-OR (http://coin-or.org) und Scip(http://scip.zib.de).

 

 

 

 

 

 

 

 

Abb. 2: Ablauf einer MIP-Optimierung

[MOPS 2011]

 

Literatur

Kallrath, J.: Gemischt-ganzzahlige Optimierung: Modellierung in der Praxis. Vieweg 2002. 

MOPS Optimierungssysteme: MOPS White Paper. s. http://www.mops-optimizer.com (abgerufen am 31.08.2011).

Nemhauser, G.; Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience 1999.  

Wolsey, Laurence A.: Integer Programming. John Wiley 1998.

 

Autor


 

Prof. Dr. Uwe Suhl, Freie Universität Berlin, Institut für Wirtschaftsinformatik, Garystr. 21, 14195 Berlin

Autoreninfo


Zuletzt bearbeitet: 26.09.2014 13:28
Letzter Abruf: 17.08.2017 03:51
Artikelaktionen