Back to search

Cornell University

EXPLORING AND EXPLOITING STRUCTURE IN LARGE SCALE SIMULATION OPTIMIZATION

Abstract

dc:description.abstract

The thesis explores how to solve simulation-based optimization problems more efficiently using information about the problem structure. Two primary ideas are explored. The first idea involves developing numerical methods to detect the structure of convexity in the output function of a simulation. The second idea exploits simulation traces to generate gradient-like information to guide optimization. The goal of this thesis is to provide insights on solving practical large-scale simulation optimization problems that defy solution by existing simulation-optimization algorithms. In doing so, we hope to inspire algorithmic developments on sub-classes of simulation optimization problems. In the first part of this thesis, we give a asymptotically valid numerical procedure to detect the convexity in the output function of a simulation model. Since the simulated function could be expensive to evaluate, we adapt a Bayesian sequential sampling procedure, in which a set of new (noisy) samples is collected in each iteration to update a posterior model of the function evaluations. Based on that, the posterior probability that the underlying function is convex is estimated using Monte Carlo simulation, for which we develop variance reduction methods with significant improvement in the efficiency. The second and third parts of this thesis are on exploiting gradient-like information from the simulation to solve large-scale simulation optimization problems. In the second part of the thesis, we give heuristics for optimizing the overnight rebalancing of the bike-sharing system in New York City with 466 stations and hence 932 decision variables. The heuristics use the number of failed trips incurred by each station to indicate approximate gradient directions, and show effective improvement given any starting solution. In the third part of the thesis we further propose the idea of pseudo-gradient defined as an approximate gradient estimated from the historical simulation traces without rerunning the simulation. We prove that when the objective is strongly convex and the pseudo-gradient is accurately approximated, a pseudo-gradient-search procedure will converge to the near-optimal solution. We give examples of the pseudo-gradient in the cases of rebalancing a bike-sharing system and scheduling and staffing agents in a multiskill call center. The resulting search procedures perform better than the existing methods for the bike-sharing case and show comparable results to the state-of-art cutting-plane method for the call center example. The results indicate the effectiveness of pseudo-gradient search and its potential of replacing more sophisticated methods.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research
Grantor
Cornell University
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Jian, Nanjing
Chair dc:contributor.chair
  • Henderson, Shane G.
Committee members dc:contributor.committeemember
  • Lewis, Adrian S.
  • Frazier, Peter

Subjects

dc:subject × 7

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
10361604
Dc Identifier Other
ProQuest Submission ID: 10447
ProQuest Publication ID: 10616799

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Jian, Nanjing. EXPLORING AND EXPLOITING STRUCTURE IN LARGE SCALE SIMULATION OPTIMIZATION. Doctor of Philosophy thesis, Cornell University, 2017. https://hdl.handle.net/1813/56927