@article{Yin2022, 
author = {Ruyang Yin and Jiping Xing and Pengli Mo and Nan Zheng and Zhiyuan Liu},
title = {BO-B&B: A hybrid algorithm based on Bayesian optimization and branch-and-bound for discrete network design problems},
year = {2022},
journal = {Electronic Research Archive},
volume = {30},
number = {11},
pages = {3993-4014},
keywords = {Bayesian optimization, branch-and-bound, discrete network design problem, simulation-based optimization},
url = {https://www.sciopen.com/article/10.3934/era.2022203},
doi = {10.3934/era.2022203},
abstract = {A discrete network design problem (DNDP) is conventionally formulated as an analytical bi-level programming problem to acquire an optimal network design strategy for an existing traffic network. In recent years, multimodal network design problems have benefited from simulation-based models. The nonconvexity and implicity of bi-level DNDPs make it challenging to obtain an optimal solution, especially for simulation-related models. Bayesian optimization (BO) has been proven to be an effective method for optimizing the costly black-box functions of simulation-based continuous network design problems. However, there are only discrete inputs in DNDPs, which cannot be processed using standard BO algorithms. To address this issue, we develop a hybrid method (BO-B&B) that combines Bayesian optimization and a branch-and-bound algorithm to deal with discrete variables. The proposed algorithm exploits the advantages of the cutting-edge machine-learning parameter-tuning technique and the exact mathematical optimization method, thereby balancing efficiency and accuracy. Our experimental results show that the proposed method outperforms benchmarking discrete optimization heuristics for simulation-based DNDPs in terms of total computational time. Thus, BO-B&B can potentially aid decision makers in mapping practical network design schemes for large-scale networks.}
}