Integer-ordered simulation optimization using R-SPLINE: retrospective search with piecewise-linear interpolation and neighborhood enumeration. 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.
Keywords for this software
References in zbMATH (referenced in 6 articles , 1 standard article )
Showing results 1 to 6 of 6.
- Amaran, Satyajith; Sahinidis, Nikolaos V.; Sharda, Bikram; Bury, Scott J.: Simulation optimization: a review of algorithms and applications (2016)
- Xie, Jing; Frazier, Peter I.; Chick, Stephen E.: Bayesian optimization via simulation with pairwise sampling and correlated prior beliefs (2016)
- Park, Chuljin; Kim, Seong-Hee: Penalty function with memory for discrete optimization via simulation with stochastic constraints (2015)
- Wang, Honggang: Direct zigzag search for discrete multi-objective optimization (2015)
- Amaran, Satyajith; Sahinidis, Nikolaos V.; Sharda, Bikram; Bury, Scott J.: Simulation optimization: a review of algorithms and applications (2014)
- Wang, Honggang; Pasupathy, Raghu; Schmeiser, Bruce W.: Integer-ordered simulation optimization using R-SPLINE: retrospective search with piecewise-linear interpolation and neighborhood enumeration (2013)