Integer-Ordered Simulation Optimization using R-SPLINE
Abstract
We consider simulation-optimization (SO) models where the decision variables are integer ordered and the objective function is defined implicitly via a simulation oracle, which for any feasible solution can be called to compute a point estimate of the objective-function value. We develop R-SPLINE---a Retrospective-search algorithm that alternates between a continuous Search using Piecewise-Linear Interpolation and a discrete Neighborhood Enumeration, to asymptotically identify a local minimum. R-SPLINE appears to be among the first few gradient-based search algorithms tailored for solving integer-ordered local SO problems. In addition to proving the almost-sure convergence of R-SPLINE’s iterates to the set of local minima, we demonstrate that the probability of R-SPLINE returning a solution outside the set of true local minima decays exponentially in a certain precise sense. R-SPLINE, with no parameter tuning, compares favorably with popular existing algorithms.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jul 01, 2013
- Source ID
- 10.1145/2499913.2499916
Entities
People
- Bruce W. Schmeiser
- Honggang Wang
- Raghu Pasupathy
Organizations
- Office of Naval Research
- Purdue University
- Rutgers University
- Virginia Tech