book1

  Solving NP-hard discrete optimization problems to optimality is often an immense job requiring very ecient algorithms, and the B&B paradigm is one of the main tools in construction of these. A B&B algorithm searches the complete space of solutions for a given problem for the best solution. However, explicit enumeration is normally impossible due to the exponentially increasing number of potential solutions. The use of bounds for the function to be optimized combined with the value of the current best solution enables the algorithm to search parts of the solution space only implicitly.