Solving Integer Programs I - Branch and Bound

z Branch and Bound 1 Overview of this lecture z Explain and illustrate branch and bound. – It is the starting point for all solution techniques for integer programming – Lots of research has been carried out over the past 40 years to make it more and more efficient – But, it is an art form to make it efficient. (We shall get a sense why.) – Integer programming is intrinsically difficult. 2 Capital Budgeting Example Investment budget = $14,000 Investment 1 2 3 4 5 6 Cash Required (1000s) $5 $7 $4 $3 $4 $6 NPV added (1000s) $16 $22 $12 $8 $11 $19 maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6 subject to 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6 ≤ 14 xj binary for j = 1 to 6 3 Complete Enumeration z Systematically considers all possible values of the decision variables. – If there are n binary variables, there are 2n different ways. z Usual idea: iteratively break the problem in two. At the first iteration, we consider separately the case that x1 = 0 and x1 = 1. 4 An Enumeration Tree Original problem 1 x1 = 0 Subproblems x1 = 1 2 3 Problem 3. 1. 2. maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6 subject to 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6 ≤ 14 6 xj binary for j = 1 to 6, and x1 = 1 0 5 An Enumeration Tree Original problem Subproblems x1 = 0 x2 = 0 x3 = 0 x3 = 1 x1 = 1 x2 = 0 x2 = 1 x3 = 0 x3 = 1 x3 = 0 x3 = 1 x2 = 1 x3 = 0 x3 = 1 6 On complete enumeration z Suppose that we could evaluate 1 billion solutions per second. z Let n = number of binary variables z Solutions times – n = 30, 1 second – n = 40, 17 minutes – n = 50 11.6 days – n = 60 31 years 7 On complete enumeration z Suppose that we could evaluate 1 trillion solutions per second, and instantaneously eliminate 99.9999999% of all solutions as not worth considering z Let n = number of binary variables z Solutions times – n = 70, 1 second – n = 80, 17 minutes – n = 90 11.6 days – n = 100 31 years 8 Subtrees of an Enumeration Tree Subtree from node 2 1 x1 = 0 x1 = 1 2 x2 = 0 3 x2 = 0 x2 = 1 4 x3 = 0 5 x3 = 1 Subtree from node 6 x3 = 0 x2 = 1 6 x3 = 1 x3 = 0 7 x3 = 1 x3 = 0 x3 = 1 9 The Essence of Branch and Bound z Scan nodes of the “enumeration tree” one at a time. z When scanning a node, see if there is a reason to stop scanning any further. – Perhaps no solution in the subtree is feasible. – Perhaps no solution in the subtree can possibly have a better objective value than some known solution x’. – Fathom (i.e., eliminate subtrees) when possible. 10 The Tree as it evolves if we select the active node with least label. (Breadth first search) 1 x1 = 0 stop searching from a node or create two children x1 = 1 2 3 5 4 x3 = 0 14 14 6 x3 = 1 8 x3 = 0 9 15 16 16 x2 = 1 x2 = 0 x2 = 1 x2 = 0 x3 = 1 10 17 18 18 7 12 11 11 19 20 22 24 x3 = 1 x3 = 0 13 21 23 25 11 Bounding (an upper bound) An IP maximize z = 16x1 + 22x2 + 12x3 subject to 5x1 + 7x2 + 4x3 ≤ 14 xj binary for j = 1 to 3 The linear relaxation of the IP maximize zLP = 16x1 + 22x2 + 12x3 subject to 5x1 + 7x2 + 4x3 ≤ 14 0 ≤ xj ≤ 1 Then z ≤ zLP. for j = 1 to 3 12 An Incumbent The incumbent is the “best available” feasible solution at each point in running the algorithm. Consider: maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6 subject to 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6 ≤ 14 xj binary for j = 1 to 6 We may start the procedure by looking for a good feasible solution. (There are lots of ways to do this.) We will assume that we have found the incumbent: z = 38; x1 = 1; x2 = 1; x3 = x4 = x5 = x6 = 0 13 A method for finding an initial solution for the capital budgeting problem maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6 subject to 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6 ≤ 14 xj binary for j = 1 to 6 First come first served (also known as greedy). Select projects in order until no more projects can be selected while meeting the budget . Select project 1. Select project 2. There is not enough money for any other project. We will use this solution as the first incumbent. z = 38; x1 = 1; x2 = 1; x3 = x4 = x5 = x6 = 0 14 More on the incumbent z We will see that the incumbent is important z As Branch and Bound proceeds, new solutions will be evaluated. If a new solution is better than the current incumbent, it replaces the current incumbent. z So, the incumbent is always the best solution seen so far. 15 Branch and Bound The essential idea: search the enumeration tree, but at each node solve the linear program. Eliminate the subtree at a node (fathom it) if 1. There is no feasible solution for any node in the subtree 2. The best solution of any node in the subtree cannot be better than the best incumbent. z Use bounding to prove this 16 Branch and Bound for 0-1 Integer Programs Node 1 is the original IP 1 44 3/7 The incumbent solution has value 38 Subroblem (1) maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6 subject to 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6 ≤ 14 xj binary for j = 1 to 6 Bound at node 1: from the opt for the LP relaxation x1 =1 x2 = 3/7 x3 = x4 = x5 = 0 x6 =1 z = 44 3/7 The IP cannot have value higher than 44 3/7. 17 Branch and Bound for 0-1 IPs 1 44 3/7 x1 = 1 x1 = 0 44 The incumbent solution has value 38 3 2 Subroblem (2) maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6 subject to 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6 ≤ 14 xj binary for j = 1 to 6, and x1 = 0 Bound for node 2 from the LP relaxation of node 2: x1 = 0 x2 = 1 x3 = 1/4 x4 = x5 = 0 x6 = 1 z = 44 18 Branch and Bound 0-1 IPs 1 x1 = 0 44 2 The incumbent solution has value 38 44 3/7 x1 = 1 3 44 3/7 The bound at node 3 is z = 44 3/7 Note: the solution to the LP relaxation at Node 3 is the same as for Node 1. 19 Node 4 1 x1 = 0 44 2 44 3/7 The incumbent solution has value 38 x1 = 1 3 x2 = 0 42 4 The LP relaxation for subproblem (4) produces the solution: 0 0 1 0 1 1 z = 42 This solution is feasible for the original problem, and is better than our incumbent solution. So, we replace our incumbent solution. 20 Node 4 1 x1 = 0 44 The incumbent solution has value 42 38 44 3/7 x1 = 1 2 3 x2 = 0 42 44 The LP relaxation at node 4 produces the solution: 0 0 1 0 1 1 z = 42 We can now fathom node 4. This means that no other node in the subtree for node 4 will be searched because none can have a better solution than the current incumbent. 21 Nodes 5, 6, 7 1 44 3/7 x1 = 0 44 x2 = 0 42 44 The incumbent solution has value 42 x1 = 1 2 3 x2 = 0 x2 = 1 44 5 44 6 44 3/7 x2 = 1 44 1/3 7 We next solved the LP’s associated with nodes 5, 6, and 7 No new integer solutions were found. None of these nodes gets fathomed. (Why?) 22 Nodes 8 to 13 1 44 3/7 x1 = 0 44 x1 = 1 2 3 x2 = 0 x2 = 1 x2 = 0 42 44 The incumbent solution has value 42 44 x3 = 0 43.75 8 5 44 x3 = 1 43.5 9 x3 = 0 43.25 10 6 44 3/7 x2 = 1 44 1/3 7 x3 = 1 43.8 11 x3 = 0 44.3 12 x3 = 1 13 -∞ 13 We next solved the LP’s associated with nodes 8 -13 There can be no feasible solution for node 13. Fathom it. 23 Summary so far z We have solved 13 different linear programs so far. – One new integer solution found – One subtree fathomed (pruned) because of bounds (node 4) • fathoming means that no other nodes in the subtree will be created. – One subtree fathomed because the solution was infeasible (node 13) z The incumbent solution was changed because we obtained a better solution for the original problem. 24 Branch and Bound 0-1 IPs 1 44 3/7 x1 = 0 44 The incumbent solution has value 42 x1 = 1 2 3 x2 = 0 x2 = 1 x2 = 0 42 44 44 5 x3 = 0 43.75 8 43.75 44 x3 = 1 43.5 9 x3 = 0 43.25 10 6 44 3/7 x2 = 1 44 1/3 7 x3 = 1 43.8 11 x3 = 0 44.3 12 x3 = 1 13 -∞ 13 42.66 We next solved the LP’s associated with the next nodes. We can fathom the node with z = 42.66. Why? 25 Getting a better bound z The bound at each node is obtained by solving the LP relaxation associated with the node z But the optimal objective value of the original problem is integer (because each cost is integer). z If the best integer valued solution for a node is at most 42.66, then we know the best bound is at most 42. z Other bounds can also be rounded down. 26 Branch and Bound 0-1 IPs 1 44 3/7 x1 = 0 44 4 x1 = 1 2 3 x2 = 0 x2 = 1 x2 = 0 42 The incumbent solution has value 42 44 5 x3 = 0 43.75 8 44 x3 = 1 43.5 9 x3 = 0 43.25 10 6 44 3/7 x2 = 1 44 1/3 7 x3 = 1 43.8 11 x3 = 0 44.3 12 x3 = 1 -∞. 13 43.75 42.66 27 Branch and Bound 0-1 IPs 1 44 x1 = 0 44 x1 = 1 2 3 4 44 5 x3 = 0 43 43 8 44 x3 = 1 43 44 x2 = 1 x2 = 0 x2 = 1 x2 = 0 42 The incumbent solution has value 42 9 43 6 x3 = 0 10 44 x3 = 1 43 11 x3 = 0 44 12 7 x3 = 1 -∞ 13 42 28 Branch and Bound 0-1 IPs 1 44 x1 = 0 44 x1 = 1 2 3 4 44 5 44 x3 = 0 43 8 43 x3 = 1 43 9 42 43 44 x2 = 1 x2 = 0 x2 = 1 x2 = 0 42 The incumbent solution has value 42 6 x3 = 0 x3 = 1 43 10 42 43 44 7 43 11 x3 = 0 44 12 x3 = 1 -∞ 13 43 We found an improved integer solution. x1 = 1, x2 = x3 = 0, x4 = 1, x5 = 0, x6 = 1 z = 43 29 Active nodes 1 44 x1 = 0 44 x1 = 1 2 3 4 44 5 44 x3 = 0 43 8 43 x3 = 1 43 9 42 43 44 x2 = 1 x2 = 0 x2 = 1 x2 = 0 42 The incumbent solution has value 42 6 x3 = 0 x3 = 1 43 10 42 43 44 7 43 11 x3 = 0 44 12 x3 = 1 -∞ 13 43 A node in the branch and bound tree is active if it is not fathomed and if one or more of its children have not been added to the tree. Nodes 11 and 12 are active. Nodes 10 and 13 are not active. 30 Branch and Bound 0-1 IPs 1 44 x1 = 0 44 x1 = 1 2 3 4 44 5 44 x3 = 0 43 8 43 x3 = 1 43 9 42 43 44 x2 = 1 x2 = 0 x2 = 1 x2 = 0 42 The incumbent solution has value 43 42 6 x3 = 0 x3 = 1 43 10 42 43 44 7 43 11 11 x3 = 0 44 12 x3 = 1 -∞ 13 43 Fathom any active node whose value cannot be better than the incumbent’s value. 31 Finishing Up 1 44 x1 = 0 44 x1 = 1 2 3 4 44 5 44 x3 = 0 43 8 43 x3 = 1 43 9 42 43 44 x2 = 1 x2 = 0 x2 = 1 x2 = 0 42 The incumbent solution has value 43 42 6 x3 = 0 x3 = 1 43 10 42 No active node remains. The algorithm ends. 43 44 7 43 11 11 43 x3 = 0 44 12 44 14 44 16 38 18 x3 = 1 -∞ 13 15 -∞ 17 -∞ 19 -∞ 32 Lessons Learned z Branch and Bound can speed up the search – Only 25 nodes (linear programs) were evaluated – Other nodes were fathomed z Obtaining a good incumbent earlier can be valuable – only 19 nodes would have been evaluated. z Each linear program can be solved quicker than usual because it starts with an almost optimal solution – uses a technique called the dual simplex method z Obtaining better bounds can be valuable. – We sometimes use properties that are obvious to us, such as the fact that integer solutions have integer solution values 33 Branch and Bound Algorithm z INITIALIZE ActiveList = {1} -- node 1 is the original problem Incumbent: = ∅ (or some heuristic finds an incumbent) z SELECT: – If ActiveList = ∅, then the Incumbent is optimal if it exists, and the problem is infeasible if no incumbent exists; – else, let j be a node from ActiveList. CASE 1. zLP(j)= -∞ (the LP is infeasible) Remove j from LIST (fathom it) Return to SELECT 34 Illustration of Case 1. 1 44 3/7 x1 = 0 44 x1 = 1 2 3 x2 = 0 x2 = 1 x2 = 0 42 44 The incumbent solution has value 42 44 x3 = 0 8 5 44 x3 = 1 9 x3 = 0 10 6 44 3/7 x2 = 1 44 1/3 7 x3 = 1 11 x3 = 0 12 x3 = 1 -∞ 13 13 The active nodes are 8 to 13. Suppose we select node 13. Then node 13 is fathomed. 35 Branch and Bound Algorithm z INITIALIZE ActiveList = {1} -- node 1 is the original problem Incumbent: = ∅ (or some heuristic finds an incumbent) z SELECT: – If ActiveList = ∅, then the Incumbent is optimal if it exists, and the problem is infeasible if no incumbent exists; – else, let j be a node from ActiveList. If cost data is integral, Case 2 is ⎣zLP(j) ⎦ > z(Incumbent) CASE 2. -∞ < zLP(j) ≤ z(Incumbent) Then zIP(j) ≤ zLP(j) ≤ z(Incumbent) Remove j from LIST (fathom it) Return to SELECT 36 Illustration of Case 2. 1 44 x1 = 0 44 x1 = 1 2 3 4 44 x3 = 0 43.75 8 44 x2 = 1 x2 = 0 x2 = 1 x2 = 0 42 The incumbent solution has value 43 42 5 44 x3 = 1 9 x3 = 0 10 6 44 7 x3 = 1 11 x3 = 0 12 x3 = 1 -∞ 13 The active nodes are 8 to 12. Suppose we select node 8. Then node 8 is fathomed. 37 Branch and Bound Algorithm z INITIALIZE ActiveList = {1} -- node 1 is the original problem Incumbent: = ∅ (or some heuristic finds an incumbent) z SELECT: – If ActiveList = ∅, then the Incumbent is optimal if it exists, and the problem is infeasible if no incumbent exists; – else, let j be a node from ActiveList. CASE 3. zIP(j) = zLP(j) > z(Incumbent), and the optimal LP solution at node j is integral, and it is better than the incumbent. Replace the incumbent with the opt sol for node j. Fathom any active nodes k if zIP(j) ≤ zLP(k) RETURN TO SELECT 38 Illustration of Case 3 The old incumbent solution has value 38 1 x1 = 0 44 x2 = 0 42 44 44 3/7 The new incumbent solution has value 42 x1 = 1 3 2 x2 = 1 The active nodes are 3, 4 and 5. 5 Suppose we select node 4 The LP relaxation at node 4 produces the solution: 0 0 1 0 1 1 z = 42 We replace the incumbent and fathom node 4. 39 Branch and Bound Algorithm INITIALIZE ActiveList = {1} -- node 1 is the original problem Incumbent: = ∅ (or some heuristic finds an incumbent) SELECT: If ActiveList = ∅, then the Incumbent is optimal if it exists, and the problem is infeasible if no incumbent exists; else, let j be a node from ActiveList. CASE 4. zLP(j) > z(Incumbent) Add two children of node j to ActiveList Remove j from ActiveList Return to SELECT 40 Illustration of Case 4 The incumbent has value 38. 1 x1 = 0 44 x2 = 0 4 44 3/7 x1 = 1 3 2 x2 = 1 The active nodes are 2 and 3 5 Suppose we select node 2. We cannot fathom node 2. Instead we create two children, and node 2 becomes inactive. 41 The Tree as it evolves if we select the active node with least label. (Breadth first search) 1 x1 = 0 x1 = 1 2 3 5 4 x3 = 0 14 14 6 x3 = 1 8 x3 = 0 9 15 16 16 x2 = 1 x2 = 0 x2 = 1 x2 = 0 x3 = 1 10 17 18 18 7 12 11 11 19 20 22 24 x3 = 1 x3 = 0 13 21 23 25 42 The Tree if we select the active node with greatest depth. (Depth first search) 1 x1 = 0 x1 = 1 2 3 5 4 x3 = 0 14 14 6 x3 = 1 8 x3 = 0 9 15 16 16 x2 = 1 x2 = 0 x2 = 1 x2 = 0 x3 = 1 10 17 18 18 7 12 11 11 19 20 22 24 x3 = 1 x3 = 0 13 21 23 25 43 Remarks z We could have selected any active node. z In practice, it is not good to select the node with lowest index. It leads to too many active nodes at a time, and too much storage z The rule in branching is that the two branches must account for all possible feasible solutions for the subproblem at the active node. 44 B & B for Pure Integer Programs z Example taken from IMP, but the branching is different. maximize 8x1 + 5x2 subject to x1 + x2 ≤ 6 9x1 + 5x2 ≤ 45 x1, x2 ≥ 0, x1, x2 integer 45 The first node of the B & B tree 41.25 1 There is no initial incumbent The bound associated with node 1 is the optimum objective value for the original LP. 46 The Graphical Representation x2 9 Max 8x1 + 5x2 8 s.t 7 x1 + x2 ≤ 6 9x1 + 5x2 ≤ 45 6 x1, x2 ≥ 0, x1, x2 integer 5 Optimal solution to the LP relaxation is x1 = 3.75, x2 = 2.25 z = 41.25 4 3 2 1 0 0 1 2 3 4 5 6 x1 47 Branch and Bound for Pure IPs 1 x1 ≤ 3 2 41.25 x1 ≥ 4 3 In general, we create two subproblems at a node with the following property: Every feasible solution to the IP at node 1 is a feasible solution to one of the subproblems at node 2 or node 3.. Node 2: the original problem plus the constraint: x1 ≤ 3. Node 3: the original problem plus the constraint: x1 ≥ 4 48 Why we chose this branching rule 1 x1 ≤ 3 2 41.25 x1 ≥ 4 3 Optimal solution to the LP relaxation is x1 = 3.75, x2 = 2.25 z = 41.25 Standard Rule: find a variable xj that has a fractional solution f in the LP. first subproblem: add the constraint “ xj ≤ ⎣ f ⎦ ” second subproblem: add the constraint “ xj ≥ ⎡ f ⎤ ” 49 Subproblems 1 and 2 x2 9 s.t 8 7 6 Max 8x1 + 5x2 x1 + x2 ≤ 6 9x1 + 5x2 ≤ 45 x1 ≤ 3 x1, x2 ≥ 0, x1, x2 integer 5 4 s.t 3 2 Max 8x1 + 5x2 x1 + x2 ≤ 6 9x1 + 5x2 ≤ 45 x1 ≥ 4 1 x1, x2 ≥ 0, x1, x2 integer 0 x1 0 1 2 3 4 5 6 50 Nodes 2 and 3 1 x1 ≤ 3 41.25 x1 ≥ 4 39 2 zLP(2) = 39. 3 Solution: x1 = 3, x2 = 3. This solution is integer, we get our first incumbent. 51 Nodes 2 and 3 1 x1 ≤ 3 The incumbent solution has value 39 41.25 x1 ≥ 4 39 41 22 3 But now node 2 can get fathomed. zLP(3) = 41. x1 = 4, x2 = 1.8 Next, add two subproblems from node 3, one with x2 ≤ 1, and one with x2 ≥ 2. 52 Nodes 4 and 5 1 The incumbent solution has value 39 41.25 x1 ≤ 3 x1 ≥ 4 39 41 22 3 x2 ≤ 1 4 x2 ≥ 2 Node 4 is the original problem plus the constraints x1 ≥ 4 and x2 ≤ 1 5 53 Subproblems 4 and 5 2 Max 8x1 + 5x2 s.t x1 + x2 ≤ 6 9x1 + 5x2 ≤ 45 x1 ≥ 4, x2 ≤ 1 x1, x2 ≥ 0, x1, x2 integer 1 Max 8x1 + 5x2 s.t x1 + x2 ≤ 6 9x1 + 5x2 ≤ 45 x1 ≥ 4, x2 ≥ 2 x1, x2 ≥ 0, x1, x2 integer 0 4 5 Subproblem 5 is infeasible. 54 Nodes 4 and 5 The incumbent solution has value 39 41.25 1 x1 ≤ 3 x1 ≥ 4 39 41 22 3 x2 ≥ 2 x2 ≤ 1 40.55 4 -∞ 5 55 Nodes 6 and 7 The incumbent solution has value 39 41.25 1 x1 ≤ 3 x1 ≥ 4 39 41 22 3 x2 ≥ 2 x2 ≤ 1 40.55 x1 ≤ 4 6 -∞ 4 5 x2 ≥ 5 7 56 Subproblems 6 and 7 2 Max 8x1 + 5x2 s.t x1 + x2 ≤ 6 9x1 + 5x2 ≤ 45 x1 = 4, x2 ≤ 1 x1, x2 ≥ 0, x1, x2 integer 1 Max 8x1 + 5x2 s.t x1 + x2 ≤ 6 9x1 + 5x2 ≤ 45 x1 ≥ 5, x2 ≤ 1 x1, x2 ≥ 0, x1, x2 integer 0 4 5 57 Nodes 6 and 7 The incumbent 39 solution has value 40 41.25 1 x1 ≤ 3 x1 ≥ 4 39 41 22 3 x2 ≥ 2 x2 ≤ 1 40.55 x1 ≤ 4 37 6 -∞ 4 x1 ≥ 5 7 40 5 All active nodes are fathomed. 58 Branch and Bound in General Notation: – Incumbent: the best solution on hand – zI(j) the optimum value for subproblem j – zLP(j) : value of the LP relaxation of node j – Children of a node: the two problems created for a node that are exhaustive. – ActiveList: the collection of active (not fathomed) subproblems. 59 On Branch and Bound z Branch and Bound is a standard way of solving integer programs. z Lots of art and engineering can go into making it work effectively z Next: a couple of issues that arise. 60 On Selection z Memory Issue: Don’t let ActiveList get too big (the solutions must be stored). Otherwise, you can run out of memory. 61 Different Branching and Bounding Rules are Possible z The more accurate the bound, the quicker the fathoming. – The better the bounding technique, the more accurate the bound and the quicker the fathoming. – The quicker that the important decisions are resolved, the quicker the fathoming z The better the incumbent, the quicker the fathoming. 62 Summary z Branch and Bound is the standard way of solving IPs to optimality. z There is art to making it work well in practice. z Much of the art is built into state-of-the-art solvers such as CPLEX. 63 A bad example for implicit enumeration maximize 2x1 + 2x2 + 2x3 + . . . + 2x100 subject to 2x1 + 2x2 + 2x3 + . . . + 2x100 ≤ 101 xi ∈ {0,1} for i = 1 to 100. Why is this a bad example? What would happen if we used branch and bound, as described earlier? 64 The Solution for the LP Relaxation for node 1 maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6 ≤ 14 subject to 0 ≤ xj ≤ 1 for j = 1 to 6 x1 x2 x3 x4 x5 x6 1 0.429 0 0 0 1 Objective value 44.43 LP solution is obtained from Excel Solver. 65 The Solution for the LP Relaxation for node 2 maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6 subject to 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6 ≤ 14 0 ≤ xj ≤ 1 for j = 1 to 6, and x1 = 0 x1 x2 x3 x4 x5 x6 0 1 0.25 0 0 1 Objective value: 44 66 The Solution for the LP Relaxation for node 3 maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6 subject to 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6 ≤ 14 0 ≤ xj ≤ 1 for j = 1 to 6, and x1 = 1 x1 x2 x3 x4 x5 x6 1 0.429 0 0 0 1 Objective value 44.43 67 The Solution for the LP Relaxation for node 4 maximize 16x1 + 22x2 + 12x3 + 8x4 +11x5 + 19x6 subject to 5x1 + 7x2 + 4x3 + 3x4 +4x5 + 6x6 ≤ 14 0 ≤ xj ≤ 1 for j = 1 to 6, and x1 = x2 = 0. x1 x2 x3 x4 x5 x6 0 0 1 0 1 1 Objective value: 42 68 The Solution for the LP Relaxation for node 5 x1 x2 x3 x4 x5 x6 0 1 0.25 0 0 1 Objective value: 44 69 The Solution for the LP Relaxation for node 6 x1 x2 x3 x4 x5 x6 1 0 0.75 0 0 1 Objective value: 44 70 The Solution for the LP Relaxation for node 7 x1 x2 x3 x4 x5 x6 1 1 0 0 0 0.333 Objective value: 44.33 71 The Solution for the LP Relaxation for node 8 x1 x2 x3 x4 x5 x6 0 1 0 0 0.25 1 Objective value: 43.75 72 The Solution for the LP Relaxation for node 9 x1 x2 x3 x4 x5 x6 0 1 1 0 0 0.5 Objective value: 43.5 73 The Solution for the LP Relaxation for node 10 x1 x2 x3 x4 x5 x6 1 0 0 0 0.75 1 Objective value: 43.25 74 The Solution for the LP Relaxation for node 11 x1 x2 x3 x4 x5 x6 1 0 1 0 0 0.833 Objective value: 43.83 75 The Solution for the LP Relaxation for node 12 x1 x2 x3 x4 x5 x6 1 1 0 0 0 0.333 Objective value: 44.33 76 The Solution for the LP Relaxation for node 13 This problem has no feasible solution. 77