Empirical stochastic branch-and-bound for optimization via simulation

Abstract

This article introduces a new method for discrete decision variable optimization via simulation that combines the nested partitions method and the stochastic branch-and-bound method in the sense that advantage is taken of the partitioning structure of stochastic branch-and-bound, but the bounds are estimated based on the performance of sampled solutions, similar to the nested partitions method. The proposed Empirical Stochastic Branch-and-Bound (ESB&B) algorithm also uses improvement bounds to guide solution sampling for better performance. A convergence proof and empirical evaluation are provided. [Supplementary materials are available for this article. Go to the publisher’s online edition of IIE Transaction for datasets, additional tables, detailed proofs, etc.]

Keywords:

• Stochastic branch-and-bound
• optimization via simulation