Fakultät für Mathematik
Campus Essen


Startseite
Kontakt
Mitarbeiter
Lehre
Forschung
Projekte
Preprints
Verweise



  Mitglied des
ZLV



Optimierung und algorithmische diskrete Mathematik , Campus Essen

Software


DDSIP - Duale Dekomposition in der zweistufigen stochastischen gemischt-ganzzahligen Optimierung

`DDSIP' ist eine C-Implementation eines Dekompositionsalgorithmus für zweistufige stochastische gemischt-ganzzahlige Optimierungsprobleme. Der Dekompositionsalgorithmus basiert auf der Lagrange-Relaxation der Nichtantizipativitätsnebenbedingungen und einem Branch-und-Bound-Algorithmus um diese wieder herzustellen. Der Algorithmus ist in [1] und [2] detailiert beschrieben.

Wir benutzen C. Helmbergs ConicBundle-Implementation [5] um das Lagrange-Dualproblem zu lösen und die CPLEX-C-Bibliothek (CPLEX ab Version 11.2.0) um die auftretenden gemischt-ganzzahligen Teilprobleme zu bearbeiten.

`DDSIP' unterstützt mehrere Mean-Risk-Modelle. Als Risikomaße stehen u.a. das Maß "Wahrscheinlichkeit des Überschreitens einer Schranke" (ausführlich untersucht in [7]), das Maß "Erwartetes Überschreiten einer Schranke" (siehe [6], hier: "expected shortfall below target"), "Absolute semideviation", "Value-at-risk" und "Tail value-at-risk" zur Verfügung.

Die Implementation ist Forschungscode, mit Sicherheit nicht vollst"ändig getestet und kommt wie bei freier Software üblich ohne jegliche Garantie. Sie läuft bei uns auf PCs unter Linux. Das Programm ist für die nichtkommerzielle Nutzung frei erhältlich. Voraussetzung für die Nutzung ist ein Computer mit einer der angegebenen OS-Umgebungen und das Vorhandensein einer CPLEX-Lizenz (DDSIP unterstützt Version 12.6).
ddsip ist jetzt auf github zu finden, der Quellcode kann vom folgenden Link mittels 'git clone' bezogen werden.:
https://github.com/RalfGollmer/ddsip
Downloads: Zwei kleine Beispielprobleme, welche die neuen Fileformate und den Aufruf von ddsip demonstrieren.
Grundsätzliche Fragen zum Format der Eingabedaten und zur Funktionalität des Programms werden im Manual [4] (ddsip-man.pdf, 177K) erläutert. Das Manual ist im github repository enthalten.


DDSIP kann auf dem NEOS-Server getestet werden:

http://www.neos-server.org/neos/solvers/slp:ddsip/MPS.html for MPS format input
http://www.neos-server.org/neos/solvers/slp:ddsip/LP.html    for LP format input

Referenzen
  1. C.C. Carøe, R. Schultz (1999), Dual Decomposition in Stochastic Integer Programming, Oper. Res. Lett. 24, pp. 37-45.
     
  2. C.C. Carøe, R. Schultz (1998), A two-stage stochastic program for unit commitment under uncertainty in a hydro-thermal power system, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Preprint SC 98-11, 1998.
     
  3. Using the CPLEX Callable Library, ILOG Inc., http://www.ilog.com.
     
  4. Märkert, A. (2004), Gollmer, R. (2008) User's guide to ddsip - A C Package for the Dual Decomposition of Stochastic Programs with Mixed-Integer Recourse.
     
  5. C. Helmberg: http://www-user.tu-chemnitz.de/~helmberg/.
     
  6. W. Ogryczak, A. Ruszczynski (1999), From stochastic dominance to mean-risk models: Semideviations as risk measures, European Journal of Operations Research 116 (1999), 33-50.
     
  7. R. Schultz, S. Tiedemann (2002), Risk aversion via excess probabilities in stochastic programs with mixed-integer recourse, SIAM Journal on Optimization (to appear).
© Universität Duisburg-Essen - Kontakt: ralf.gollmer 'at' uni-duisburg-essen.de