CS 570 – HW 5
Due April 16, 2021 (by 4 AM Pacific Time)
1 Maximizing Profit (15 points)
A furniture company produces three types of couches. The first type uses 1 foot of framing wood and 3 feet of cabinet wood. The second type uses 2 feet of framing wood and 2 feet of cabinet wood. The third type uses 2 feet of framing wood and 1 foot of cabinet wood. The profit of the three types of couches is $10, $8, and $5, respectively. The factory produces 500 couches each month of the first type, 300 of the second type, and 200 of the third type (with no wood resources leftover). However, this month there is a shortage of cabinet wood by 600 feet, but the supply of framing wood is increased by 100 feet. How should the production of the three types of couches be adjusted to minimize the decrease in profit? Formulate this problem as a linear programming problem.
Solution + Rubric:
Explanation (3 points): Suppose the number of couches of each type that are produced in addition to the usual be x1,x2,x3. The net additional profit is 10×1 + 8×2 + 5×3 which should be maximized (equivalent to minimizing de- crease in profit). This objective is subject to the following constraints. The additional consumption of framing wood is x1 + 2×2 + 2×3 which can be at most 100, while the additional consumption of cabinet wood is 3×1 + 2×2 + x3 which can be at most -600 (owing to a shortage of 600). The total number of couches of each type is 500 + x1, 300 + x2, 200 + x3 resp., all of which should be non- negative. The resultant LP formulation is as follows:
maximize: subject to:
10×1 + 8×2 + 5×3 3 points 3×1+2×2+x3≤−600, 3points
x1 + 2×2 + 2×3 ≤ 100, x1 ≥ −500,
x2 ≥ −300,
x3 ≥ −200.
3 points 1 point 1 point 1 point
Alternatively, define x1, x2, x3 as the decrements in couch quantities produced to get the following LP:
1
minimize: subject to:
10×1 + 8×2 + 5×3
3×1 + 2×2 + x3 ≥ 600, x1 +2×2 +2×3 ≥ −100, x1 ≤ 500,
x2 ≤ 300,
x3 ≤ 200.
Alternatively, define x1,x2,x3 as the new couch quantities produced. This re- quires computing the default wood supplies as 2300 and 1500 units, and in turn, the new wood supplies as 1700 and 1600 units. Then, we get the following LP:
maximize: subject to:
10×1 + 8×2 + 5×3
3×1 + 2×2 + x3 ≤ 1700, x1 +2×2 +2×3 ≤ 1600, x1 ≥ 0,
x2 ≥ 0,
x3 ≥ 0.
More details on the rubric:
• The scoring break-up is the same in all 3 cases: 3 for explaining the variables and constraints, 3 for objective, 3+3+1+1+1 for constraints as shown.
• In each of the cases, the objective maxf(x) can be switched to min−f(x) and vice versa.
• Any objective expression f(x) can also be expressed as f(x) + c for some constant c (e.g., the usual month’s profit).
• 2 point penalty if max/min is incorrect
• 2 points penalty each if only the inequality signs are incorrect in the first
2 constraints (wood supply constraints)
2
2 Dual Program (15 points)
Consider the following linear program:
max(3×1 + 2×2 + x3)
subject to
x1 − x2 + x3 ≤ 4 2×1 +x2 +3×3 ≤6 −x1 + 2×3 = 3 x1 + x2 + x3 ≤ 8 x1,x2,x3 ≥0
Write the dual problem. You do not need to demonstrate intermediate steps.
Solution + Rubric:
Let dual variables y1,y2,y3 correspond to the three ≤ constraints and let y4 correspond to the = constraint. Then, we get the dual LP as follows:
min: 4y1 +6y2 +8y3 +3y4 subject to: y1 +2y2 +y3 −y4 ≥3,
−y1 +y2 +y3 ≥2,
y1 +3y2 +y3 +2y4 ≥1, y1,y2,y3 ≥0.
Alternatively, a more classical approach could be that the equality constraint can be broken down into a ≤ and a ≥, with corresponding dual variables y4 and y5, to get the following dual:
min: 4y1 +6y2 +8y3 +3y4 +3y5 subject to: y1 +2y2 +y3 −y4 −y5 ≥3,
−y1 +y2 +y3 ≥2,
y1 +3y2 +y3 +2y4 +2y5 ≥1, y1,y2,y3,y4 ≥ 0,y5 ≤ 0.
Scoring breakup (3+3+5+4):
• 3 Points for correct no. of dual variables (four/five in the two cases).
• 3 points for having three constraints (excluding variable bounds).
• 5 points for all coefficients and inequality signs (2 point penalty for incor- rect inequality signs, 2 point penalty for incorrect objective, neither to be repeated if the mistake is due to incorrect number of variables/constraints which is already penalized as aforementioned).
• 4 points for variable bounds.
3
• No penalty for negating all the coefficients of a variable and switching the bound — the most likely/common instance of this would be using y5 ≥ 0 in the second solution and having all the coefficients of y5 negated.
4
3 Spectrum Management (15 points)
Spectrum management is the process of regulating the use of radio frequencies to promote efficient use and gain a net social benefit. Given a set of broadcast emitting stations s1,…,sn, a list of frequencies f1,…,fm, where m ≥ n, and the set of adjacent stations {(si,sj)} for some i,j ∈ [n]. The goal is to assign a frequency to each station so that adjacent stations use different frequencies and the number of used frequencies is minimized. Formulate this problem as an integer linear programming problem.
Solution + Rubric:
Define variables (2 points): Let binary xij denote whether station si uses fre- quency fj or not. Let binary uj denote whether frequency fj is used or not.
Let E denote the set of pairs of adjecent stations. (Given as input) Here is the IP formulation:
minx,u : subject to:
nk=1 uk
xij +xkj ≤1, ∀j∈[m]∀(si,sk)∈E nj=1 xij = 1 ∀i ∈ [n],
xij ≤uj ∀i∈[n]∀j∈[m],
3 points
3points 3 points 3points
1 point
uj ∈{0,1}∀i∈[n],
xij ∈{0,1}∀i∈[n]∀j∈[m].
Explanation: The objective minimizes the number of frequencies used. Con- straint 1 ensures any adjecent stations si,sk do not have the same frequency fj for any j. Constraint 2 ensures each station is assigned exactly one frequency. Constraint 3 ensures that any frequency j is counted as used (uj = 1), if it is assigned to any station (xij = 1). Finally constraints 4,5 ensure that the variables take binary values.
Side Note: This is identical to the well-known Garph Coloring problem. Rubric details:
• Full points for individual objective/constraints only if the explanation is provided. 1 point penalty for each missing/incorrect explanations (max penalty 3 if no explanations provided).
• 1 point penalty for each missing/incorrect ∀ descriptors (max penalty 2 if none are provided).
• A maximum of 8 points for a partially incorrect approach, such as not defining any uj, and attempting to capture the objective with just xij’s
5
4 Short Questions (15 points)
Prove or disprove the following statements.
1. IfA≤p BandBisinNP-hard,thenAisinNP-hard.
2. IfA≤p BandBisinNP,thenAisinNP.
3. If 3-SAT ≤p 2-SAT, then P = NP.
4. Any NP problem can be solved in time O(2poly(n)), where n is the input size and poly(n) is a polynomial.
5. If a problem A ≤p B, then it follows that B ≤p A.
Solution + Rubric:
1. False (2 points). This only suggests B is “at least as hard” as A. A need not be NP-hard.
2. True (5 points). Since A ≤p B, we can construct an instance of B of size m where m is at most O(nc) for some integer c, with n being the size of the A instance. Further, since B is in NP, there exists a certificate of size O(md) for some integer d, and a certifier that runs in time O(mf ) for some integer f. To show that A ∈ NP, we provide a certificate for the B instance that is obtained from the reduction of the A instance. The size of this certificate is O(md) = O(ncd). The certifier would first obtain the B instance in polynomial time (since A ≤p B) and then run the certifier of B which runs in time O(mf ) = O(ncf ), thus, also polynomial in n. Thus, A has a certificate of polynomial size and a certifier running in polynomial time, hence, A ∈ NP.
Scoring: 2 points for answer, 3 for explanation — 1.5 each for showing poly-size certificate and poly-time certifier.
3. True(2 points). 2-SAT is in P. Hence, 3-SAT ≤p 2-SAT would mean that 3-SAT is in P. 3-SAT being NP-hard, every NP problem can be reduced to 3-SAT, and in turn, can be solved in polynomial-time. Thus, P=NP.
4. True(4 points). Since each certificate is of polynomial size, say, O(nc), there are O(2nc ) different possible certificates. We can check for each of them in polynomial time, and output yes if one is found. Thus, in total O(2poly(n)) time suffices.
Scoring: 2 points for answer, 2 for explanation.
5. False(2 points). ≤p is not a symmetric relation. As a counter-example,
consider a case that A is a problem in P , while B is not.
No penalty if the explanation is omitted for 1,3,5.
6
5 Finding a Satisfying Assignment (20 points)
Assume that you are given a polynomial time algorithm that given a 3-SAT instance decides in polynomial time if it has a satisfying assignment. Describe a polynomial time algorithm that finds a satisfying assignment (if it exists) to a given 3-SAT instance.
Solution + Rubric:
Let Φ(x1,x2,…,xn) = c1 ∧c2 ∧…∧cm be the boolean formula corresponding to a 3-SAT instance where c1,c2,…,cm are the clauses and x1,x2,…,xn are the variables. Suppose the algorithm A takes a CNF formula and outputs 1 if it is satisfiable, and 0 if not.
If A(Φ((x1, x2, . . . , xn))) = 0, then return that the instance is non satisfiable. If A(Φ((x1,x2,…,xn))) = 1, then, i.e., given Φ is satisfiable, we can find an assignment for x1 as follows. If A(Φ((1, x2, . . . , xn))) = 1, then we can set x1 = 1 and be guaranteed that Φ1(x2,x3,…,xn) := Φ(1,×2,…,xn) is satis- fiable. Else, we can set x1 = 0 and be guaranteed that Φ′1(x2,x3,…,xn) := Φ(0, x2, . . . , xn) is satisfiable. We can continue iteratively with Φ1 or Φ′1 resp. to find the subsequent assignments. (E.g., say Φ1 is satisfiable. Then, in the sec- ond iteration, we find an assignment for x2 by computing A(Φ1 (1, x3 , . . . , xn )), and setting x2 = 1 if it returns 1, or x2 = 0 otherwise, and so on.)
This will lead to n iterations with one call to A per iteration. In each iteration, finding the new formula by plugging the value of a variable takes O(m) time. Hence, we can find the assignment in polynomial time.
Rubric details:
• Any iterative/recursive algorithm that runs with linearly many calls to A is acceptable. Describing in words or a pseudo-code are both okay.
• 2 point penalty if polynomial runtime is not explained.
• 3 point penalty if it calls A more than linearly many times but still poly-
nomial.
• At most 5 points allotted for an algorithm with exponentially many calls to A.
7
6 Multi-Lane Highway (20 points)
The government wants to build a multi-lane highway across the country. The plan is to choose a route and rebuild the roads along this route. We model this problem with a simple weighted undirected graph with the nodes denoting the cities and the edges capturing the existing road network. The weight of an edge denotes the length of the road connecting the corresponding two cities.
Let duv denote the shortest path distance between nodes u and v.
Let d(v,P) denote the shortest path distance from a node v to the closest node on a path P (i.e. minduv).
u∈P
Next, we define the aggregate remoteness of P as r(P ) = d(v, P ).
v∈V
In the example shown in the figure below, path P = ABCD is the highway.
Then, d(A,P) = d(B,P) = d(C,P) = d(D,P) = 0, while d(X,P) = dXB = 2, d(Y,P) = dY B = 5, and, d(Z,P) = dZC = 7. The remoteness of path ABCD is 0 + 0 + 0 + 0 + 2 + 5 + 7 = 14.
The government wants a highway with the minimum aggregate remoteness, so that all the cities are somewhat close to the highway. Formally, we state the problem as follows, “Given a graph G, and a number k, does there exist a path P in G having remoteness r(P) at most k”? Show that this problem is NP-complete by reduction from the Hamiltonian Path problem.
Solution + Rubric:
Call this problem REMOTE-PATH.
REMOTE-PATH ∈ NP (6 points): A path will be a certificate (thus, poly-size). For each vertex v, d(v, P ) can be computed by first running Dijkstra from v and then finding the closest point on P . Adding d(v, P ) for all the nodes v gives the total remoteness. Thus, the certifier runs in polynomial time.
NP-hardness (14 points): We show this with a reduction from Hamiltonian Path (HP). Consider an HP instance graph G = (V, E). Construct a weighted graph H by assigning arbitrary positive weights to all the edges in E. Pass this weighted graph H and k = 0 as input to REMOTE-PATH. We show that G has a hamiltonian path if and only if H has a path with zero remoteness. To
8
prove the first direction, suppose P is a hamiltonian path of G. Since, all the nodes lie on P, we have d(v,P) = 0 ∀v ∈ V, and hence, r(P) = 0. Hence, REMOTE-PATH outputs ‘Yes’. For the other direction, suppose H has a path with zero remoteness, say P. If there is a node v ∈/ P, then d(v,P) > 0 since all the edge-weights are positive. Hence, as r(P) = 0, P must contain all the nodes, thus, G indeed has a hamiltonian path.
Since assigning the weights is done in O(|E|) time, the reduction is poly-time. Rubric details:
• Showing in NP: 2 points for the certificate, 3 points for the certifier (need to explain how the remoteness can be computed). 1 point for mentioning polynomial time.
• Reduction for NP-hardness: 5 for construction (3 for Adding strictly positive weights to unweighted HP instance, 2 for setting k = 0). 4+4 for proving each direction (partial scoring for unclear/missing proof steps). 1 for mentioning that the reduction is poly-time.
• Maximum 5 points for a reduction TO Hamiltonian Path. (i.e. taking the city graph and checking if it has a hamiltonian path)
9