Loading...
Please wait, while we are loading the content...
Similar Documents
A mathematical programming approach to stochastic and dynamic optimization problems
| Content Provider | Semantic Scholar |
|---|---|
| Author | Bertsimas, Dimitris |
| Copyright Year | 1994 |
| Abstract | We survey a new approach that the author and his co-workers have developed to formulate generic stochastic and dynamic optimization problems as mathematical programming problems. The approach has two components: (a) it produces bounds on the performance of an optimal policy, and (b) it develops techniques to construct optimal or near-optimal policies. The central idea for developing bounds is to characterize the region of achievable performance (or performance space) in a stochastic and dynamic optimization problem, i.e., find linear or nonlinear constraints on the performance vectors that all admissible policies satisfy. With respect to this goal we review recent progress in characterizing the performance space and its implications for the following problem classes: Indexable systems (the multi-armed bandit problem and its extensions), polling systems, multiclass queueing networks and loss networks. We propose three ideas for constructing optimal or near-optimal policies: (1) for systems for which we have an exact characterization of the performance space we outline an adaptive greedy algorithm that gives rise to indexing policies (we illustrate this technique in the context of indexable systems); (2) we use integer programming to construct policies from the underlying descriptions of the performance space (we illustrate this technique in the context of polling systems); (3) we use linear control over polyhedral regions to solve deterministic versions for this class of problems. This approach gives interesting insights for the structure of the optimal policy (we illustrate this idea in the context of multiclass queueing networks). The unifying theme in the paper is the thesis that better formulations lead to deeper understanding and better solution methods. Overall the proposed approach for stochastic and dynamic optimization parallels efforts of the mathematical programming community in the last fifteen years to develop sharper formulations (polyhedral combinatorics and more recently nonlinear relaxations) and leads to new insights ranging from a complete characterization for indexable systems to tight lower bounds and new algorithms with provable a posteriori guarantees for their suboptimality for polling systems, multiclass queueing and loss networks. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://dspace.mit.edu/bitstream/handle/1721.1/5228/OR-288-94-30352171.pdf?sequence=1 |
| Alternate Webpage(s) | http://dspace.mit.edu/bitstream/1721.1/2507/1/SWP-3668-30352171.pdf |
| Alternate Webpage(s) | http://mit.dspace.org/bitstream/handle/1721.1/5228/OR-288-94-30352171.pdf?sequence=1 |
| Alternate Webpage(s) | http://dspace.mit.edu/bitstream/handle/1721.1/2507/SWP-3668-30352171.pdf?sequence=1 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
