  


Stochastically Constrained Simulation Optimization On IntegerOrdered Spaces: The cgRSPLINE Algorithm
Kalyani Nagaraj (kalyaninpurdue.edu) Abstract: We consider the problem of identifying the solution(s) to an optimization problem whose domain is a subset of the integer lattice, and whose objective and constraint functions can only be observed using a stochastic simulation. Such problems seem particularly prevalent (see www.simopt.org) within service systems having capacity or servicelevel constraints. We present cgRSPLINE  a random restarts algorithm that repeatedly executes a gradientbased simulation optimization (SO) routine on strategically relaxed samplepath problems, to return a sequence of local solution estimators at increasing precision; the local solution estimators are probabilistically compared to update an incumbent solution sequence that estimates the global minimum. Four issues are salient. (i) Solutions with binding stochastic constraints render naive sampleaverage approximation inconsistent; consistency in cgRSPLINE is guaranteed through sequential relaxation of the stochastic constraints. (ii) Lighttailed convergence that is characteristic of SO problems on unconstrained discrete spaces seems to be weakened here; the general convergence rate is shown to be subexponential. (iii) An explorationexploitation characterization demonstrates that cgRSPLINE achieves the fastest convergence rate when the number of restarts is proportional to simulation budget per restart; this is in contrast with the continuous context where much less exploration has been prescribed. (iv) Certain heuristics on choosing constraint relaxations, solution reporting, and premature stopping are important to ensure that cgRSPLINE exhibits good finitetime performance while retaining asymptotic properties. We demonstrate cgRSPLINE using three examples, two of which are nontrivial. Keywords: stochastic constraints, integerordered simulation optimization, cgRSPLINE Category 1: Stochastic Programming Category 2: Integer Programming Category 3: Global Optimization Citation: Under review with Operations Research. Submission date: August 2014 Download: [PDF] Entry Submitted: 10/03/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  