R-SPLINE

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.


References in zbMATH (referenced in 12 articles , 1 standard article )

Showing results 1 to 12 of 12.
Sorted by year (citations)

  1. Pasupathy, Raghu; Song, Yongjia: Adaptive sequential sample average approximation for solving two-stage stochastic linear programs (2021)
  2. Cooper, Kyle; Hunter, Susan R.: PyMOSO: software for multiobjective simulation optimization with R-PERLE and R-MinRLE (2020)
  3. Cooper, Kyle; Hunter, Susan R.; Nagaraj, Kalyani: Biobjective simulation optimization on integer lattices using the epsilon-constraint method in a retrospective approximation framework (2020)
  4. Pedrielli, Giulia; Wang, Songhao; Ng, Szu Hui: An extended two-stage sequential optimization approach: properties and performance (2020)
  5. Hu, Liujia; Andradóttir, Sigrún: An asymptotically optimal set approach for simulation optimization (2019)
  6. Lam, Henry: Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization (2019)
  7. Amaran, Satyajith; Sahinidis, Nikolaos V.; Sharda, Bikram; Bury, Scott J.: Simulation optimization: a review of algorithms and applications (2016)
  8. Xie, Jing; Frazier, Peter I.; Chick, Stephen E.: Bayesian optimization via simulation with pairwise sampling and correlated prior beliefs (2016)
  9. Park, Chuljin; Kim, Seong-Hee: Penalty function with memory for discrete optimization via simulation with stochastic constraints (2015)
  10. Wang, Honggang: Direct zigzag search for discrete multi-objective optimization (2015)
  11. Amaran, Satyajith; Sahinidis, Nikolaos V.; Sharda, Bikram; Bury, Scott J.: Simulation optimization: a review of algorithms and applications (2014)
  12. Wang, Honggang; Pasupathy, Raghu; Schmeiser, Bruce W.: Integer-ordered simulation optimization using R-SPLINE: retrospective search with piecewise-linear interpolation and neighborhood enumeration (2013)