Sequential Decision-making Under Uncertainty: Novel Methodologies and Applications

In sequential decision-making under uncertainty, multistage stochastic mixed-integer programming (MSMIP) is a tool for addressing optimization problems with a given probability distribution and the goal of optimizing a performance measure over a planning horizon. If there is no knowledge about the probability distribution, multistage adaptive robust optimization (MSARO) is a suitable modeling framework. The goal of this thesis is to expand the methodological aspects of these two techniques, and in turn their applications. First, we study MSMIP problems, which can be approximated by using certain policies, e.g., linear decision rules. However, directly applying this idea to problems with integer decisions is difficult. We introduce Lagrangian dual decision rules (LDDRs) for MSMIP that overcome this difficulty by applying decision rules in Lagrangian duals of the MSMIP. We propose two new bounding techniques based on stagewise and nonanticipative Lagrangian duals. Our proposal requires fewer assumptions than most existing MSMIP methods. Our numerical experiments demonstrate that the LDDR approaches yield significant optimality gap reductions compared to existing general-purpose bounding methods for MSMIP. Next, we consider two problems in telecommunications industry. Network service providers routinely allocate resources to incoming requests and recover under-utilized capacity. For this resource allocation/reallocation, we present the first two-stage stochastic programming models to maximize the expected throughput, and solve them by an efficient decomposition algorithm that benefits from their observed tight linear programming bound. Additionally, we model the provisioning problem by MSMIP and approach it by our LDDR methodology. Experiments on real backbone networks reveal the significant value of considering the often overlooked uncertainty. Lastly, for MSARO problems we design primal and dual bounding methods, originated from adaptation of two decision rules rooted in stochastic programming. Our framework approximates the primal and dual formulations of MSARO with two-stage models. We provide sufficient conditions under which the column-and-constraint generation can exactly solve the primal approximation. For the dual approximation, we present a monolithic bilinear program valid for continuous MSARO problems, and a cutting-plane method for mixed-integer cases. Computational experiments on newsvendor and location-transportation problems show that our bounds yield considerably smaller optimality gaps compared to the existing methods.

Department dc:contributor.department

Mechanical and Industrial Engineering

Year dc:date.issued

2022

Author dc:creator

• Daryalal, Maryam

Advisor dc:contributor.advisor

• Bodur, Merve

• Decomposition methods
• Robust optimization
• Sequential decision-making
• Stochastic programming
• Telecommunications

Handle dc:identifier.uri

http://hdl.handle.net/1807/124908

OAI identifier oai:identifier

oai:utoronto.scholaris.ca:1807/124908