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 zwei Mean-Risk-Modell. Als Risikomaße stehen
zum einen das Maß "Wahrscheinlichkeit des Überschreitens einer Schranke"
(ausführlich untersucht in [7]) und zum anderen das Maß "Erwartetes Überschreiten einer
Schranke" (siehe [6], hier: "expected shortfall below target") 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 SUN ULTRASparc unter Solaris sowie 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.
Downloads: Quellcode (Stand: 12.03.2011) des Programms (entpackt sich im aktuellen Verzeichnis)
und zwei kleine Beispielprobleme,
welche die 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.
Referenzen
- C.C. Carøe, R. Schultz (1999), Dual Decomposition in Stochastic Integer Programming,
Oper. Res. Lett. 24, pp. 37-45.
- 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.
- Using the CPLEX Callable Library,
ILOG Inc., http://www.ilog.com.
- 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.
- C. Helmberg: http://www-user.tu-chemnitz.de/~helmberg/.
- 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.
- R. Schultz, S. Tiedemann (2002), Risk aversion via excess probabilities in stochastic
programs with mixed-integer recourse, SIAM Journal on Optimization (to appear).
|
