Homework 4: Duality

1. Max-Flow / Min-Cost. Here’s a story from Harry Potter. Ollivander, the famous wand maker of Diagon Alley, has a logistics problem. He produces wands of seven di erent types for which he must arrange delivery to a favored customer, using ve owls. There’s a limit to the total number of wands that each owl can carry, shown in the following table.

Owl
1
2
3
4
5






Max Wands That Can Be Carried
6
5
4
2
10







Each owl can carry at most one wand of each type. Ollivander wants to deliver as many total wands to his customer as possible.

(a) Formulate and solve in Julia a max- ow problem to determine the maximum number of wands that can be delivered.

NB: There are various ways to formulate this problem, but you need to formulate it as a max- ow problem.

Have your code output clearly the optimal objective value (the maximum total number of wands delivered), together with the number of wands to be carried by each of the ve owls, and the number of each type of wand that can be shipped.

Hint: Your network should have the following nodes: one source node (Ollivander’s store), a layer of 7 nodes in which each node represents one of the types of wands, a layer of 5 nodes in which each node represents an owl, and a destination node (the customer). (14 nodes in total!) You need to de ne the edges (arcs) and the capacities on each each edge to ll out the de nition of the max- ow problem.

(b) As you know, the dual of max- ow is min-cut. Min-cut can be viewed as partitioning the network into two subsets of nodes, one subset containing the source and the other containing the destina-tion, by removing a subset of edges in such a way that the sum of the maximum capacities on the edges removed is minimized. For Ollivander’s problem above, at the solution of the min-cut version, what is the subset of nodes containing the destination (customer) node? Explain.


2. 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 (that’s half a gram) of calcium.

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

b) Suppose you can buy calcium 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 calcium supplement?


3. Dual interpretation. Suppose t 2 [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


1 of 2
CS/ECE/ISyE 524    Introduction to Optimization    Steve Wright,    Spring 2021


    a) 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).

    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