Optimization Techniques: B&B vs Backtracking
Learn how Branch and Bound (B&B) and Backtracking algorithms differ in searching state space trees exhaustively for optimization problems. Understand the basic idea of using estimate functions to guide the search and explore the assignment problem example. Dive into the general recursive B&B template and discover how lower bounds help find optimal solutions efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Branch and bound As backtracking, B&B searches the state space tree exhaustively. Backtracking depth-first searches the state space tree. B&B breadth-depth searches the state space tree. B&B is only useful for optimization problems.
Basic idea Use an estimate function to select a branch that has a better chance to lead to an optimal solution. Use the estimate function as a bounding function to prune the state space tree. Lower bounds are commonly used as the estimate and bounding functions. Moreover, a solution to a relaxation of the original problem could be a common lower bound.
General recursive b&b template Assume that array x[n] is global. void build(int k) { Declare local arrays for storing choices and estimates; Compute estimates for all choices of the k'th component; Sort choices according to estimates; while (more choices && the next estimate is better than the current best) { x[k] = the next choice; if (x[1..k] satsifies the criterion function) { if (k is the last component) update the current best; else build(k+1) } }
Assignment problem There are n agents to be assigned to n tasks, each agent having exactly one task to perform. The cost of assigning agent i to task j is ci,j. The problem is to assign agents to tasks so as to minimize the total cost of executing n tasks.
1 2 3 4 a 11 12 18 40 b 14 15 13 22 c 11 17 19 23 d 17 14 20 28 Upper bound on the answer : (Any assignment) a:1, b:2, c:3, d:4 = 11+15+19+28 = 73 Lower bound (sum smallest elements of columns) 11+12+13+22 = 58 58<=answer <=73
Explore a tree whose nodes correspond to partial assignment. Use lower bound to guide the search, I.e. use lower bounds as estimates. 60 = 11+14+13+22 a:1 58 a:2 1 2 3 4 a 11 12 18 40 65 a:3 b 14 15 13 22 a:4 78 c 11 17 19 23 d 17 14 20 28
1 2 3 4 a 11 12 18 40 b 14 15 13 22 c 11 17 19 23 d 17 14 20 28 a:2,b:1 68 = 12+14+19+23 60 a:1 a:2,b:3 59 a:2 58 a:2,b:4 64 65 a:3 a:4 78
a:2,b:1 68 60 a:1 a:2,b:3,c:1,d:4 64 a:2,b:3 a:2 59 65 58 a:2,b:3,c:4,d:1 a:2,b:4 64 65 a:3 a:4 78
68 a:1,b:3,c:2,d:4 a:1,b:2 69 a:1 a:1,b:3 60 61 a:1,b:3,c:4,d:2 61 66 a:1,b:4 68 a:2,b:1 a:2,b:3,c:1,d:4 64 a:2,b:3 a:2 59 58 a:2,b:3,c:4,d:1 65 a:2,b:4 64 65 a:3 a:4 78
Traveling salesperson problem (TSP) Given a finite number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting every city once and only once and returning to the starting city.
TSP example Suppose the cost can for traveling between cities is described by the following cost matrix. 1 2 3 4 5 0 14 0 5 7 7 4 7 0 9 10 8 7 0 4 20 7 16 2 0 1 14 4 11 18 2 C = 3 4 17 5 Each entry is the cost of traveling from a city in the ith row to one in the jth column. The zeros down the diagonal indicate that you cannot travel from a city to itself
Lower bound on TSP tour 1 2 3 4 5 0 14 0 5 7 7 4 7 0 9 10 8 7 0 4 20 7 16 2 0 1 14 4 11 18 2 C = 3 4 17 5 Every tour must leave every node and arrive at every node. [(4+7+4+2+4)+(4+5+4+4+2)]/2=40/2=20
Lower Bound on TSP Tour Once some edges are specified we can incorporate that information and calculate a lower bound on that partial solution. If we knew the partial tour 1-3-4 then the lower bound on the partial solution would be: 4+7+[(7+2+7)+(14+7+2)]/2 = 30.5 1 2 3 4 5 0 14 0 5 7 7 4 7 0 9 10 8 7 0 4 20 7 16 2 0 1 14 4 11 18 2 C = 3 4 17 5
TSP: The state space tree 1 20 1,2 1,4 1,3 1,5 31 29 24 41 1,3,4 1,3,5 1,4,2 1,4,3 1,4,5 1,3,2 30.5 40.5 40 41.5 29 24 1,4,5,3,2 1,4,5,2,3 1,3,2,4,5 1,3,2,5,4 48 30 37 31
The Graph Partitioning Problem (GPP) Given a weighted, undirected graph G=(V,E). The problem is to partition V into two disjoint subsets V1 and V2 of equal size such that the sum of weights of edges connecting vertices belonging to different subsets is as small as possible.
Upper bound on GPP 1 2 3 4 5 6 0 14 0 5 8 7 12 4 5 0 9 10 8 9 0 4 25 20 7 17 4 0 6 15 12 4 25 6 0 1 14 4 10 20 15 2 3 4 17 4 5 6 Upper bound on the answer : (Any partition) {{1,2,3}, {4,5,6}}:10+20+15+8+7+12+9+17+4 = 102
Lower bound on GPP 1 2 3 4 5 6 0 14 0 5 8 7 12 4 5 0 9 10 8 9 0 4 25 20 7 17 4 0 6 15 12 4 25 6 0 1 14 4 10 20 15 2 3 4 17 4 5 6 sum smallest 3 elements of columns 28 20 13 21 17 22 Lower bound (sum of smallest 3 sums) 20+13+17 = 50 50<=answer <=102
Lower bound on GPP 1 2 3 4 5 6 0 14 0 5 8 7 12 4 5 0 9 10 8 9 0 4 25 20 7 17 4 0 6 15 12 4 25 6 0 1 14 4 10 20 15 2 3 4 17 4 5 6 14+5+7 20+4+6 - 26 13 22 30 25 60 = 13+22+25 1 sum i th element and smallest 2 elements of columns 28 - 13 21 17 22 51 = 13+21+17 2 63 = 20+21+22 28 20 - 21 27 22 3 54 = 20+17+17 4 28 20 17 - 17 35
Lower bound on GPP 1 2 3 4 5 6 0 14 0 5 8 7 12 4 5 0 9 10 8 9 0 4 25 20 7 17 4 0 6 15 12 4 25 6 0 1 14 4 10 20 15 2 3 4 17 4 5 6 14+4+10 12+4+6 28 - - 21 28 22 1 71 = 21+22+28 3 51 2 28 - 18 - 17 41 4 63 = 28+18+17 3 69 = 26+21+22 38 - 26 21 - 22 5 4
GPP: The state space tree {} {1} {3} {2} {4} 60 63 51 54 {1,2} {1,3} {1,4} {1,5} {2,3} {2,4} {2,5} {3,4} {3,5} {4,5} 66 74 74 72 71 63 69 75 63 84 {1,2,3} {1,2,4} {1,2,5} {1,2,6} {1,5,6} {2,5,6} {2,4,5} {2,3,4} {2,3,5} {2,3,6} {2,4,6} {3,5,6} 102 101 81 89 97 112 97 81 105 74 101 118
A Programming project Implement the branch and bound assignment algorithm. You are required to use b&b template, build. Besides all solutions found, you need to print out the partial assignments with the estimates right after you compute and sort estimates. (Try instructor s program for sample outputs.) Use the following test data. 1. 2. 3. 1 2 3 4 5 4. a 11 17 8 16 20 b 9 7 12 6 15 c 13 16 15 12 16 d 21 24 17 28 26 e 14 10 12 11 15
