4 (15 points) This question deals with the branch-and-bound method of solving in- teger programming models. Suppose you are charged with deciding which of 50 potential distribution centers to open, and how much demand from each of your 150 customers should be provided by each of those distribution centers. Your objective is to minimize total cost, where the cost is the sum of the fixed costs of opening the centers and the transportation costs associated with serving the customers. Suppose you have modeled this decision problem using 50 binary variables and 7500 continuous variables. At some point you solver has investigated 13 branch- and-bound nodes, which form a tree that can be represented like this: 500 550 530 8 9 610 625 810 600 4 10 11 inicas 750 685 700 12 13 710 800 The number at each node is the objective value in thousands) of the continuous LP subproblem at that node, or "infeas" if the subproblem has no feasible solution at that node. A double circle indicates a node where the solution to the continuous LP subproblem is integer-feasible (no binary variables take fractional values). The numbers above the nodes indicate the order in which they were created; you can use these numbers to identify the nodes in your answer. a: What is the cost of the best integer-feasible solution found so far? b: Which are the remaining active nodes at this point? c: What is the current lower bound on the optimal cost? d: What is the "gap" between the current lower and upper bounds? e: Suppose you tried instead to solve this problem by enumerating all the possible combinations of facilities to open, and solving a linear program for each of these possibilities. How many linear programs would you have to solve? 4 (15 points) This question deals with the branch-and-bound method of solving in- teger programming models. Suppose you are charged with deciding which of 50 potential distribution centers to open, and how much demand from each of your 150 customers should be provided by each of those distribution centers. Your objective is to minimize total cost, where the cost is the sum of the fixed costs of opening the centers and the transportation costs associated with serving the customers. Suppose you have modeled this decision problem using 50 binary variables and 7500 continuous variables. At some point you solver has investigated 13 branch- and-bound nodes, which form a tree that can be represented like this: 500 550 530 8 9 610 625 810 600 4 10 11 inicas 750 685 700 12 13 710 800 The number at each node is the objective value in thousands) of the continuous LP subproblem at that node, or "infeas" if the subproblem has no feasible solution at that node. A double circle indicates a node where the solution to the continuous LP subproblem is integer-feasible (no binary variables take fractional values). The numbers above the nodes indicate the order in which they were created; you can use these numbers to identify the nodes in your answer. a: What is the cost of the best integer-feasible solution found so far? b: Which are the remaining active nodes at this point? c: What is the current lower bound on the optimal cost? d: What is the "gap" between the current lower and upper bounds? e: Suppose you tried instead to solve this problem by enumerating all the possible combinations of facilities to open, and solving a linear program for each of these possibilities. How many linear programs would you have to solve