Assignment 3 LP and IP

CSC373 
Assignment 3

Instructions
1. Be sure to include your name and student number with your assignment. Typed assignments
are preferred (e.g., PDFs created using LaTeX or Word), especially if your handwriting is
possibly illegible or if you do not have access to a good quality scanner. Please submit a
single PDF on MarkUS at https://markus.teach.cs.toronto.edu/csc373-2019-09.
2. You will receive 20% of the points for any (sub)problem for which you write “I do not know
how to approach this problem.” (you will receive 10% if you leave the question blank and do
not write this or a similar statement). Not applicable to BONUS questions.
3. You may receive partial credit for the work that is clearly on the right track. But if your
answer is largely irrelevant, you will receive 0 points.
4. This assignment has 4 questions (worth 20, 10, 20, 20 marks).
Q1 [20 Points] LP and IP
Consider the following primal LP and IP in standard form:
Maximize x2
Subject to −3x1 + 5x2 ≤ 8
7x1 + 3x2 ≤ 12
x1, x2 ≥ 0
For the IP, add the constraints that x1 and x2 are integers.
Plot the feasible region of this program. Note: You do not need to submit this with the assignment,
but it will be helpful to plot the feasible region. You can use any online graphing programs such as
desmos, fooplot, etc.
(a) [5 Points] What are the vertices of the feasible region of the primal LP? (No explanation is
needed.)
(b) [5 Points] What are the optimal solutions of the primal LP and IP? What are the corresponding
optimal objective values? (No explanation is needed.)
(c) [5 Points] Provide the dual LP of the primal LP above. Clearly indicate which dual variable in
your formulation corresponds to which primal constraint.
(d) [5 Points] What are the optimal solutions of the dual LP and its IP version? What are the
corresponding optimal objective values? Does strong duality hold for this particular pair of primal
and dual IP?
1
Q2 [10 Points] Team Building
You are putting together a team of m players. The m positions in your team are ranked (so there
is a position k for every k ∈ {1, 2, . . . , m}. You can select your players from a pool of n people,
denoted N = {1, . . . , n}. Assume n m.
Each person i ∈ N has a celebrity rating ci and suitability sik ∈ [0, 1] that measures how well
person i can play in position k on the team, where k ∈ {1, 2, . . . , m}. You are also given a relation
I ⊆ N ×N, where (i, j) ∈ I indicates that person i and person j are incompatible, and should never
be put on the team together. You can assume that this relation is symmetric, so (i, j) ∈ I if and
only if (j, i) ∈ I.
Your goal is to pick a team that maximizes the total celebrity rating of all selected players, subject
to making sure that the total suitability of players for their assigned positions is at least 1 and no
pair of players on the team is incompatible.
Give an linear or integer programming formulation for choosing the desired optimal team. Please
include a high-level verbal description of your program and justify the correctness of your solution.
Q3 [20 Points] P , NP , and coNP
For each decision problem below, state whether it belongs to P, NP, or coNP. Make the strongest
claim that you can. E.g. if you can show that a problem is in P, then you should claim so, as this
implies membership in NP and coNP. Similarly, e.g., if you think it is not in P but is in both NP
and coNP, then you should claim so, instead of claiming membership in just one of them. Note
that if you claim a problem is in NP or coNP, you do not have to show NP- or coNP-completeness.
In all the problems below, you may assume that a cycle in a graph means a simple cycle with no
repeated vertices. Assume all graphs are undirected. Z
+ is the set of positive integers.
Justify your answers. If you claim a problem is in P, give a polynomial-time algorithm and argue
its correctness and running time. If you claim a problem is in NP and/or coNP, then prove this
membership.
(a) [5 Points] AllSmallCycles (“ASC” for short)
Input: Graph G = (V, E), edge weights w : E → Z
+, vertex s ∈ V , bound B ∈ Z
+.
Question: Does EVERY cycle in G that includes vertex s have total weight at most B?
(b) [5 Points] AllLargeCycles (“ALC” for short)
Input: Graph G = (V, E), edge weights w : E → Z
+, vertex s ∈ V , bound B ∈ Z
+.
Question: Does EVERY cycle in G that includes vertex s have total weight at least B?
(c) [5 Points] SomeLargeCycles (“SLC” for short)
Input: Graph G = (V, E), edge weights w : E → Z
+, vertex s ∈ V , bound B ∈ Z
+.
Question: Does SOME cycle in G include vertex s and have total weight at least B?
(d) [5 Points] SomeSmallCycles (“SSC” for short)
Input: Graph G = (V, E), edge weights w : E → Z
+, vertex s ∈ V , bound B ∈ Z
+.
Question: Does SOME cycle in G include vertex s and have total weight at most B?
2
Q4 [20 Points] Friendly Representatives
There is a set of n people, denoted N = {1, . . . , n}. Some of them are friends with some other
people. This is captured by a friendship relation F ⊆ N ×N, where (i, j) ∈ F indicates that person
i and person j are friends. You can assume that friendship is symmetric, so (i, j) ∈ F if and only
if (j, i) ∈ F.
Here is a decision problem, termed FriendlyRepresentatives.
Input: Set of people N, friendship relation F, integer m.
Question: Does there exist S ⊆ N with |S| = m such that every person who is not in S is friends
with someone who is in S?
(a) [5 Points] Show that this problem is in NP.
(b) [15 Points] Show that this problem is NP-complete. For this part, you can use the fact that
ConnectedVertexCover problem, which takes a connected graph G = (V, E) as input and decides whether it admits a vertex cover of size exactly k, is NP-complete.
[Hint: The following gadget might be useful!]
3