The following figure describes the tree obtained at some point in the algorithm. For each subproblem...

 

Transcribed Image Text:

The following figure describes the tree obtained at some point in the algorithm. For each subproblem we indicate the number of the subproblem, whether the optimal solution is an integer solution or fractional, and the optimal value of that LP (if feasible). (Po): fractional opt. value = 50 (P1): fractional opt. value = 51 (P2): fractional opt. value 50 (Ps): infeasible (P4): fractional opt. value = 53 (Ps): integer opt. value = 58 (P6): fractional opt. value 53.5 (P7): fractional opt. value=55 (Ps): fractional opt. value 54.5 (Pg): integer opt. value = 60 (Pio): fractional opt. value 56 (P1): fractional opt. value = 57 (P12): integer opt. value = 56 Now answer the following questions, and justify your responses. (a) From the above, what is the best upper bound you can give for the optimal value of the given IP? (b) From the above, what is the best lower bound you can give for the optimal value of the given IP? (c) Which subproblem(s) do we still need to branch on and explore further? The following figure describes the tree obtained at some point in the algorithm. For each subproblem we indicate the number of the subproblem, whether the optimal solution is an integer solution or fractional, and the optimal value of that LP (if feasible). (Po): fractional opt. value = 50 (P1): fractional opt. value = 51 (P2): fractional opt. value 50 (Ps): infeasible (P4): fractional opt. value = 53 (Ps): integer opt. value = 58 (P6): fractional opt. value 53.5 (P7): fractional opt. value=55 (Ps): fractional opt. value 54.5 (Pg): integer opt. value = 60 (Pio): fractional opt. value 56 (P1): fractional opt. value = 57 (P12): integer opt. value = 56 Now answer the following questions, and justify your responses. (a) From the above, what is the best upper bound you can give for the optimal value of the given IP? (b) From the above, what is the best lower bound you can give for the optimal value of the given IP? (c) Which subproblem(s) do we still need to branch on and explore further?