Original title: Úlohy dvojstupňové a dvojúrovňové optimalizace
Translated title: Two-stage and bilevel programming
Authors: Kašný, Jakub ; Zapletal, František (referee) ; Popela, Pavel (advisor)
Document type: Master’s theses
Year: 2025
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta strojního inženýrství
Abstract: [eng] [cze]
Tato diplomová práce se zabývá dvěma typy optimalizačních modelů: stochastickým dvoustupňovým modelem a dvouúrovňovým modelem, a jejich deterministickými, resp. stochastickými variantami. Práce pojednává o již známých vztazích mezi těmito modely a dále je rozšiřuje. Především se v práci ukazuje ekvivalence mezi Karush-Kuhn-Tucker (KKT) jednostupňovými reformulacemi dvouúrovňového a stochastického dvouúrovňového modelu. Tato ekvivalence dovoluje použít algoritmy navržené pro deterministické dvouúrovňové modely i na obecnější stochastické dvouúrovňové modely, a to s žádnými nebo pouze malými úpravami těchto algoritmů. Dále pak lze upravené dvouúrovňové algoritmy testovat při řešení stochastických dvoustupňových úloh. Nejprve je však představen přehled algoritmů pro dvoustupňové a dvouúrovňové modely, ze kterého jsou vybrány čtyři algoritmy k implementaci — lineární a nelineární pro každý typ modelu. Tyto čtyři algoritmy jsou následně podrobněji diskutovány a je představena modifikace dvouúrovňových algoritmů pro použití ve scénářovém stochastickém rámci. Praktická použitelnost dvouúrovňových algoritmů na vybrané dvoustupňové úlohy je posouzena prostřednictvím analýzy složitosti spojené s reformulací dvoustupňové úlohy do tvaru vhodného pro řešení pomocí dvouúrovňových algoritmů. Poté jsou algoritmy testovány na vybrané lineární a nelineární dvoustupňové úloze. Toto testování slouží k odhalení implementačních problémů, které by nemusely být zřejmé z teoretických zjištění. Vzhledem k tomu, že algoritmy navržené přímo pro stochastické dvoustupňové úlohy by měly dosahovat lepších výsledků, testování výkonu sloužilo jako srovnání rozdílů ve výkonnosti. Kromě toho porovnání jednotlivých principů metod řešení společně s porovnáním struktur úloh vedlo k odhalení cest pro další výzkum v oblasti stochastických dvouúrovňových algoritmů. This thesis is concerned with two types of optimization models: the stochastic two-stage model and the bilevel model, along with their deterministic and stochastic variants, respectively. It discusses and extends existing connections between these models found in the literature, particularly focusing on demonstrating the equivalence of the Karush-Kuhn-Tucker (KKT) single-level reformulations for bilevel and stochastic bilevel problems. The discussed equivalence supports the idea to apply algorithms designed for deterministic bilevel cases to more general stochastic bilevel problems with no or small modifications of the existing algorithms. Furthermore, the adapted bilevel algorithms can be tested for solving stochastic two-stage problems. However, firstly, an overview of two-stage and bilevel algorithms is provided, from which four algorithms are selected for implementation, choosing linear and nonlinear algorithms for each model type. These four algorithms are discussed in more detail and a modification of the bilevel algorithms for use in scenario-based stochastic framework is presented. The practical applicability of the bilevel algorithms onto slected two-stage problems is evaluated by analyzing the complexity involved in reformulating a two-stage problem into a form suitable for solution by bilevel techniques. Then the algorithms themselves are tested on a linear and nonlinear two-stage problem to subdue the theoretical findings to a computational testing to unveil problems that might not be apparent from the theory but might occur during the software implementation. Since algorithms developed specifically for stochastic two-stage problems are assumed to perform better, the performance testing served as a comparison of the differences in the performance. Moreover, comparison of the methods' principles and problem structures paved the path for future research of the stochastic bilevel algorithms.
Keywords: algoritmus prohledávání aktivních omezení; dvoustupňové programování; dvouúrovňové programování; Karush-Kuhn-Tucker jednoúrovňová reformulace; L-shaped algoritmus; optimalizace; PHA; stochastické programování; stochastický dvouúrovňový algoritmus oblasti důvěry; active inequalities search; bilevel programming; Karush-Kuhn-Tucker single level reformulation; L-shaped algorithm; optimization; progressive hedging algorithm; stochastic bilevel trust-region algorithm; stochastic programming; two-stage programming

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: https://hdl.handle.net/11012/252457

Permalink: http://www.nusl.cz/ntk/nusl-683037


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses