Branch_and_Bound_PPT_Data Structures and algorithms.pptx

Branch and bound algorithms

1. Unit 5 : Branch and Bound

2. Syllabus Introduction to Branch and Bound - Methods: Control abstractions for Least Cost Search, Bounding, FIFO branch and bound, and LC branch and bound. Branch and Bound combined with Dynamic Programming like Job Scheduling, Branch and Bound  with Backtracking like subset sum problem .  Applications of Branch and Bound in Real-World Problems -Job Assignment Problem, 15 puzzle problem –An example.

3. Introduction Branch & Bound Algorithm Branching is the process of generating sub problems. Bounding refers to ignoring partial solutions that cannot be better than the current best solution. It is a search procedure to find the optimal solution. It eliminates those parts of a search space which does not contain better solution (Pruning). In this method we basically extend the cheapest partial path.

4. Algorithm design paradigm for combinatorial optimization . Explores a state-space tree of candidate solutions . Uses pruning to reduce search space.

5. Control Abstraction for Least Cost (LC) Branch and Bound Approach Least Cost (LC) Branch and Bound Selects the node with the least cost (lowest lower bound ). Expands this node and generates children . Updates best solution and prunes nodes with higher cost.

6. What is Control Abstraction ? Controls search process: storing, selecting, expanding, and pruning nodes . Maintains a priority queue sorted by cost . Abstracts traversal of the search tree for efficient exploration.

7. How Control Abstraction Works in Least Cost Branch & Bound Initialize with root node. Select node with least lower bound. Expand node to generate children. Prune nodes exceeding best cost. Repeat until no live nodes remain.

8. Example Problem - Assignment Problem Task 1 Task 2 Task 3 Person 1 9 2 7 Person 2 6 4 3 Person 3 5 8 1 Goal: Assign each person to one task minimizing total cost. Step 1 - Initialization and Root Node No assignments, cost lower bound = 0. Live nodes list contains root . Step 2 - Branching from Root Assign Person 1 → Task 1 (cost 9 ) Assign Person 1 → Task 2 (cost 2 ) Assign Person 1 → Task 3 (cost 7 ) Calculate lower bounds for each child . Add children to live nodes list.

9. Step 3 – Select Least Cost Node and Expand Select node with lowest cost e.g . Person 1 → Task 2 (cost 2 ). Assign Person 2 → remaining tasks . Generate child nodes with lower bounds . Add to live nodes.

10. Step 4 - Continue Until Solution Always pick node with least lower bound . Prune nodes with cost above best solution . Update best solution when complete assignments are found. Repeat until no nodes left.

11. LC Branch and Bound selects nodes by least cost. Control abstraction manages node list and pruning. Efficiently finds optimal solution by exploring promising paths. Useful in combinatorial optimization problems like assignment problem.

12. Key Definitions • Live Node: Generated but children not yet explored • E-Node: Live node whose children are being explored • Dead Node: Node that will not be explored further • Heuristic: Strategy to improve efficiency (rule of thumb)

13. Assignment Problem (Branch and Bound) Q . Consider 4 workers corresponding to 4 jobs . Person Job 1 Job 2 Job 3 Job 4 a 9 2 7 8 b 6 4 3 7 c 5 8 1 8 d 7 6 9 4

14. Search Strategies • FIFO (BFS-like): Uses Queue • LIFO (DFS-like): Uses Stack • LC (Least Cost): Uses ranking function to select next node

15. FIFO Branch and Bound First-In-First-Out is an approach to the branch and bound problem that uses the queue approach to create a state-space tree. In this case, the breadth-first search is performed, that is, the elements at a certain level are all searched, and then the elements at the next level are searched, starting with the first child of the first node at the previous level. For a given set {A, B, C, D}, the state space tree will be constructed as follows :

16. The above diagram shows that we first consider element A, then element B, then element C and finally we'll consider the last element which is D. We are performing BFS while exploring the nodes . So, once the first level is completed. We'll consider the first element, then we can consider either B, C, or D. If we follow the route then it says that we are doing elements A and D so we will not consider elements B and C. If we select the elements A and D only, then it says that we are selecting elements A and D and we are not considering elements B and C. Selecting element A

17. Now, we will expand node 3, as we have considered element B and not considered element A, so, we have two options to explore that is elements C and D. Let's create nodes 9 and 10 for elements C and D respectively. Considered element B and not considered element A

18. Now, we will expand node 4 as we have only considered elements C and not considered elements A and B, so, we have only one option to explore which is element D. Let's create node 11 for D . Considered elements C and not considered elements A and B

19. Till node 5, we have only considered elements D, and not selected elements A, B, and C. So, We have no more elements to explore, Therefore on node 5, there won't be any expansion . Now, we will expand node 6 as we have considered elements A and B, so, we have only two option to explore that is element C and D. Let's create node 12 and 13 for C and D respectively .

20. Now, we will expand node 7 as we have considered elements A and C and not consider element B, so, we have only one option to explore which is element  D. Let's create node 14 for D .

21. Till node 8, we have considered elements A and D, and not selected elements B and C, So, We have no more elements to explore, Therefore on node 8, there won't be any expansion.

22. Now, we will expand node 9 as we have considered elements B and C and not considered element A, so, we have only one option to explore which is element D. Let's create node 15 for D .

23. Least Cost (LC) Search • Ranking function: c(x) = f(h(x)) + g(x) - h(x): Cost to reach node - g(x): Estimate to reach answer • Algorithm LC Search uses Least() and Add() to explore nodes • BFS and DFS are special cases of LC-search

24. Bounding • Bounding helps prune unnecessary branches • Cost function c(x) provides lower bound • If c(x) > upper bound → node pruned • Updated when new answer nodes are found

25. FIFO Branch and Bound • Uses queue structure (BFS style) • Upper bound updated when better solutions found • Example: Job Sequencing Problem

26. Job Sequencing with deadline Jobs 1 2 3 4 Penalty 5 10 6 3 Deadline 1 3 2 1 Time 1 2 1 1

27. 15 puzzle problem The 15 Puzzle is a sliding puzzle that consists of a 4×4 grid with 15 numbered square tiles and one blank space . The objective is to move tiles one at a time (sliding into the blank space) until the tiles are arranged in order : Goal State: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 _

28. Properties State Space: All possible configurations of the 16 positions (16! possibilities, but only half are solvable). Operators: Move up, down, left, right by sliding a tile into the blank. Goal Test: Current configuration matches the goal configuration. Path Cost: Typically, each move costs 1.

29. Solving Methods 1. Brute Force Search Generate all possible moves until the goal is found (impractical due to large state space). 2. Branch and Bound Construct a search tree where nodes are states. Use a cost function : f(n)=g(n)+ h(n) where g(n ): cost so far (number of moves taken), h(n ): heuristic (e.g., misplaced tiles or Manhattan distance). Expand nodes with the least cost first. 3. Dynamic Programming Store already explored states (via hashing) to avoid recomputation . Useful when many repeated subproblems occur. 4. A* Search (Most Common) Uses Branch and Bound with heuristic . Popular heuristics: Misplaced Tiles: Count tiles out of place. Manhattan Distance: Sum of distances each tile is away from its goal position. Linear Conflicts / Pattern Databases: More advanced heuristics.

30. Applications Tests AI search strategies . Demonstrates Branch & Bound, DP, A*, IDA* . Basis for solving larger puzzles (e.g., 24 puzzle).

31. Algorithm: 15 Puzzle using Branch & Bound (A*) Input: Initial state (4×4 grid with tiles + blank). Goal state (tiles ordered from 1 to 15, blank at the end). Output: Sequence of moves leading to the goal state.

