Efficient Algorithms for Constrained Simulation Optimziation

Stochastic simulation is a powerful tool for evaluating large-scale complex engineeringsystems, since closed-form analytical models generally do not exist for these systems.Simulation allows one to accurately specify a system through the use of logicallycomplex, and often non-algebraic variables and constraints. Detailed dynamics of thesystem can therefore be modeled. This capability complements the inherent limitation oftraditional optimization toward large-scale complex systems, and makes simulationoptimization a popular tool for improving the performance of these systems.In this project, we consider stochastically constrained simulation optimization overdiscrete solution space, where the objective function is deterministic and the constraintmeasures are evaluated via stochastic simulation. This problem is challenging primarilybecause: the solution space often lacks rich structure that can be utilized in identifyinggood-quality solutions (difficulty 1); and the feasibility of a solution cannot be knownfor certain, due to the noisy measurements of the constraints (difficulty 2).In order to handle difficulty 1, we will exploit two different types of search methods toeffectively explore the solution space: a globally convergent search framework (nestedpartitions, NP) and a locally convergent search framework (convergent optimization viamost promising area stochastic search, COMPASS). The high efficiency of both methodshas been widely tested, and the new optimization algorithms will be developed based onthese two search frameworks. For difficulty 2, we will design an efficient feasibilitydetection procedure for the sampled solutions. The feasibility detection procedure is usedwhen the objective value of a sampled solution is better than that of the currentobserved best feasible solution. Therefore, a large number of solutions visited by thesearch algorithms do not need to be simulated, which opens up the possibility for thecomputing efficiency to be significantly improved. For problems with very large scale, wealso explore the use of parallel computing to further improve the efficiency of theproposed algorithms. Some preliminary empirical results suggest that the proposedresearch is very promising.In particular, this project consists of three objectives:1. Develop an NP-based algorithm for the simulation optimization problem underconsideration;2. Develop a COMPASS-based algorithm for the simulation optimization problem underconsideration;3. Investigate the benefits and implementation of parallel computing environments forthe proposed algorithms in Objective 1 and 2.