東華大學圖書館 |

Performance Analysis in Large-scale Stochastic Dynamic Programs.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Performance Analysis in Large-scale Stochastic Dynamic Programs./
Author:	Chen, Chen.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2020,
Description:	227 p.
Notes:	Source: Dissertations Abstracts International, Volume: 81-12.
Contained By:	Dissertations Abstracts International81-12.
Subject:	Business administration. -
Online resource:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=27742831
ISBN:	9798645466756

Performance Analysis in Large-scale Stochastic Dynamic Programs.
Chen, Chen.

Performance Analysis in Large-scale Stochastic Dynamic Programs. - Ann Arbor : ProQuest Dissertations & Theses, 2020 - 227 p.

Source: Dissertations Abstracts International, Volume: 81-12.

Thesis (Ph.D.)--Duke University, 2020.

This item must not be sold to any third party vendors.

This dissertation studies approximations to large-scale stochastic dynamic programs, with an emphasis on applications in revenue management and operations.Many sequential decision problems from a wide variety of fields can be formulated as stochastic dynamic programs, with optimal policies characterized by the corresponding Bellman equations. However, many such formulations suffer from the so-called "curse of dimensionality": the number of possible states grows exponentially with the size of the problem, rendering finding an optimal solution impossible when the problem size is large. This forces us to design and analyze suboptimal heuristic policies. In this dissertation, we study two duality techniques --- information relaxations and Lagrangian relaxations --- for analyzing the sub-optimality of heuristic policies in particular applications. These performance bounds in turn imply asymptotic optimality of the heuristic policies for specific "large" regimes in which the "curse of dimensionality" is especially relevant.The information relaxation duality approach relaxes non-anticipativity constraints by considering a decision maker who has access to the outcomes of future uncertainties before making decisions and adds a penalty that punishes violations of the non-anticipativity onstraints. With a "perfect" information relaxation, the decision maker has access to all future uncertainties, and the problem then reduces to solving a deterministic problem for each outcome. As an application, we consider the classic problem of non-preemptively scheduling a set of jobs on machines with stochastic job processing times and the weighted sum of expected completion time objective. Scheduling problems have a deep and well-developed literature in both operations research and computer science, and many varieties of scheduling problems arise in a broad range of applications. Over the past several decades, research in the stochastic scheduling literature has been focused on the case when processing times are identical across machines, and far less is known about the case with specialized (or "unrelated") machines --- i.e., each job's processing distribution may vary across machines. Using a perfect information relaxation duality approach in which all processing times are revealed before scheduling jobs and a penalty that appropriately compensates for this additional information, we explicitly characterize the performance loss of a simple static routing policy relative to an optimal adaptive, non-anticipative scheduling policy. Our result implies that a static routing policy is asymptotically optimal in the regime of many jobs relative to the number of machines.The second part of the dissertation focuses on Lagrangian relaxations, which decompose a problem into simpler subproblems by moving "complicated" constraints to the objective using Lagrangian dual variables. As an application, we study the problem of dynamic pricing of resources that relocate over a network of locations. Customers with private willingness-to-pay sequentially request to relocate a resource from one location to another, and a revenue-maximizing service provider sets a price for each request. This problem can be formulated as an infinite horizon stochastic dynamic program, but is quite difficult to solve, as optimal pricing policies may depend on the locations of all resources in the network. We first focus on networks with a hub-and-spoke structure, and we develop a dynamic pricing policy and a performance bound based on a Lagrangian relaxation of the capacity constraint that the number of resources at the hub being nonnegative. This relaxation decomposes the problem over spokes and is thus far easier to solve than the original problem. We analyze the performance of the Lagrangian-based policy and focus on a supply-constrained large network regime in which the number of spokes (n) and the number of resources grow at the same rate. We show that the Lagrangian policy loses no more than O(\\sqrt{ln n/n}) in performance compared to an optimal policy, thus implying asymptotic optimality as n grows large. Using the same methodology, we also show that no static policy is asymptotically optimal in the large network regime. Finally, we extend the approach to general networks (i.e., multiple, interconnected hubs and spoke-to-spoke connections) and to incorporate relocation times, and we observe strong empirical performance of the policies and bounds on extensive numerical examples, including examples based on data from the ride-hailing company RideAustin.

ISBN: 9798645466756Subjects--Topical Terms:

3168311
Business administration.
Subjects--Index Terms:

Approximation methods

