comp3530 final exam (s2, 2021)
C:\Documents and Settings\Dennis\Desktop\Exam Typing
Instructions.doc
Page 2 of 4
01/27 Semester 2, 2005 Page X of XY
Faculty of ECONOMICS & BUSINESS
ECON2002 – INTERMEDIATE MICROECONOMICS
Duration: 2h30m
Reading time: 10 mins
SEAT NUMBER: _______________________________
FULL NAME: _______________________________
SID: _______________________________
INSTRUCTIONS TO CANDIDATES
Answer each Section in a separate book……
Etc etc etc
Paper Code: This
no. can be found
on the Spec sheet.
This information is only necessary if
the paper is NOT TO BE REMOVED
FROM EXAM ROOM.
CONFIDENTIAL EXAM PAPER
This paper is not to be removed from the exam venue.
Computer Science
EXAMINATION
Semester 2 – Practice, 2021
comp3530 Discrete Optimization
EXAM WRITING TIME: 2 hours and 30 minutes
READING TIME: 10 minutes
EXAM CONDITIONS:
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:
None
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.
page 1 of 14
https://sydney.edu.au/students/academic-dishonesty.html
https://sydney.edu.au/students/academic-dishonesty.html
comp3530 final exam (s2, 2021)
Problem 1. Consider the following linear program:
minimize 2×1 − 3×2
subject to x1 − 2×2 ≥ 7
2×1 + 4×2 ≥ 1
x1 ≥ 0
x2 free
Your task is to derive its dual.
page 2 of 14
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 ∑
P∈P
xP
subject to ∑
P∈P :e∈P
xP ≤ 1 ∀ e ∈ E
xP ≥ 0 ∀ P ∈ P
Your task is to:
Derive its dual program.a)
Design a separation oracle for the dual.b)
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 ∑
M∈M
cMxM
subject to ∑
M∈M:e∈M
xM = 1 ∀ e ∈ E
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:
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.
a)
Define a new function h : 2U → R+ as h(S) = 2 f (S). Prove that h need not be
submodular.
b)
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. Let G = (V, E) be a graph with edge weights w : E → R+ and let S ⊆ 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:
Give an integer linear programming formulation for the problem.a)
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.)
b)
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