An efficient strategy for solving stochastic programming problems under endogenous and exogenous uncertainties

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ä.