ZIB-Logo
KONRAD-ZUSE-ZENTRUM
FÜR INFORMATIONSTECHNIK
BERLIN
Home » Forschung » Diskrete Mathematik » Optimierung » Lineare und Nichtlineare Ganzzahlige Optimierung
MATHEON-Logo

Quickview

Ganzzahlige Optimierung
Leitung: Dr. Thorsten Koch

Mitarbeiter,
Projekte (Aktuell | Archiv),
Publikationen,

Software


Lineare und Nichtlineare Ganzzahlige Optimierung

Die ganzzahlige Programmierung beschäftigt sich mit Optimierungsproblemen, in denen Güter oder Entscheidungen unteilbar sind. Viele Probleme lassen sich effizient mit linearer Zielfunktion und linearen Nebenbedingungen formulieren. Bei einigen Anwendungen wirken jedoch nichtlineare und diskrete Komponenten auf komplexe Weise zusammen.

Viele Probleme aus Bereichen wie Telekommunikation, Verkehr oder Chip-Entwicklung lassen sich als sogenannte lineare gemischt-ganzzahlige Programme (linear mixed integer programs, MIPs) formulieren. Aber gerade weil diese Methode so vielseitig ist, werden die Anforderungen an die Lösungsverfahren immer höher. Wir entwickeln und verbessern grundlegende Algorithmen, um MIPs mittels eines allgemeinen, von der Problemstruktur unabhängigen Standardverfahrens zu lösen.

Nichtlineare gemischt-ganzzahlige Programme
(non-linear mixed integer programs, MINLPs) treten auf in Anwendungsbereichen wie der Optimierung von Einnahmen (= Preis x Menge) bei der Angebotsplanung im Verkehr, der Planung und Steuerung von Gas-, Wasser- und Abwassernetzen, bei denen neben der Flussmenge Größen wie der Druck wichtig sind, oder der Behandlung von Vermischungen bei der Materialflussoptimierung im Bergbau. Diese Probleme sind sogar noch schwieriger und bisher weniger untersucht als MIPs. Wir arbeiten sowohl an Techniken zur Ausnutzung spezieller Strukturen zur Lösung konkreter Fragestellungen als auch an der Verbesserung allgemeiner Lösungsverfahren.