Implementace algoritmu progressive hedging pro inženýrské aplikace

An Implementation of Progressive Hedging Algorithm for Engineering Problems

conference paper

en

The purpose of the paper is to introduce an original parallel implementation of the decomposition algorithm for large-scale engineeering decision making problems involving uncertain parameters. Reference to these problems in mechanical and civil engineering are included. Specifically, a mathematical programming approach is chosen to model decisions. The uncertain parameters are modeled by random elements with discrete probability distributions. Therefore, the suitable models are scenario-based stochastic programs that may have several stages. Among the decomposition algorithms, we have chosen a progressive hedging algorithm (PHA) that is suitable also for the common case in engineering when nonlinear programs are related to scenarios. The algorithm is described in the form that is suitable for an object-oriented implementation and further implemented within the object-oriented framework for parallel computations. However, the inner parts of the implementation allows to use various solvers for the scenario-related problems. We have chosen the GAMS as a good initial to solve problems of scenarios. The original example is utilized to illustrate algorithm's implementation behaviour and further large-scale tests are listed.

Článek se zabývá popisem původní paralelní implementace dekompozičního algoritmu pro rozsáhlé inženýrské optimalizační úlohy zahrnující neurčité parametry. Odkazy na příklady těchto úloh ve strojním a stavebním inženýrství jsou rovněž uvedeny. V těchto úlohách je použito přístupu matematického programování jako prostředku pro modelování rozhodovacích problémů, ve kterých jsou neurčité parametry reprezentovány pomocí náhodných proměnných s diskrétním rozložením pravděpodobnosti. Vhodnými modely pro tyto úlohy jsou tedy scénářové stochastické programy, které mohou být i vícestupňové. Mezi různými dekompozičními algoritmy jsme zvolili algoritmus progressive hedging, který je vhodný pro inženýrské úlohy, které jsou obvykle nelineární. Algoritmus je popsán ve formě, která je vhodná pro objektově orientovanou implementaci se strukturou pro paralelní výpočty. Výhodou implementace je skutečnost, že pro řešení scénářových úloh lze použít různé optimalizační řešiče podle charakteru řešené úlohy. My jsme pro řešení scénářových úloh použili optimalizační software GAMS. V článku je prezentován původní příklad demonstrující chování algoritmu a výčet použití algoritmu pro rozsáhlé inženýrské problémy.

The purpose of the paper is to introduce an original parallel implementation of the decomposition algorithm for large-scale engineeering decision making problems involving uncertain parameters. Reference to these problems in mechanical and civil engineering are included. Specifically, a mathematical programming approach is chosen to model decisions. The uncertain parameters are modeled by random elements with discrete probability distributions. Therefore, the suitable models are scenario-based stochastic programs that may have several stages. Among the decomposition algorithms, we have chosen a progressive hedging algorithm (PHA) that is suitable also for the common case in engineering when nonlinear programs are related to scenarios. The algorithm is described in the form that is suitable for an object-oriented implementation and further implemented within the object-oriented framework for parallel computations. However, the inner parts of the implementation allows to use various solvers for the scenario-related problems. We have chosen the GAMS as a good initial to solve problems of scenarios. The original example is utilized to illustrate algorithm's implementation behaviour and further large-scale tests are listed.

scénářové stochastické programy, algoritmus progressive hedging, objektově orientovaný přístup, optimalizační software GAMS

scenario-based stochastic program, progressive hedging algorithm, object-oriented approach, optimization software GAMS

2010

23.06.2010

BUT

Brno

978-80-214-4120-0

MENDEL 2010 - 16th International Conference on Soft Computing

459–464

6