Homework 5: Duality

Description

1. [3 points] Stigler’s supplement. Consider Stigler’s diet problem from Homework 2. To help further lower the cost of your diet, a friend o ers to sell you calcium supplements. Each calcium pill contains 500 mg of calcium.

1. 1. What is the most you would be willing to pay per pill? Hint: use duality!

1. 2. Suppose you can buy calcium pills at a cost $0.01 each. What is your new optimal diet? How much money does it save compared to the original optimal diet that didn’t have access to the calcium supplement?

2. [3 points] Dual interpretation. Suppose t 2 [0; 2 ] is a parameter. Consider the following LP:

minimize p + q + r + s

p;q;r;s

subject to: p r = cos(t)

q s = sin(t)

p; q; r; s 0

1. 1. Plot the optimal objective of this LP as a function of t. Can you explain what you see?

Hint: you can do this by looping over values of t, and solving a separate LP for each di erent value of t. To interpret what you’re seeing, you may want to separately consider the cases where cos(t) and sin(t) are positive or negative (four cases).

1. 2. Write out the dual LP. Interpret and solve the dual LP graphically. Does your solution agree with the solution found in part a)?

3. [3 points] Max- ow to min-cost. Consider the following graph (where blue nodes are sources, yellow nodes are relays, red nodes are sinks, and the edge capacity is labeled on each edge):

3	1	3	2
	4
2			3
	2

We wish to maximize the ow from the source to the sink nodes. Using the trick learned in lecture 7, you will formulate this max- ow problem as a min-cost problem. DO NOT use Julia to solve the problem. Simply state the answers to the questions.

1. Recall the min-cost model from class:

max c^>x

x

subject to Ax = b

p x q

Remember that A (the incidence matrix) is a property of the graph, not the speci c problem. Find A for this graph. What is x? What are p and q?

CS/ECE/ISyE 524 Introduction to Optimization L. Roald, Spring 2022

2. Modify the graph using the trick to formulate a min-cost problem. What is your new x, p, and q? What are c and b?

Remember from the lecture that the dual problem of this problem is the minimum cut problem.

3. What is the minimum cut of the this graph (you can just look at the graph to determine the minimum cut, and either give the solution either graphically or as a list of the edges in the cut)? What can you say about the values of the dual variables corresponding to the capacity constraints _ij and the nodal balance constraints _i?

2 of 2