Consider the following BnB enumeration tree: 22 3 = 920 23 SE Ps (8)=910 (3) 21...

Transcribed Image Text:

Consider the following BnB enumeration tree: 22 ≤3 = 920 23 SE Ps (8)=910 (3) 21 ≤ 63 P6 (6) D ΣΣΕ P₁=(¹) = 950 PA 23 28 B P2) (PT) (7)=915 IFS 1264 = 935 Ps) () = C IFS Answer the following based on the above tree, using the strategies discussed in the class. Note: IFS stands for Integer Feasible Solution. (d) Is it a maximization or a minimization problem? Explain. (e) Write all the possible pairwise relations among A, B, C, D. Also suggest a possible upper or lower value for A, B, C, D. (f) What could be the node selection strategy in the above tree? Explain your answer using: best bound, depth first best back, breadth first best next, most recent. (g) What could be the branching direction selection strategy in the above tree? Explain your answer using: branch-up, branch-down, mixed. (3) (3) (3) (3) (h) At (P3), the LP solution is z = 5,12 = 3.1.13 = 7,2 = 5.9. What could be the variable selection strategy? Explain your answer using: highest fraction, lowest fraction, or nearest to integer. (i) Write the relationship between E & F. Also suggest a possible upper or lower value for E & F. (j) Explain a possible sequence of events that occurred from node (P+) to node (Pg). Based on the explanation, what should be the next node to process? (k) What is the incumbent solution in the above tree? How far is it from the global optimal solution? Consider the following BnB enumeration tree: 22 ≤3 = 920 23 SE Ps (8)=910 (3) 21 ≤ 63 P6 (6) D ΣΣΕ P₁=(¹) = 950 PA 23 28 B P2) (PT) (7)=915 IFS 1264 = 935 Ps) () = C IFS Answer the following based on the above tree, using the strategies discussed in the class. Note: IFS stands for Integer Feasible Solution. (d) Is it a maximization or a minimization problem? Explain. (e) Write all the possible pairwise relations among A, B, C, D. Also suggest a possible upper or lower value for A, B, C, D. (f) What could be the node selection strategy in the above tree? Explain your answer using: best bound, depth first best back, breadth first best next, most recent. (g) What could be the branching direction selection strategy in the above tree? Explain your answer using: branch-up, branch-down, mixed. (3) (3) (3) (3) (h) At (P3), the LP solution is z = 5,12 = 3.1.13 = 7,2 = 5.9. What could be the variable selection strategy? Explain your answer using: highest fraction, lowest fraction, or nearest to integer. (i) Write the relationship between E & F. Also suggest a possible upper or lower value for E & F. (j) Explain a possible sequence of events that occurred from node (P+) to node (Pg). Based on the explanation, what should be the next node to process? (k) What is the incumbent solution in the above tree? How far is it from the global optimal solution?

Answer rating: 100% (QA)

ANSWER d The incumbent solution i... View the full answer