swMATH ID: 29802
Software Authors: Wang, Honggang; Pasupathy, Raghu; Schmeiser, Bruce W.
Description: 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.
Homepage: https://dl.acm.org/citation.cfm?doid=2499913.2499916
Keywords: simulation optimization; retrospective search algorithm; piecewise-linear interpolation; discrete neighborhood enumeration; local minima
Related Software: COMPASS; EGO; SimOpt; ASTRO-DF; PyMOSO; Tabu search; DiceOptim; DiceKriging; MultiMin; Scatter Search; SNOBFIT; CMA-ES; NOMADm; VBASim; RngStreams; PyPRS; GitHub; MRG32k3a; RngSteam; OptQuest
Cited in: 12 Publications

Citations by Year