ISyE $3133,$ Programming Assignment $3$

This assignment can be done in a group of up to three students. Please write all group member names on the PDF file and in a comment in the code. Only one group member should submit the files on Canvas.

Solve the following integer program using the branch and bound method.

$ma{?}_1+4x_2$

$31x_1+232x_{2}359$

$23x_1+79x_{2}203$

$x_1,x_{2}0,$

$x_1,x_2$inZ.

You should draw a branch and bound tree for this problem, starting with the root node LP relaxation. Label each branch with the extra constraint added to the child node. Label each node with the optimal solution and optimal objective value for the LP relaxation solved at that node $($unless the LP relaxation is infeasible; then write infeasible in the node$).$ Label the node with a name that you use in your code, so we can match the model with the node. Continue to grow the branch and bound tree until you have identified an optimal solution to the integer program.

To solve the LP relaxation at each node, implement that LP in Gurobi. Every node should have its own model in your code $($could be mod$1,$ mod$2,$ mod$3,$ or rootmod, leftmod, rightmod, etc$).$ You can do a brute$-$force model where you copy and paste, or you can copy the root node model using mod.copy$()$ and add constraints to that model. See example code: Model$\_$Copying.py$.$

You should submit:

A PDF report with the final branch and bound tree $($can be handwritten and embedded$)$ as well as answers to following questions $($typed$)$

What is the optimal solution to your integer program?

How can you tell it is optimal from your branch and bound tree?

Your $.$py code with all models $($for all nodes in the tree$)$