A Partition-Based Optimization Approach for Level Set Approximation: Probabilistic Branch and Bound

We present a partition-based random search optimization algorithm, called probabilistic branch and bound (PBnB), to approximate a level set that achieves a user-defined target. Complex systems are often modeled with computer simulations, both deterministic and stochastic, and a decision-maker may desire a set of near-optimal solutions, such as solutions with performance metrics in the best 10% overall, instead of a single estimate of a global optimum. Our approach is valid for black-box, ill-structured, noisy function evaluations, involving both integer and real-valued decision variables. PBnB iteratively maintains, prunes, or branches subregions of a bounded solution space based on an updated confidence interval of a target quantile. Finite-time probability bounds are derived on the maximum volume of incorrectly maintained or incorrectly pruned regions. Thus, the user has a statistical quantification of the output. For example, with probability greater than 0.9, the final maintained subregion is inside the target level set with the volume of incorrectly maintained points less than 2% of the volume of the initial set. Numerical results on noisy and non-noisy test functions demonstrate the performance of the PBnB algorithm. Tests on a sphere function, with spherical level sets, allow a comparison between the theoretical bounds and numerical results. PBnB has been applied to several application areas including: weather impacts on air traffic flow management; policy decisions on screening and treatment budget allocation for hepatitis C; combining portable ultrasound machines with reserved MRI usage for orthopedic care; and optimizing water distribution networks using simulation.