Performance Analysis in Large-scale Stochastic Dynamic Programs.
LDR:05746nmm a2200361 4500 001 2275343
005 20210119090706.5
008 220723s2020 ||||||||||||||||| ||eng d
020 $a 9798645466756
035 $a (MiAaPQ)AAI27742831
035 $a AAI27742831
040 $a MiAaPQ $c MiAaPQ
100 1 $a Chen, Chen. $3 1267258
245 1 0 $a Performance Analysis in Large-scale Stochastic Dynamic Programs.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2020
300 $a 227 p.
500 $a Source: Dissertations Abstracts International, Volume: 81-12.
500 $a Advisor: Brown, David B.;Balseiro, Santiago R.
502 $a Thesis (Ph.D.)--Duke University, 2020.
506 $a This item must not be sold to any third party vendors.
520 $a This dissertation studies approximations to large-scale stochastic dynamic programs, with an emphasis on applications in revenue management and operations.Many sequential decision problems from a wide variety of fields can be formulated as stochastic dynamic programs, with optimal policies characterized by the corresponding Bellman equations. However, many such formulations suffer from the so-called "curse of dimensionality": the number of possible states grows exponentially with the size of the problem, rendering finding an optimal solution impossible when the problem size is large. This forces us to design and analyze suboptimal heuristic policies. In this dissertation, we study two duality techniques --- information relaxations and Lagrangian relaxations --- for analyzing the sub-optimality of heuristic policies in particular applications. These performance bounds in turn imply asymptotic optimality of the heuristic policies for specific "large" regimes in which the "curse of dimensionality" is especially relevant.The information relaxation duality approach relaxes non-anticipativity constraints by considering a decision maker who has access to the outcomes of future uncertainties before making decisions and adds a penalty that punishes violations of the non-anticipativity onstraints. With a "perfect" information relaxation, the decision maker has access to all future uncertainties, and the problem then reduces to solving a deterministic problem for each outcome. As an application, we consider the classic problem of non-preemptively scheduling a set of jobs on machines with stochastic job processing times and the weighted sum of expected completion time objective. Scheduling problems have a deep and well-developed literature in both operations research and computer science, and many varieties of scheduling problems arise in a broad range of applications. Over the past several decades, research in the stochastic scheduling literature has been focused on the case when processing times are identical across machines, and far less is known about the case with specialized (or "unrelated") machines --- i.e., each job's processing distribution may vary across machines. Using a perfect information relaxation duality approach in which all processing times are revealed before scheduling jobs and a penalty that appropriately compensates for this additional information, we explicitly characterize the performance loss of a simple static routing policy relative to an optimal adaptive, non-anticipative scheduling policy. Our result implies that a static routing policy is asymptotically optimal in the regime of many jobs relative to the number of machines.The second part of the dissertation focuses on Lagrangian relaxations, which decompose a problem into simpler subproblems by moving "complicated" constraints to the objective using Lagrangian dual variables. As an application, we study the problem of dynamic pricing of resources that relocate over a network of locations. Customers with private willingness-to-pay sequentially request to relocate a resource from one location to another, and a revenue-maximizing service provider sets a price for each request. This problem can be formulated as an infinite horizon stochastic dynamic program, but is quite difficult to solve, as optimal pricing policies may depend on the locations of all resources in the network. We first focus on networks with a hub-and-spoke structure, and we develop a dynamic pricing policy and a performance bound based on a Lagrangian relaxation of the capacity constraint that the number of resources at the hub being nonnegative. This relaxation decomposes the problem over spokes and is thus far easier to solve than the original problem. We analyze the performance of the Lagrangian-based policy and focus on a supply-constrained large network regime in which the number of spokes (n) and the number of resources grow at the same rate. We show that the Lagrangian policy loses no more than O(\\sqrt{ln n/n}) in performance compared to an optimal policy, thus implying asymptotic optimality as n grows large. Using the same methodology, we also show that no static policy is asymptotically optimal in the large network regime. Finally, we extend the approach to general networks (i.e., multiple, interconnected hubs and spoke-to-spoke connections) and to incorporate relocation times, and we observe strong empirical performance of the policies and bounds on extensive numerical examples, including examples based on data from the ride-hailing company RideAustin.
590 $a School code: 0066.
650 4 $a Business administration. $3 3168311
650 4 $a Operations research. $3 547123
653 $a Approximation methods
653 $a Asymptotic optimality
653 $a Dynamic programming
653 $a Information relaxation duality
653 $a Lagrangian relaxation
690 $a 0310
690 $a 0796
710 2 $a Duke University. $b Business Administration. $3 1026640
773 0 $t Dissertations Abstracts International $g 81-12.
790 $a 0066
791 $a Ph.D.
792 $a 2020
793 $a English
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=27742831