1.204 Lecture 17 Branch and bound: Method Method Warehouse location problem Breadth first search • Breadth first search managges E-nodes in the branch and bound tree – An E node is the node currently being explored – In breadth first search, E-node stays live until all its children have been generated – The children are placed on a queue, stack or heap • Typical strategies to select E-nodes – Choose node with largest upper bound (in a maximization problem),), using a heappp g – Choose node likely to be optimal, even if we can’t prove it’soptimal immediately • Use problem specific, heuristic rule • It can be a previous optimal result to similar problem – Choose ‘quick improvement’ node based on a gradient estimate from the upper and lower bounds on a node 1Several are used to decide which–Branching on nodes • Several strategies are used to decide whichstrategies branch (0 or 1) to take: – User specified rules. Again, heuristics are used – Set a group of 0-1 variables to given values, not just one • This seems to perform better in many problems • Our code in this lecture does not do this • Other strategies to improve performance: – If dual can be computed If dual can be computed, it provides a lower boundit provides a lower bound – Bound tightening, such as truncation (like we used in the last lecture on the knapsack problem) – Adding linear constraints (0<=x<=1) in subproblems in hopes that integer answers are obtained – Greedy heuristics, including dual descent and others… Facility location problem Warehouse 1 Customer 4 Customer 1 Customer 3 Customer 2 8 1814 10 Warehouse 0 Warehouse 2 Warehouse 3 Customer 0 3 e.g., Amazon Intel Tropicana 23Facility location exampleWarehouse Fixed costkf[k]01 23 4Cost to ship to customer j• Set of 4 possible warehouses (0-3) to serve 5 possible customers (0-4)[]0431081814169465526126104838865129()• Table gives annual capital (fixed) cost of warehouse if it is built, and the annual cost of shipping to each customer via that warehouse• Decision is whether to build (xi= 1) or not build (xi=0) each warehouse• Objective is to minimize fixed plus shipping costsComputing bounds• Lower (optimistic) bound at each node is sum of:(p )– Minimum transport cost over all built or unknown warehouses– Fixed cost of built warehouses• Upper (pessimistic) bound at each node is sum of– Minimum transport cost over all built warehouses– Fixed cost of built warehouses• Pruning rules– If minimum (pessimistic) savings from building a warehouse are greater than its fixed cost we build itare greater than its fixed cost, we build it– If maximum (optimistic) savings from building a warehouse are less than its fixed cost, we don’t build it• All combinations are feasible in this problem, so there is no reduction in the size of the tree from feasibility constraints– We can introduce capital budget constraints in some casesPruning rules from Akinc, Khumwala•Computational strategy • Start at root node – Apply upper and lower bound at root – Try to lock in or lock out some warehouses • Then create tree node with arbitrary warehouse locked in or out – Apply upper and lower bound at this node – Try to lock in or lock out additional warehouses – Generate children if bounds don’t prune them • Use stack, queue or heapp to hold children ,q • Continue until all E-nodes have been explored – Output optimal solution – Difference between lower and upper bound decreases as algorithm continues • We can stop when the difference is small enough, evenwithout an exact optimal solution Computational example: root node • Root node – All warehouses xi are unknown – Upper bound at root is “infinity”, by convention – Lower bound at root is sum of: • Cost of built warehouses (none) plus • Minimum transport cost over all built or unknownwarehouses, which is all of them. Lower bound= 21 – Use convention: • x= 1 is built warehouse • x= 0 is unknown warehousex= 0 is unknown warehouse • x= -1 is warehouse not built – Thus, root node solution is {0, 0, 0, 0} 45Pruning rules at root• Minimum savings at all warehouses (if warehouse is cheapest, compare it with next cheapest):Warehouse Fixed cost Minimum Pruningkf[k]01234idiiCost to ship to customer j• Maximum savings at all warehouses (compare it with most expensive):Warehouse Fixed cost Maximum PruningCost to ship to customer jkf[k]01234savingsdecision0 4 3 10 8 18 14 5 x0=11 6 9 4 6 5 5 5 None2 6 12 6 10 4 8 1 None3 8 8 6 5 12 9 1 None• Thus we are able to prune the x0branch of the treek f[k] 0 1 2 3 4 savings decision0 4 3 10 8 18 14 11 None1 694655 35None2 6 12 6 10 4 8 24 None3 8 8 6 5 12 9 24 NoneOrange is cheapest warehouse to serve customer; gray is next cheapestTree from rootx= {0,0,0,0}Upper bound= ∞265x0=1 x0=-1 x1=1 x1=-1 x1=1 x1=-1 x2=-1 x2=1 x2=-1 x2=1 PrunedLower bound= 21+0=21x= {1,0,0,0}Upper bound= 53+4=57Lower bound= 21+4=25Generate Enode to left of root:•0122Generate E-node • Generate E-node to left of root: – Warehouse 0 is built (x0= 1 in root solution) • Compute upper and lower bounds at E-node – All customers served from warehouse 0 – Upper bound= 4 (fixed cost) + 53 (transport cost)= 57 • Assume all customers served from warehouse 0 – Lower bound= 4 (fixed cost) + 21 (transport cost) = 25 • Assume customers served from built and unknownAssume customers served from built and unknown warehouses • No further pruning is possible at this node • Arbitrarily branch on warehouse 1. Set x1= 1 E node bounds x= {0,0,0,0} Upper bound= ∞ 2 65 x0=1 x =-1 x1=1 x1=-1 x1=1 x =-1 x2=-1x2=1x =-1 x =1 Pruned Lower bound= 21+0= 21 x= {1,0,0,0} Upper bound= 53+4=57 Lower bound= 21+4=25 x= {1,1,0,0} Upper bound= 23+10=33Upper bound 23+10 33 Lower bound= 21+10=31 67Pruning rules at E-node• Minimum savings at all warehouses:Warehouse Fixed cost Minimum Pruningkf[k]01234idiiCost to ship to customer j• Maximum savings at all warehouses:kf[k]01234savingsdecision0 4 3 10 8 18 14 NA NA1 694655NANA2 612610481None3 88651291NoneWarehouse Fixed cost Maximum Pruningkf[k]01234savingsdecisionCost to ship to customer j• Thus we are able to prune the x2and x3branches of the tree0 4 3 10 8 18 14 NA NA1 694655NANA2 6 12 6 10 4 8 1 x2=-13 88651291x3=-1Yellow is cheapest warehouse to serve customer; gray is next cheapestE node boundsx0=1 x0=-1 Prunedx=