Simulation-based optimization over discrete sets with noisy constraints

Abstract

This article considers a constrained optimization problem over a discrete set where noise-corrupted observations of the objective and constraints are available. The problem is challenging because the feasibility of a solution cannot be known for certain, due to the noisy measurements of the constraints. To tackle this issue, a method is proposed that converts constrained optimization into the unconstrained optimization problem of finding a saddle point of the Lagrangian. The method applies stochastic approximation to the Lagrangian in search of the saddle point. The proposed method is shown to converge, under suitable conditions, to the optimal solution almost surely as the number of iterations grows. The effectiveness of the proposed method is demonstrated numerically in three settings: (i) inventory control in a periodic review system; (ii) staffing in a call center; and (iii) staffing in an emergency room.

Keywords:

• Optimization via simulation
• discrete optimization
• Lagrangian duality