An efficient strategy for solving stochastic programming problems under endogenous and exogenous uncertainties
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2020-03-17
Department
Major/Subject
Systems and Operations Research
Mcode
SCI3055
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
55
Series
Abstract
Despite multi-stage decision problems being common in production planning, there is a class of such problems for which a general solution framework does not exist, namely problems with endogenous uncertainty. Methods from decision analysis and stochastic programming can be used, but both require significantly constraining assumptions. In order to overcome the current challenges, Decision Programming combines approaches from these two fields, making it possible to acquire optimal strategies for different decision problems. Decision Programming is strictly limited to problems in which uncertainty events and decisions are taken from a finite discrete set, reducing its applicability to problems with continuous decision spaces. Discretizing a continuous decision space increases the problem size and can lead to computational intractability. This thesis presents a problem decomposition approach extending the Decision Programming framework. The decomposition approach allows for considering continuous decision and uncertainty spaces in problems with a suitable structure. The proposed framework was applied to three different problems, including a large-scale production planning problem from literature. The main example in this thesis is a novel approach on climate change mitigation cost-benefit analysis, where R&D is carried out simultaneously with the emissions abatement decisions. The R&D projects provide information on the climate damage severity and decrease the price of abatement. Problems with similar structure have not been discussed in the literature, and the extended Decision Programming framework is able to solve the problem to optimality.Vaikka monivaiheiset päätöksenteko-ongelmat ovat yleisiä tuotannon suunnittelussa, erääseen ryhmään näitä ongelmia ei ole yleistä ratkaisumenetelmää. Tämä johtuu niinsanotusta endogeenisestä epävarmuudesta. Näihin ongelmiin voidaan soveltaa stokastisen optimoinnin ja päätösanalyysin menetelmiä, mutta kummatkin vaativat merkittäviä rajoittavia oletuksia. Uusi menetelmä, Decision Programming, yhdistää stokastisen optimoinnin ja päätösanalyysin menetelmiä mahdollistaen optimistrategioden löytämisen erilaisissa päätösongelmissa. Decision Programming rajoittuu ongelmiin joissa satunnaistapahtumat ja päätökset valitaan äärellisistä diskreeteistä joukoista. Tämä rajoittaa sen soveltuvuutta ongelmiin joissa päätösjoukot ovat jatkuvia, sillä tällaisen päätösjoukon diskretointi kasvattaa ongelman kokoa ja saattaa johtaa laskennallisiin haasteisiin. Tässä työssä esitellään Decision Programming -viitekehystä laajentava hajotusmenetelmä jonka avulla voidaan ratkaista ongelmia, jotka sisältävät jatkuvia päätös- ja epävarmuusjoukkoja. Menetelmän soveltaminen vaatii kuitenkin ongelmalta sopivan rakenteen. Työssä esitettyä menetelmää sovellettiin kolmeen esimerkkiongelmaan, joista yksi on suuren mittakaavan tuotannonsuunnitteluongelma kirjallisuudesta. Työn pääesimerkki on uudenlainen lähestymistapa ilmastonmuutoksen hillinnän kustannus-hyötyanalyysiin, jossa tutkimustyötä tehdään samanaikaisesti päästövähennysten kanssa. Tutkimusprojekteilla saadaan lisätietoa ilmastovaikutusten vakavuudesta ja lasketaan päästövähennysten hintaa. Vastaavanlaisia ongelmia ei ole ennen käsitelty kirjallisuudessa ja laajennettu Decision Programming -viitekehys mahdollistaa optimiratkaisun löytämisen tässä esimerkissä.Description
Supervisor
Oliveira, FabricioThesis advisor
Ekholm, TommiKeywords
decision programming, endogenous uncertainty, stochastic programming, decision analysis, influence diagrams, climate change mitigation