4. (15 points) The following diagram shows a branch-and-bound tree search for an integer programming maximization proble
Posted: Wed May 11, 2022 9:49 am
- 4 15 Points The Following Diagram Shows A Branch And Bound Tree Search For An Integer Programming Maximization Proble 1 (114.56 KiB) Viewed 26 times
4. (15 points) The following diagram shows a branch-and-bound tree search for an integer programming maximization problem. Each node has a number in parenthesis representing the search order and a value Z indicating the optimal LP relaxation value in that node. Assume that only nodes 5 and 6 yield integer solutions (i.e., their optimal LP relaxation solution turned out to be an integer solution). (1), Z = 64 (2), Z = 58 (3), Z = 61 (4), Z = 58.5 (5), Z = 55 (6), Z = 56 (7), Z = 57 (a) What is the best upper bound and lower bound that you can derive from this branch- and-bound tree? (b) Now consider that we branch on node 2 and create two new nodes: 8 and 9. Node 9 is infeasible and node 8 has Z = 56.5. What can you say about the optimal solution of the problem? If you cannot conclude that the optimal solution has been found, which node should we explore next, why?