Optimization Techniques for Solving Complex Problems

CHAPTER 12

Tools for Tree Searches: Branch-and-Bound and A* Algorithms

C. LEÓN, G. MIRANDA, and C. RODRÍGUEZ

Universidad de La Laguna, Spain

12.1 INTRODUCTION

Optimization problems appear in all aspects of our lives. In a combinatorial optimization problem, we have a collection of decisions to make, a set of rules defining how such decisions interact, and a way of comparing possible solutions quantitatively. Solutions are defined by a set of decisions. From all the feasible solutions, our goal is to select the best. For this purpose, many search algorithms have been proposed. These algorithms search among the set of possible solutions (search space), evaluating the candidates and choosing one as the final solution to the problem. Usually, the search space is explored following a tree data structure. The root node represents the initial state of the search, when no decision has yet been made. For every decision to be made, a node is expanded and a set of children nodes is created (one for each possible decision). We arrive at the leaf nodes when all the problem decisions have been taken. Such nodes represent a feasible solution. The tree structure can be generated explicitly or implicitly, but in any case, the tree can be explored in different orders: level by level (breadth-first search), reaching a leaf node first and backtracking (depth-first search), or at each step choosing ...