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).