Branch and Bound - Complete EnumerationAn Enumeration TreeOn complete enumerationSlide 4Branch and Bound (B&B) algorithmBranch and Bound (B&B) algorithm – contd.Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Branch and BoundSlide 15Slide 16Slide 17Slide 18Slide 19Slide 20Summary so farSlide 22Getting a better boundSlide 24Slide 26Slide 27Slide 28Finishing UpLessons LearnedExample of Branch-and-BoundUtilizing the information about the optimal solution of the LP-relaxationBranching stepBranching step (graphically)Solution treeNext branching step (graphically)Solution tree (cont.)Slide 38Solution tree (final)Branch and Bound - Complete Enumeration•Systematically considers all possible values of the decision variables. –If there are n binary variables, there are 2n different ways.•Usual idea: iteratively break the problem in two. At the first iteration, we consider separately the case that x1 = 0 and x1 = 1.An Enumeration Treex1 = 0 x1 = 1x2 = 0x2 = 1x2 = 0x2 = 1x3 = 0 x3 = 1 x3 = 0 x3 = 1 x3 = 0 x3 = 1 x3 = 0 x3 = 1Original problemOn complete enumeration•Suppose that we could evaluate 1 billion solutions per second.•Let n = number of binary variables•Solutions times (approx.)–n = 30, 1 second–n = 40, 18 minutes–n = 50 13 days–n = 60 31 yearsOn complete enumeration•Suppose that we could evaluate 1 trillion solutions per second, and instantaneously eliminate 99.9999999% of all solutions as not worth considering•Let n = number of binary variables•Solutions times–n = 70, 1 second–n = 80, 17 minutes–n = 90 11.6 days–n = 100 31 yearsBranch and Bound (B&B) algorithm5Branch and Bound (B&B) algorithm – contd.6Branch and Bound (B&B) algorithm – contd.7Branch and Bound (B&B) algorithm – contd.8Branch and Bound (B&B) algorithm – contd.Exhaustive Search1. function Fk(b)2. if k = n then return f(b)3. Else4. Begin5. bk+1 := 0; u := Fk+1(b)6. bk+1 := 1; v := Fk+1(b)7. return max(u, v)8. end9. Explanation: In line 2 we handle the case when all coordinates are fixed, i.e., we have arrived at a leaf of the search tree. In this case bn(b) = {b}; so the maximum over this set can only be f(b). If k < n then in lines 5 and 6 we compute recursively the function for two possible cases (branch): when the next coordinate is fixed at 0 (line 5) and when it is fixed at 1 (line 6). The maximum of the two gives the value of Fk(b) in line 7, since this is the maximum over the set when the (k + 1)th coordinate is not fixed, only the first k. What guarantees that the recursion ends after a finite number of steps? This is guaranteed by the fact that the recursive call is always made for a larger value of k and when the largest value k = n is reached then there is no more recursive call.9Branch and Bound (B&B) algorithm – contd.10Branch and Bound (B&B) algorithm – contd.Branch and Bound1. function Fk(b)2. if k = n then3. begin4. if f(b) > maxlow then maxlow := f(b)5. return f(b)6. end7. else8. if Uk(b) > maxlow then9. Begin10. bk+1 := 0; u := Fk+1(b)11. bk+1 := 1; v := Fk+1(b)12. return max(u; v)13. End14. else return maxlow11Branch and Bound (B&B) algorithm – contd.Explanation. Observe that if we remove lines 4, 8 and 14 then we exactly get back the exhaustive search (ignoring the unnecessary begin-end pairs). Thus, let us take a closer look how these lines change the exhaustive search.In the case k = n the only change is that before returning f(b) we update the value of maxlow in line 4: if the new function value is larger then the old value of maxlow, then this larger value will be the new best lower bound on the optimum, otherwise the old one remains. The most essential difference is in line 8, this is the bounding. Here the idea is that we only make the recursive calls if the upper bound Uk(b) is larger than the current value of maxlow. Why we can do this without losing anything?Because if the condition in line 8 is not satisfied, thenmaxlow ≥ Uk(b) ≥ Fk(b) Must hold.This means that from this parameter combination (k; b) we cannot hope improvement on the best value found so far, since the maximum in this subtree of the search tree (i.e., Fk(b)) is already known to be not more than maxlow, so it makes no sense to explore this subtree. Thus, in this case we do not make any recursive call and return maxlow in line 14 (just to return something).12Branch and Bound (B&B) algorithm – contd.Note that for the above bounding step we need to compute the value of Uk(b), but we assumed that for this an independent subroutine is available. The savings may be essential if this subroutine is much faster then the exhaustive recursive algorithm. This is typically the case in the successful applications of B&B.13Branch and BoundThe essential idea: search the enumeration tree, but at each node1. Solve the linear program at the node2. Eliminate the subtree (fathom it) if1. The solution is integer (there is no need to go further- why?) or2. The best solution in the subtree cannot be as good as the best available solution (the incumbent- how does that happen?) or3. There is no feasible solutionBranch and Bound144 3/7Solution at node 1: x1 =1 x2 = 3/7 x3 = x4 = x5 = 0 x6 =1 z = 44 3/7 Node 1 is the original LP Relaxationmaximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6subject to 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6 14 0 xj 1 for j = 1 to 6The IP cannot have value higher than 44 3/7.Branch and Bound12x1 = 044 3/744Solution at node 2: x1 = 0 x2 = 1 x3 = 1/4 x4 = x5 = 0 x6 = 1 z = 44 Node 2 is the original LP Relaxation plus the constraint x1 = 0.maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6subject to 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6 14 0 xj 1 for j = 1 to 6, x1 = 0Branch and Bound12x1 = 044 3/744Node 3 is the original LP Relaxation plus the constraint x1 = 1.3x1 = 1The solution at node 1 was x1 =1 x2 = 3/7 x3 = x4 = x5 = 0 x6 =1 z = 44 3/7 Note: it was the best solution with no constraint on x1. So, it is also the solution for node 3. (If you add a constraint, and the old optimal solution is feasible, then it is still optimal.) 44 3/7Branch and Bound12 3x1 = 0 x1 = 144 3/74444 3/7Solution at node 4: 0 0 1 0 1 1 z = 42
View Full Document
Unlocking...