Abstract
Search strategies are used in Branch-and-bound (B&B) algorithms to determine the order to process the nodes in a search tree. A search strategy that has seen frequent success in B&B algorithms is Best First Search (BFS). However, a new search strategy called Cyclic Best First Search with depth contour (CBFS-depth) has been shown to consistently process fewer nodes than BFS on several combinatorial optimization problems. In this paper, we study the properties of search trees under which CBFS-depth may outperform BFS in terms of the average number of nodes explored to prove optimality. To facilitate the study, a search tree model is proposed for minimization problems solved by B&B algorithms which is based on the distributions of nodes in the tree with different lower bounds. Using this model, we estimate the expected number of nodes expanded by CBFS-depth. Additionally, we apply B&B algorithms using both search strategies to trees that are randomly generated according to the proposed model in order to study how the average number of nodes expanded by each search strategy is affected by the search tree. Finally, both search strategies are tested on existing optimization problems to validate the observations from the randomly generated search trees.
Original language | English (US) |
---|---|
Article number | 105129 |
Journal | Computers and Operations Research |
Volume | 126 |
DOIs | |
State | Published - Feb 2021 |
Externally published | Yes |
Keywords
- Branch-and-bound algorithm
- Cyclic best-first search
- Performance comparison
- Search strategies
ASJC Scopus subject areas
- General Computer Science
- Modeling and Simulation
- Management Science and Operations Research