A Computational Study of Probabilistic Branch and Bound with Multilevel Importance Sampling

Hao Huang, Pariyakorn Maneekul, Danielle F. Morey, Zelda B. Zabinsky, Giulia Pedrielli

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Probabilistic branch and bound (PBnB) is a partition-based algorithm developed for level set approximation, where investigating all subregions simultaneously is a computational costly sampling scheme. In this study, we hypothesize that focusing branching and sampling on promising subregions will improve the efficiency of the PBnB algorithm. Two variations to Original PBnB are proposed: Multilevel PBnB and Multilevel PBnB with Importance Sampling. Multilevel PBnB focuses its branching on promising subregions that are likely to be maintained or pruned, as opposed to Original PBnB that branches more subregions. Multilevel PBnB with Importance Sampling attempts to further improve this efficiently by combining focused branching with a posterior distribution that updates iteratively. We present numerical experiments using benchmark functions to compare the performance of each PBnB variation.

Original languageEnglish (US)
Title of host publicationProceedings of the 2022 Winter Simulation Conference, WSC 2022
EditorsB. Feng, G. Pedrielli, Y. Peng, S. Shashaani, E. Song, C.G. Corlu, L.H. Lee, E.P. Chew, T. Roeder, P. Lendermann
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages12
ISBN (Electronic)9798350309713
StatePublished - 2022
Externally publishedYes
Event2022 Winter Simulation Conference, WSC 2022 - Guilin, China
Duration: Dec 11 2022Dec 14 2022

Publication series

NameProceedings - Winter Simulation Conference
ISSN (Print)0891-7736


Conference2022 Winter Simulation Conference, WSC 2022

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Computer Science Applications


Dive into the research topics of 'A Computational Study of Probabilistic Branch and Bound with Multilevel Importance Sampling'. Together they form a unique fingerprint.

Cite this