Grant: Discovery Grants Program - Individual
University of Toronto
$72,000.00
Multistage Stochastic Integer Programming: Approximate Solution Methods and Applications
EF 2023-24
Résumé
Multistage stochastic programming (MSP) provides a modeling framework for sequential decision making under uncertainty. The majority of the application of mathematical programming assumes deterministic data. However, real world problems almost always include some uncertain parameters (e.g., in a portfolio optimization problem, the returns of different assets are highly uncertain at the time of investment). It has been traditionally difficult to predict such uncertainties with a high accuracy, but now with the existence of substantial historical records and advances in data analytics, we can accurately model uncertainty. The ability to exploit available data made it possible to incorporate uncertainty into mathematical models, which is the case in stochastic programming. Moreover, in many applications, the planning horizon has multiple decision stages and the uncertainty is revealed gradually over time. Therefore, MSP is a viable modeling approach. MSP has numerous applications in areas like energy, finance, and scheduling. However, MSP models are notoriously hard to solve in general, and existing solution approaches frequently fail to solve real-life size problems. Motivated by its application potential and limitations of the state-of-the-art solution methods, this program aims to make fundamental algorithmic and theoretical contributions to MSP (especially with integer variables), and extend its applications in a variety of areas.Theme 1 of the program will focus on developing methods that can overcome modeling and algorithmic challenges in the class of MSP problems, especially the ones involving integer variables, and that can provide (provably) good feasible policies. The methodology will be mostly based on novel ways of using (linear) decision rules. In particular, new decision rules will be developed for MSP models with integer variables. The tractability of the proposed methods and the quality of the obtained solutions will be analyzed. The results will significantly advance the state-of-the-art in stochastic programming.Theme 2 of the program will explore diverse applications of MSP such as operating room scheduling, power systems and portfolio optimization. Novel MSP models will be proposed for certain important problems in these areas, and the value of such models over deterministic and two-stage stochastic programming models will be investigated. The results will provide valuable planning, scheduling and operational tools for decision makers.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2018-04984
Name nom
Bodur, Merve
Department département
School of Mathematics
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2018
Award amount
72000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
9999
Research subject group en
Not available
Research subject group fr
Not available
Research subject en
Non disponible
Research subject fr
Non disponible
Application title
Multistage Stochastic Integer Programming: Approximate Solution Methods and Applications
Keyword
Container ship stowage planning; Decision rules; Decomposition algorithms; Integer programming; Operating room scheduling; Optimization; Power systems; Service system staffing and scheduling; Stochastic programming; Two-stage approximations
Application summary
Multistage stochastic programming (MSP) provides a modeling framework for sequential decision making under uncertainty. The majority of the application of mathematical programming assumes deterministic data. However, real world problems almost always include some uncertain parameters (e.g., in a portfolio optimization problem, the returns of different assets are highly uncertain at the time of investment). It has been traditionally difficult to predict such uncertainties with a high accuracy, but now with the existence of substantial historical records and advances in data analytics, we can accurately model uncertainty. The ability to exploit available data made it possible to incorporate uncertainty into mathematical models, which is the case in stochastic programming. Moreover, in many applications, the planning horizon has multiple decision stages and the uncertainty is revealed gradually over time. Therefore, MSP is a viable modeling approach. MSP has numerous applications in areas like energy, finance, and scheduling. However, MSP models are notoriously hard to solve in general, and existing solution approaches frequently fail to solve real-life size problems. Motivated by its application potential and limitations of the state-of-the-art solution methods, this program aims to make fundamental algorithmic and theoretical contributions to MSP (especially with integer variables), and extend its applications in a variety of areas.Theme 1 of the program will focus on developing methods that can overcome modeling and algorithmic challenges in the class of MSP problems, especially the ones involving integer variables, and that can provide (provably) good feasible policies. The methodology will be mostly based on novel ways of using (linear) decision rules. In particular, new decision rules will be developed for MSP models with integer variables. The tractability of the proposed methods and the quality of the obtained solutions will be analyzed. The results will significantly advance the state-of-the-art in stochastic programming.Theme 2 of the program will explore diverse applications of MSP such as operating room scheduling, power systems and portfolio optimization. Novel MSP models will be proposed for certain important problems in these areas, and the value of such models over deterministic and two-stage stochastic programming models will be investigated. The results will provide valuable planning, scheduling and operational tools for decision makers.