Semester 2, 2005 Page X of XY
Faculty of ECONOMICS & BUSINESS
ECON2002 – INTERMEDIATE MICROECONOMICS
This information is only necessary if
the paper is NOT TO BE REMOVED
comp3530 Discrete Optimization SID: _______________________________
2 hours and 30 minutes 10 minutes
Duration: 2h30m Reading time: 10 mins
EXAM WRITING TIME: FROM EXAM ROOM.
READING TIME: EXAM CONDITIONS:
Section in a separate book……
comp3530 final exam (s2, 2021)
CONFIDENTIAL EXAM PAPER
This paper is not to be removed from the exam venue.
Computer Science
EXAMINATION
SEAT NUMSBeEmR:e_s_t_e_r__2__-__P_r_a__c_t_ic__e_,_2_0__2_1_______
FULL NAME: _______________________________
This is a restricted open book exam: Handwritten notes, printed notes, and
textbooks are allowed.
All submitted work must be done individually without consulting someone else’s help, in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
MATERIALS TO BE SUPPLIED TO STUDENTS:
INSTRUCTIONS TO STUDENTS:
Type your answers in your text editor (Latex, Word, etc.) and convert it into a pdf file.
Submit this pdf file via Canvas. No other file format will be accepted. Hand- written responses will not be accepted.
Start by typing you student ID at the top of the first page of your submission. Do not type your name.
Submit only your answers to the questions. Do not copy the questions.
Do not copy any text from the permitted materials. Always write your answers
in your own words.
Dennis\Desktop\Exam Typing Page 2 of 4
page 1 of 14
comp3530 final exam (s2, 2021) Problem 1. Consider the following linear program:
minimize subject to
Your task is to derive its dual.
x1 − 2×2 ≥ 7 2×1 + 4×2 ≥ 1 x1 ≥ 0 x2 free
page 2 of 14
Your task is to:
a) Derive its dual program.
b) Design a separation oracle for the dual.
comp3530 final exam (s2, 2021)
Problem 2. Let G = (V, E) be an undirected graph. For a given pair of vertices s,t ∈ V, let P be the set of simple s-t paths in G. Consider the following linear programming formulation for finding the maximum number of edge disjoint paths from s to t:
maximize subject to
∀ e ∈ E ∀ P ∈ P
page 3 of 14
comp3530 final exam (s2, 2021) (solution to Problem 2 continues here)
page 4 of 14
comp3530 final exam (s2, 2021)
Problem 3. In the bipartite maximum edge coloring problem we are given a bipartite graph G = (V,E). Let M be the collection of all possible matchings of G. The objective is to partition the edge set E into a collection of matchings M1, M2, . . . , Mk ∈ M with minimum total cost, where the cost of a matching M is defined as cM = |M|, the maximum edge weight in M.
Consider the following linear programming relaxation of this problem: minimize ∑ cMxM
subjectto ∑xM =1 ∀e∈E M∈M:e∈M
xM ≥ 0 ∀ M ∈ M
Although the linear program has an exponentially number of variables, it can be solved using the modified version of simplex that only keeps track of the current feasible basis. Recall that in order to do that, we need a routine that tests whether there is a non-basic variable with negative reduced cost.
Your task is to design an efficient algorithm that takes as input a feasible basis and returns a non-basic variable with negative reduced cost or reports that there is no such variable.
page 5 of 14
comp3530 final exam (s2, 2021) (solution to Problem 3 continues here)
page 6 of 14
comp3530 final exam (s2, 2021)
Problem 4. Let f : 2U → R+ be a monotone non-decreasing and submodular func-
tion. Your task is to prove the following properties:
a) Define a new function g : 2U → R as g(S) = log(f(S)). Assuming f(S) > 0 for
all S ⊆ U, prove that g is submodular.
b) Define a new function h : 2U → R+ as h(S) = 2f(S). Prove that h need not be submodular.
page 7 of 14
comp3530 final exam (s2, 2021) (solution to Problem 4 continues here)
page 8 of 14
comp3530 final exam (s2, 2021)
Problem 5.LetG=(V,E)beagraphwithedgeweightsw:E→R+ andletS⊆V be a distinguished subset of vertices. Consider the problem of finding a spanning tree T of G with minimum weight such that the vertices in S are leaves in T; in other words, degT(u) = 1 for all u ∈ S.
Your task is to give an integral linear programming formulation for this problem:
a) Give an integer linear programming formulation for the problem.
b) Argue that the linear relaxation of your program is integral; that is, show that every extreme point of the linear relaxation is integral. (You can assume inte- grality results proved in class.)
page 9 of 14
comp3530 final exam (s2, 2021) (solution to Problem 5 continues here)
page 10 of 14
comp3530 final exam (s2, 2021)
(exam questions end here. use the rest of the space for rough work)
page 11 of 14
comp3530 final exam (s2, 2021) (use the rest of the space of rough work)
page 12 of 14
comp3530 final exam (s2, 2021) (use the rest of the space of rough work)
page 13 of 14
comp3530 final exam (s2, 2021) (use the rest of the space of rough work)
page 14 of 14