8jJUrTR5xXP3Vw
Assignment problems.
A9-1. Cutting planes
Consider the following integer program (IP):
max
7 5 x
s.t.
0@ 5 16 4
21 39
1Ax 
0@ 2819
91
1A
x 0, x integer
Let (LP) be the LP relaxation of (IP), i.e. we drop the integrality constraint from (IP). The
feasible region for (LP) is drawn below, and the integer points inside the feasible region are
feasible solutions to (IP).
0 1 2 3 4 5
1
2
3
4
5
x1
x2
6 7 8
6
7
8
5x1 x2  28
( 1105318 ,
49
106 )
21x1 39x2  91
6x1 4x2  19
(a) The optimal solution to (LP) is (1105318 ,
49
106). What is the optimal solution to (IP)? Give
a simple geometric argument for your answer.
(b) Suppose we add slack variables to (LP) to get (LP-SEF)
max

7 5 0 0 0 x
s.t.
0@ 5 1 1 0 06 4 0 1 0
21 39 0 0 1
1Ax =
0@ 2819
91
1A
x 0
8jJUrTR5xXP3Vw
We now solve it using simplex to get this optimal canonical form (LP-OPT).
max

0 0 0 6353 1159

x+ 3500159
s.t.
0@1 0 0 13106 21590 1 0 7106 153
0 0 1 3653 7159
1Ax =
0@110531849
106
1763
159
1A
x 0
For each constraint in (LP-OPT), derive a cutting plane using the method from class.
(c) From the cutting plane that you have derived from the first equation, substitute the slack
variables using the constraints in (LP-SEF). Then plot the corresponding inequality on
the feasible region of (LP) to show that it is indeed a cutting plane.
(d) Add the cutting plane from the first equation to (LP-OPT), and then solve for a new
optimal solution (use computational tools). Plot this new optimal solution on the
diagram. Explain why this new solution is an improvement over the old solution.
8jJUrTR5xXP3Vw
A9-2. Branch-and-bound
Consider the following integer program.
max 5x1 + 13x2
s.t. 25x1 + 10x2  17
6x1 + 14x2  67
x1, x2 0
x1, x2 Z
The feasible region of the LP relaxation is sketched below.
6x1 + 14x2  67
25x+ 10y  17
Perform the branch-and-bound method on this problem until you have reached an integral
optimal solution. When you have a choice of which variable to branch on, you should branch
on x1. For each subproblem, include its optimal solution and optimal value. Explain how
you are resolving each subproblem. For each feasible subproblem, sketch its feasible region.
(You should use computational tools to solve the original LP relaxation and each subprob-
lem.)
8jJUrTR5xXP3Vw
A9-3. Knapsack problem
Consider the binary knapsack problem with the following 5 items, and the weight limit is
W = 50.
Item 1 2 3 4 5
Weight 17 21 6 13 25
Value 170 180 50 105 200
Notice that the items are already arranged in decreasing value-to-weight ratio.
(a) We can rewrite the LP relaxation of the general formulation of the binary knapsack
problem as
max
nX
i=1
vixi
s.t.
nX
i=1
wixi  W
xi  1 8i = 1, . . . , n
x 0
Write down the explicit formulation for our problem with 5 items.
(b) Write down the dual of the formulation from part (a). Use y, z1, z2, z3, z4, z5 as the dual
variables (they correspond to the 6 main primal constraints).
(c) Write down all the complementary slackness conditions for the primal-dual pair.
(d) Using the formula from class, we see that x¯ = (1, 1, 1, 613 , 0)
T is an optimal solution to
the primal LP. Derive a dual solution that satisfies CS conditions with x¯.
(e) Explain how arranging the items in decreasing value-to-weight ratio ensures that the
dual solution from part (d) is feasible (hence optimal).
***** There is one more part on the next page. *****
8jJUrTR5xXP3Vw
(f) The following diagram shows the first few steps in applying the branch-and-bound
method to this problem. Each box contains the optimal solution and value to the
subproblem.
Original problem
(1, 1, 1, 613 , 0)
T
⇠ 448.5
Subproblem 4
(1, 821 , 0, 0, 1)
T
⇠ 438.6
Subproblem 5
(1, 0, 1, 1, 1425 )
T
437
Subproblem 6
( 1617 , 1, 0, 1, 0)
T
445
Subproblem 3
(1, 1, 1, 0, 0)T
400
Subproblem 1
(1, 1, 1, 0, 625 )
T
448
Subproblem 2
(1, 2021 , 0, 1, 0)
T
⇠ 446.4
x4 = 0 x4 = 1
x5 = 0 x5 = 1 x2 = 0 x2 = 1
Complete the remainder of the branch-and-bound method, resolving the subproblems
from left to right. Explain how you are resolving each subproblem and why. Produce
an optimal solution to the knapsack problem in the end.