Branch and Bound (B&B)
Branch and Bound (B&B) algorithms are exact anytime optimization algorithms. They iteratively divide the search space ${\mathbb{X}}$ into smaller and smaller subsets $X\subseteq\mathbb{X}$. For each subset $X$, they maintain a lower bound $L(X)$ for the objective values of any element $x\in X$. They also maintain an upper bound $U$ of the objective value of the best possible solution. Initially, $U=\infty$. If a subset contains only a single solution $x_s$, then we compute the objective value $f(x_s)$ of $x_s$ and update $U\gets\min{U,f(x_s)}$. Of course, from now on, we only need to consider subsets $X$ with $L(X)<U$, because otherwise, they cannot contain any solution better than $x_s$.
Publications
- Thomas Weise (汤卫思), Yan JIANG (江炎), Qi QI (齐琪), and Weichen LIU (刘伟臣): A Branch-and-Bound-Based Crossover Operator for the Traveling Salesman Problem. International Journal of Cognitive Informatics and Natural Intelligence (IJCINI) 13(3):1-18. Autumn 2019.
- Yan JIANG (江炎), Thomas Weise (汤卫思), Jörg Lässig, Raymond Chiong, and Rukshan Athauda: Comparing a Hybrid Branch and Bound Algorithm with Evolutionary Computation Methods, Local Search and their Hybrids on the TSP. IEEE Symposium on Computational Intelligence in Production and Logistics Systems (CIPLS'2014), part of the IEEE Symposium Series on Computational Intelligence (SSCI'2014), December 9-12, 2014, Orlando, FL, USA, pages 148-155. Los Alamitos, CA, USA: IEEE Computer Society Press.