CS524 Homework 4- Duality Solution

(Submit a single pdf image of your Jupyter notebook via Canvas.)
(Please denote the start of each question in your Julia workbook using a LARGEFONT.) (Starter code is provided for some questions.)
1. [5 points] Network reliability. We consider the telecommunications network represented in Figure 1. This network consists of eleven sites connected by bidirectional lines for data transmission. Each line has a bandwidth (i.e. maximum rate for data transmission) of 1.0. We are interested in the total bandwidth for the connection between nodes 10 and 11, and what happens to this bandwidth if a node is eliminated.

Figure 1: Telecommunications network
(a) Formulate the problem as a maxflow problem and solve. (Hint: Each bidirectional line can be represented by two directional edges, one in each direction. That is, if there is a line connecting nodes i and j, then [i,j] and [j,i] are both edges in the edge set. See the definition of the set ”edges” in the starter file.)
(b) By adjusting your model for part (a), **not** recoding the edge set from scratch, find what happens if node 3 is eliminated from the graph. (That is, all lines connected to node 3 can no longer carry data.) What is the new maximum bandwidth between nodes 10 and 11?
(c) Can your maxflow problem be reformulated more compactly by using birectional lines? That is, redefining the edge set by eliminating duplicated lines (see the starter code) while allowing data to flow in either direction. Write down your reformulation of part (a) and code and solve it in
Julia.
2. [3 points] Stigler’s supplement. Consider Stigler’s diet problem from Homework 2. To help further lower the cost of your diet, a friend offers to sell you riboflavin supplements. Each riboflavin pill contains 1 mg of riboflavin.
(a) What is the most you would be willing to pay per pill? Hint: use duality!
(b) Suppose you can buy riboflavin pills at a cost $0.01 each. Add this new “food” to your basic diet problem formulation and re-solve to obtain a new optimal diet.
• How much money does it save compared to the original optimal diet that didn’t have access to the supplement?
1 of 2
• How do the other foods in the diet change as a result of introducing the supplements into the diet?
3. [3 points] Dual interpretation. Suppose t ∈ [0,2π] is a parameter. Consider the following LP:
min
p,q,r,s p + q + r + s
subject to: p − r = cos(t)
q − s = sin(t) p,q,r,s ≥ 0
(b) Write out the dual LP. Interpret and solve the dual LP graphically. Does your solution agree with the solution found in part a)?
2 of 2