Optimization Online


Stochastically Constrained Simulation Optimization On Integer-Ordered Spaces: The cgR-SPLINE Algorithm

Kalyani Nagaraj (kalyanin***at***purdue.edu)
Raghu Pasupathy (pasupath***at***purdue.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 service-level constraints. We present cgR-SPLINE --- a random restarts algorithm that repeatedly executes a gradient-based simulation optimization (SO) routine on strategically relaxed sample-path 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 sample-average approximation inconsistent; consistency in cgR-SPLINE is guaranteed through sequential relaxation of the stochastic constraints. (ii) Light-tailed convergence that is characteristic of SO problems on unconstrained discrete spaces seems to be weakened here; the general convergence rate is shown to be sub-exponential. (iii) An exploration-exploitation characterization demonstrates that cgR-SPLINE 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 cgR-SPLINE exhibits good finite-time performance while retaining asymptotic properties. We demonstrate cgR-SPLINE using three examples, two of which are nontrivial.

Keywords: stochastic constraints, integer-ordered simulation optimization, cgR-SPLINE

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
Entry Accepted: 10/03/2015
Entry Last Modified: 10/03/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society