Discrete optimization via simulation: Algorithms and error control.

摘要

We propose an optimization-via-simulation (OvS) algorithm, called COMPASS, for use when the performance measure is estimated via a stochastic, discrete-event simulation, and the decision variables are integer ordered. We prove that COMPASS converges to the set of local optimal solutions with probability 1 for both terminating and steady-state simulation, and for both fully constrained problems and partially constrained or unconstrained problems under very mild conditions. We show that COMPASS can solve a wide range of problems and work better than some widely used algorithms.; Ranking and selection (R&S) has been proposed in the literature to control the error of OvS algorithms. To fully incorporate R&S in OvS algorithms, at least two problems need to be solved: The first problem is managing the significant computational overhead associated with switching among simulations of different solutions when using fully-sequential R&S procedures; and the second problem is adapting R&S procedures to work when solutions are revealed sequentially. To solve the first problem, we propose new adaptive sequential R&S procedures that balance the sampling cost and switching cost. To solve the second problem, we design new procedures that allow solutions be added sequentially into the set of solutions in comparison. These procedures provide the same statistical guarantees as existing procedures.