Branch and Bound

[jimin-kiim]

Problem Solving

Modeling - Designing - Implementation - Analyzing

Design Approaches

1. Brute Force
2. Divide and Conquer
3. Dynamic Programming
4. Greedy
5. Backtracking (DFS + pruning)
6. Branch and Bound (BFS + pruning)
7. Approximation

Introduction

• in case of difficult problems, time complexity using DP or BF have no difference so it needs a new design approach.
• difficult problems cannot avoid enumerating all possible combinations, so in order to improve the performance, should find a design approach which can lead the enumerating process to 'more efficient' way.
• Backtracking and Branch and Bound come up from the question "should we check all the enumerations for real?"
  • theses two approaches use the promising function and if it seems to be non-promising, they stop enumerating and prune the tree.
  • Backtracking is doing a DFS traversing and Branch and Bound is doing a BFS traversing of a state-space tree whether each node is promising and if it's not stop examining its child nodes

Backtracking ? or Branch and Bound ?

• if an effective h-value can be found, it's better to use Branch and Bound rather than Backtracking
• since it can prune earlier near the root node
• being proficient, using B&B would be much better so persistent practice is needed

Branch and Bound

• Non-Optimization Problems
  • N-queens Problem, Subset Sum Problem
• Optimization Problems
  • 0/1 KnapSack Problem, Traveling Salesman Problem
  • need bounding function (f = g + h) to find upper bound / lower bound

Design

• Step 1. design promising function
• Step 2. BFS traverse with pruning

Analysis

• we already know that the Time Complexity using Branch and Bound is not that great. its TC is EXP like BF.
• the point we have an interest is an execution time, run time(empirical performance) not TC

[jimin-kiim]

N-Queens Problem

• Non - Optimization Problem
• it doesn't use f = g + h as bounding function
• BFS traversing with pruning by promising function

[jimin-kiim]

TSP

• Traveling Salesman Problem(Traveling Sales Person Problem)
• the most widely used combinatorial optimization problem in computer science
• BF, Greedy can also solve it but for better performance, Branch and Bound would be proper because it cannot eluding enumertion
• minimization optimization
  • h should be underestimating value in order to avoid pruning mistakes
  • 0 < h < h* < infinite
  • h = h* - alpha
  • the smaller the alpha is, the higher pruning power is
  • but it should not be 0 bc if h = 0, it means it doesn't estimate at all
• there are two types of TSP
  • symmetric problem: weight on the edge has no direction
  • asymmetric problem: weight on the edge differs by the direction
• designing great h-value is also key point of designing
  • there can be several options
  • but this time, we decided to use h as (min cost of entering the vertex + min cost of exiting the vertex) / 2
• bounding function : f = g + h
  • g: actual cost. sum of weights of visited edges
  • h: future cost estimation.

[jimin-kiim]

0/1 KS problem

• optimization problem
• 0/1 KS with Branch and Bound