Management Science I: Homework 4
Fall 2023 | Due Friday 2/23/2024 (@ 11:59 PM)
There are four problems in this homework assignment, totaling 60 points. You may submit either typed
or handwritten solutions (in addition to screenshots where requested). You will submit the homework
using Gradescope (“Homework 4”), and you will submit the accompanying spreadsheet on Canvas.
General reminders for assignments:
● Different questions build off each other in the homework. You will receive partial credit if you do
the right thing using an upstream incorrect answer (e.g., if you use the wrong formula in an
Excel cell in one part, and then rely on that cell later). We can only know whether you were
doing the right thing if you include an explanation of how you got your numbers – so include
brief (1 sentence or phrase) explanations of your logic if you want to be eligible for partial credit.
● As stated in the syllabus, you may work in groups of up to 4 people. A couple of reminders: do
not collaborate outside of these groups, and do not use Generative AI tools to assist with any of
the problem solutions.
, Problem 1 [15 pts]: Branch and Bound
The diagram below shows a partial branch and bound tree, up to the 8 th subproblem. In each node, the
optimal value of the subproblem ( Z LP) reported. We denote the optimal value of each node as “ Z LP” to
indicate that these are all LPs (with more and more constraints added as we move down the tree). In
cases where ( Z LP =Z IP), this means that the solution in the node is integer – the optimal value of the LP
is therefore also the optimal value of the IP for this subproblem.
Main Pb.
ZLP = 170
Sub Pb. #1 Sub Pb. #2
ZLP = 160 ZLP = 140
Sub Pb. #3 Sub Pb. #4 Sub Pb. #5 Sub Pb. #6
ZLP = 150 ZIP = ZLP = 120 ZLP = 130 ZLP = 110
Sub Pb. #7 Sub Pb. #8
ZLP = 125 ZLP = 115
X7* = 6.7
A) [2 pts] Is the problem a maximization or minimization problem?
It is a maximization problem.
B) [2 pts] Given the original IP problem, how was the branch and bound starting solution (“Main
Pb.”) obtained?
The starting solution of a branch and bound problem is obtained by solving the original
IP problem as an LP problem. This involves relaxing the integer constraints and allowing
the decision variables to take any real values.
C) [4 pts] Given the current state of the tree, what are the upper and lower bounds on the optimal
value for the original IP?
The upper bound is given by the highest integer solution found so far in the tree. In this
case, it is given by the highest ZLP, which is 150 at Sub Problem #3. The lower bound is
determined by the smallest that we know we could do, which is the ZLP = ZIP, which is
120 at Sub Problem #4.
D) [2 pts] Which subproblem(s) cannot contain the optimal solution?
The best integer solution found so far is 120 at Sub Problem #4. The subproblems that
cannot contain the optimal solution are Z_LP values 110 Sub Problem #6, and Z_LP
values 115 Sub Problem #8, which are all less than the lower bound 120.
Fall 2023 | Due Friday 2/23/2024 (@ 11:59 PM)
There are four problems in this homework assignment, totaling 60 points. You may submit either typed
or handwritten solutions (in addition to screenshots where requested). You will submit the homework
using Gradescope (“Homework 4”), and you will submit the accompanying spreadsheet on Canvas.
General reminders for assignments:
● Different questions build off each other in the homework. You will receive partial credit if you do
the right thing using an upstream incorrect answer (e.g., if you use the wrong formula in an
Excel cell in one part, and then rely on that cell later). We can only know whether you were
doing the right thing if you include an explanation of how you got your numbers – so include
brief (1 sentence or phrase) explanations of your logic if you want to be eligible for partial credit.
● As stated in the syllabus, you may work in groups of up to 4 people. A couple of reminders: do
not collaborate outside of these groups, and do not use Generative AI tools to assist with any of
the problem solutions.
, Problem 1 [15 pts]: Branch and Bound
The diagram below shows a partial branch and bound tree, up to the 8 th subproblem. In each node, the
optimal value of the subproblem ( Z LP) reported. We denote the optimal value of each node as “ Z LP” to
indicate that these are all LPs (with more and more constraints added as we move down the tree). In
cases where ( Z LP =Z IP), this means that the solution in the node is integer – the optimal value of the LP
is therefore also the optimal value of the IP for this subproblem.
Main Pb.
ZLP = 170
Sub Pb. #1 Sub Pb. #2
ZLP = 160 ZLP = 140
Sub Pb. #3 Sub Pb. #4 Sub Pb. #5 Sub Pb. #6
ZLP = 150 ZIP = ZLP = 120 ZLP = 130 ZLP = 110
Sub Pb. #7 Sub Pb. #8
ZLP = 125 ZLP = 115
X7* = 6.7
A) [2 pts] Is the problem a maximization or minimization problem?
It is a maximization problem.
B) [2 pts] Given the original IP problem, how was the branch and bound starting solution (“Main
Pb.”) obtained?
The starting solution of a branch and bound problem is obtained by solving the original
IP problem as an LP problem. This involves relaxing the integer constraints and allowing
the decision variables to take any real values.
C) [4 pts] Given the current state of the tree, what are the upper and lower bounds on the optimal
value for the original IP?
The upper bound is given by the highest integer solution found so far in the tree. In this
case, it is given by the highest ZLP, which is 150 at Sub Problem #3. The lower bound is
determined by the smallest that we know we could do, which is the ZLP = ZIP, which is
120 at Sub Problem #4.
D) [2 pts] Which subproblem(s) cannot contain the optimal solution?
The best integer solution found so far is 120 at Sub Problem #4. The subproblems that
cannot contain the optimal solution are Z_LP values 110 Sub Problem #6, and Z_LP
values 115 Sub Problem #8, which are all less than the lower bound 120.
