CO250 INTRODUCTION TO OPTIMIZATION, SPRING 2021
ASSIGNMENT 7
*
Due: Monday July 19, 2021, at 4:00 p.m. EDT Please submit a pdf file to CROWDMARK. Recall, late assignments
will not be accepted. It is the responsibility of the students to make sure that the file they submit is clearly readable.
Important information: You are expected to do the assignments on your own. The only sources allowed
for doing the assignments are:
• all of the material on the co250 Spring 2021 course website,
• the textbook,
• all of the material on the co250 Spring 2021 Piazza website,
• your Instructors and TAs.
Usage of any other source in doing the homework assignments is against the academic integrity rules for co250 in the
Spring 2021 term.
For example, copying or paraphrasing a solution from some fellow student or from old solutions from previous
offerings of related courses or various sources on the web, qualifies as cheating and the TA’s have been instructed to
actively look for evidence of academic offences when evaluating assignment papers. By uWaterloo policy, academic
integrity violations by a student in assignments will lead to a mark of zero in that assignment and a 5% deduction
from the Final Course Grade. In addition, all academic offences are reported to the Associate Dean for Undergraduate
Studies.
If you have any questions about the marking and feedback on assignments, then you should first check your
solutions against the posted solutions. After that if you still have questions please contact the TAs in charge of
feedback for the assignment. For Assignment 7 the following TAs are in charge:
Question TA email address
1 Samuel Winnick stwinnick@uwaterloo.ca
2 Hao Sun hao.sun@uwaterloo.ca
3 Jimit Majmudar jmajmudar@uwaterloo.ca
4 Elvis Iam hciam@uwaterloo.ca
*COPYRIGHT: Reproduction, sharing or online posting of this document is strictly forbidden ©University of Waterloo, Walaa Moursi and
Martin Pei.
1
2
Exercise 1 (25 marks=18+7).
Let G be the following graph, with two specified vertices s, t, and the edges are labelled with their lengths ce.
187
11 9
2
5
3 8
15 5
9
9
s
a b
c
d e
t
(a) Perform the shortest s, t-path algorithm as described in the lectures. For each step, show the cut you are consideering, the slacks of relevant edges, the width assignment for your cut, and all tight edges. At the end of the
algorithm, prove that your s, t-path is the shortest using the width assignments you computed.
You may choose to use the worksheet provided on LEARN for your solution.
(b) Suppose we change the length of edge de to some constant α > 0. Determine all values of α such that your
solution from part (a) is still optimal. Justify your answer using complementary slackness conditions.
3
Exercise 2 (25 marks).
Recall that the fundamental theorem of linear programming states that every linear programming problem is either
(a) is infeasible, or
(b) is unbounded, or
(c) has an optimal solution.
Consider the integer program (IP):
max x1 +
√
3×2
s.t. x1 +
√
3×2 ≤ 0
x1 ≥ 1
x1, x2 integer.
(Note that (IP) is not a linear program.) Which of (a) — (c) hold for (IP), if any? Justify your answer.
4
Exercise 3 (25 marks=8+8+9).
Consider the following integer program (IP):
max (1, 1)x
s.t.
−5 16
32 −3
!
x ≤
68
200!
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
32×1 − 3×2 ≤ 200−5×1 + 16×2 ≤ 68 (
3404
497 ,
3176
497 )
(
25
4
, 0)T
(a) Draw the convex hull of the feasible solutions of (IP). Then write it down in the form of a polyhedron Ax ≤ b.
(b) The optimal solution to (LP) is (
3404
497 ,
3176
497 ). What is the optimal solution to (IP)? Give a simple geometric
argument for your answer.
(c) We see from part (b) that the optimal solution of (IP) is fairly “close” to the optimal solution of (LP). But this is
not necessarily the case. Determine one possible alternative objective function c
T x (where c ̸= 0) such that the
optimal solution to (LP) is still the same, but the optimal solution of (IP) is (6, 0)T
.
Note: Do not include “how” you found the vector in your solution. You only need to present your vector c, and
give a short proof of optimality for both (LP) and (IP) (e.g. using cones of tight constraints).
5
Exercise 4 (25 marks=1+10+7+7).
We will use the same (IP) and (LP) from the exercise 3, except we are changing the objective function to (1, −1)x.
Suppose we add slack variables to (LP) to get (LP-SEF)
max (1, −1, 0, 0)x
s.t.
−5 16 1 0
32 −3 0 1!
x =
68
200!
x ≥ 0
We now solve it using simplex to get this optimal canonical form (LP-OPT).
max (0, −
29
32 , 0, −
1
32 )x +
25
4
s.t.
1 −
3
32 0
1
32
0
497
32 1
5
32!
x =
25
4
397
4
!
x ≥ 0
(a) Write down the optimal solution for (LP-SEF), and the corresponding optimal solution for (LP).
(b) For each constraint in (LP-OPT), derive a cutting plane using the method from class. You should include all details
of the derivation.
(c) From the cutting planes that you have derived from part (b), substitute the slack variables using the constraints
in (LP-SEF). Then plot the corresponding inequalities on the feasible region of (LP) to show that they are indeed
cutting planes for your optimal solution from part (a).
(d) The cutting plane method from class applies the floor function to the coefficients and constants. Find a way to
generate cutting planes (in general) that uses the ceiling function ⌈a⌉ instead. You can assume that a generic
constraint in an optimal canonical form has the form xℓ +
P
j∈N A¯
ijxj = ¯bi
, where ℓ is the basic variable of
the constraint, N is the set of indices for non-basic variables, and i is the row index. Prove that your method is
correct, and apply your method to one of the constraints of (LP-OPT).