32. Step 1: Define the Cost Function f(n)=g(n)+h(n)f(n) = g(n) + h(n)f(n)=g(n)+h(n) g(n)g(n)g(n): cost to reach state nnn (number of moves made). h(n)h(n)h(n): heuristic cost (e.g., Manhattan distance of tiles from goal). Step 2: Initialize Create a priority queue (PQ) (min-heap) ordered by f(n)f(n)f(n). Insert the initial state into PQ with g=0g=0g=0, h= h=h= heuristic(initial). Maintain a visited set to avoid revisiting states. Step 3: Search Process While PQ is not empty: a. Remove the node nnn with the lowest f(n)f(n)f(n) from PQ. b. If nnn is the goal state , return the path (solution found). c. Generate all valid moves by sliding a tile into the blank (up, down, left, right). d. For each child state: Compute g(child)=g(n)+1g(child) = g(n) + 1g(child)=g(n)+1. Compute h(child)h(child)h(child) (Manhattan distance or misplaced tiles). Compute f(child)=g(child)+h(child)f(child) = g(child) + h(child)f(child)=g(child)+h(child). If child not in visited set OR has lower cost → insert into PQ. e. Add nnn to visited set. Step 4: Termination If PQ becomes empty without finding the goal → puzzle unsolvable. Otherwise, return the reconstructed path from start to goal.

33. example given initial state 1 2 3 4 5 6 _ 8 9 10 7 11 13 14 15 12 Goal state 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 _

34. X4=1 =70 Sum of Subset Problem by Backtracking

35. Job scheduling using Dynamic Programming

36. Job Start Time End Time Profit Value a 1 4 3 b 2 6 5 c 4 7 2 e 6 8 6 d 5 9 4 f 7 10 8 Sort jobs as per end time

37. Name a b c e d f Time (1,4) (2,6) (4,7) (6,8) (5,9) (7,10) Profit 3 5 2 6 4 8 □ □ □ □ □ □

38. LC Branch and Bound • Combines Least-Cost strategy with bounding • Selects next E-node with minimum estimated cost • Example: Graph traversal with LC bounding

39. Traveling Salesperson Problem (TSP) • Goal: Visit all nodes once and return to start with minimum cost • Branch and Bound reduces search space • Steps: Matrix reduction, calculate lower bounds, prune paths • Example: LC Branch & Bound achieves cost = 28

40. 0/1 Knapsack Problem • Branch and Bound calculates upper and lower bounds • Convert maximization to minimization by negating profit • Example: Items (10,10,12,18), Capacity=15 • Solution = (1,1,0,1), Max profit = 38

41. Applications & Comparison • Optimization problems: TSP, Knapsack, Scheduling • Strengths: Efficient pruning, finds optimal solution • Limitations: Complexity remains exponential

42. Graph Coloring using Backtracking Graph coloring is a concept in graph theory, a branch of discrete mathematics that studies graphs—mathematical structures used to model pairs of objects that are related in some way. Graph coloring is specifically concerned with assigning "colors" to certain elements of a graph following specific rules. Key Concepts Graph Basics: A graph consists of a set of vertices (nodes) and edges (connections) between vertices. If two nodes are connected by an edge, they are called adjacent. Graph Coloring: Graph coloring involves assigning colors to graph elements such that no two adjacent elements share the same color. The most common type is vertex coloring, where the rule is that no two connected vertices can have the same color. Chromatic Number: The chromatic number of a graph is the smallest number of colors needed to color the graph according to the rules. For example, a triangle (3 connected vertices) requires 3 colors so that no two connected vertices are the same. Applications: Scheduling problems: Assigning time slots to tasks so that no conflicting tasks overlap. Map coloring: Coloring countries on a map so that adjacent countries have different colors. Register allocation in compilers: Efficiently assigning variables to a limited number of CPU registers. Special Graph Colorings: Edge coloring: Assign colors to edges so that no two edges sharing a vertex have the same color. Face coloring: Applied in planar graphs where regions (faces) are colored differently.