Biobjective Simulation Optimization on Integer Lattices Using the Epsilon-Constraint Method in a Retrospective Approximation Framework

We consider multiobjective simulation optimization (MOSO) problems on integer lattices, that is, nonlinear optimization problems in which multiple simultaneous objective functions can only be observed with stochastic error, for example, as output from a Monte Carlo simulation model. The solution to a MOSO problem is the efficient set, which is the set of all feasible decision points that map to nondominated points in the objective space. For problems with two objectives, we propose the retrospective partitioned epsilon-constraint with relaxed local enumeration (R-PERLE) algorithm. R-PERLE is designed for simulation efficiency and provably converges to a local efficient set under appropriate regularity conditions. It uses a retrospective approximation (RA) framework and solves each resulting biobjective sample-path problem only to an error tolerance commensurate with the sampling error. R-PERLE uses the subalgorithm RLE to certify it has found a sample-path approximate local efficient set. We also propose R-MinRLE, which is a provably convergent benchmark algorithm for problems with two or more objectives. R-PERLE performs favorably relative to R-MinRLE and the current state of the art, MO-COMPASS, in our numerical experiments. This work points to a family of RA algorithms for MOSO on integer lattices that employ RLE to certify sample-path approximate local efficient sets and for which we provide the convergence guarantees.