Penalty Function with Memory for Discrete Optimization via Simulation with Stochastic Constraints

Abstract

We consider a discrete optimization via simulation (DOvS) problem with stochastic constraints on secondary performance measures in which both objective and secondary performance measures need to be estimated by stochastic simulation. To solve the problem, we develop a new method called the Penalty Function with Memory (PFM). It is similar to an existing penalty-type method—which consists of a penalty parameter and a measure of violation of constraints—in a sense that it converts a DOvS problem with constraints into a series of unconstrained problems. However, PFM uses a different penalty parameter, called a penalty sequence, determined by the past history of feasibility checks on a solution. Specifically, assuming a minimization problem, a penalty sequence diverges to infinity for any infeasible solution but converges to zero for any feasible solution under certain conditions. As a result, a DOvS algorithm combined with PFM performs well even when an optimal feasible solution is a boundary solution with one or more active constraints. We prove convergence properties and discuss parameter selection for the implementation of PFM. Experimental results on a number of numerical examples show that a DOvS algorithm combined with PFM works well.