Bi-objective Stochastic Simulation Optimization on Integer Lattices via Scalarization

Abstract

We address the challenging problem of multiobjective optimization via stochastic simulation over a discrete design space. We consider the setting where objective functions are expensive black-box simulations corrupted by heteroscedastic noise, and the decision space is usually too large for exhaustive enumeration. Existing methods often struggle to balance three competing needs: scalable surrogate modeling on discrete domains, principled handling of simulation noise (specifically regarding the uncertainty of the current best solution), and efficient navigation of the multiobjective landscape. Our proposed framework extends the single-objective Complete Expected Improvement acquisition function to the bi-objective case. Our contribution is threefold: (1) we employ Gaussian Markov Random Field surrogates to exploit the integer lattice structure; (2) we use ParEGO-style scalarizations but restrict them to linear to preserve the Gaussianity of the posterior, allowing us to derive a closed-form scalarized acquisition function that explicitly accounts for the covariance between the candidate solution and the noisy incumbent. (3) To maximize this acquisition function, we integrate a discrete Genetic Algorithm with specialized local and jump mutation operators as the inner optimizer. We benchmark our approach against an adaptation of state-of-the-art methods on noisy variants of standard test functions, showing faster early convergence while retaining computational tractability.