Retrospective optimization of discrete stochastic systems using simplicial linear interpolation

Optimizing a stochastic system with a set of discrete design variables x is an important and difficult problem arising widely in various fields of operations research and the management sciences. Much research has developed methods for discrete stochastic optimization problems in which the objective function g is defined by a Monte Carlo simulation oracle. The function g is implicit in the oracle, in that at any design point x the objective value g( x) can be obtained only asymptotically by averaging over many calls to the oracle. Our interest is in integer decision variables x when the objective function g is smooth, in the sense that if viewed from a distance the discreteness is negligible. Such applications arise, for example, when the decision variables are inventory reorder points and quantities, numbers of machines, numbers of stock options, or staffing levels. Such smoothness implies that a local search on g can be successful in finding a good solution. Hong and Nelson [21] and Hong [20] discuss algorithm ideas for solving such problems. Many global random search methods also could be used for such problems, but their generality makes them inefficient compared to local-search approaches. We propose a family of simulation-based retrospective optimization algorithms for large-scale discrete stochastic systems via piecewise-linear interpolation. With a simplicial linear interpolation we create a continuous response surface for a discrete feasible region. A retrospective framework generates a sequence of deterministic sample-path problems that can be solved using deterministic nonlinear optimization techniques. Numerical experiments show that our method finds good estimates of optimal solutions for inventory control, transportation and scheduling systems significantly faster than the state of the art, including the recently developed COMPASS and Coordinate Search