Starting from:
$30
CS524- Homework 4 Duality Solved
1. [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 3 2
2
We wish to maximize the ow from the source to the sink nodes. Using the trick learned in lecture, you will formulate this problem as a min-cost problem. DO NOT use Julia to solve the problem. Simply state the answers to the questions.
a) Recall the min-cost model from class:
subject to Ax = b
p x q
Remember that A (the incidence matrix) is a property of the graph, not the specic problem. F ind A for this graph. What is x? What are p and q?
b) 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 lecture that the dual problem of this problem is the minimum cut problem.
c) 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 i j and the nodal balance constraints i ?
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
a) Plot the optimal objective of this LP as a function of t. Can you explain what you see? H int: you can do this by looping over values of t, and solving a separate LP for each dierent 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)?
1 of 2
CS/ECE/ISyE 524 Introduction to Optimization L. Roald, Spring 2020
3. [3 points] Electricity grid with storage. The town of Hamilton buys its electricity from the Powerco utility, which charges for electricity on an hourly basis. If less than 50 MWh is used during a given hour, then the cost is $100 per MWh. Any excess beyond 50 MWh used during the hour is charged at the higher rate of $400 per MWh. The maximum power that Powerco can provide in any given hour is 75 MWh. Here is what the average daily electricity demand looks like for Hamilton during the month of January:
Hour of day (AM)
1
2
3
4
5
6
7
8
9
10
11
12
Demand (MWh)
43
40
36
36
35
38
41
46
49
48
47
47
Hour of day (PM)
1
2
3
4
5
6
7
8
9
10
11
12
Demand (MWh)
48
46
45
47
50
63
75
75
72
66
57
50
The mayor of Hamilton is concerned because the high electricity use during evening hours is costing the city a lot of money. There is also risk of black-outs at around 7pm because the average demand is dangerously close to Powerco’s 75 MW limit.
To address these issues, the mayor purchased a large battery with a storage capacity of 30 MWh. The idea is that extra electricity could be purchased early in the day (at the lower rate), stored in the battery, and used later in the day when demand (and prices) are high.
a) How much money can the town of Hamilton save per day thanks to the battery? Assume that the battery begins the day completely drained.
b) How much money would be saved if the battery had an innite capacity? In this scenario, how much of the battery’s capacity is actually used? Should you be using duality here? Why, or why not?
c) Make a plot that shows (i) the typical energy demand vs time of day (ii) the electricity purchased using the strategy found in part a) vs time of day, and (iii) the battery capacity used as a function of time (draw all three plots on the same axes).
2 of 2
3 3 2
2
We wish to maximize the ow from the source to the sink nodes. Using the trick learned in lecture, you will formulate this problem as a min-cost problem. DO NOT use Julia to solve the problem. Simply state the answers to the questions.
a) Recall the min-cost model from class:
subject to Ax = b
p x q
Remember that A (the incidence matrix) is a property of the graph, not the specic problem. F ind A for this graph. What is x? What are p and q?
b) 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 lecture that the dual problem of this problem is the minimum cut problem.
c) 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 i j and the nodal balance constraints i ?
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
a) Plot the optimal objective of this LP as a function of t. Can you explain what you see? H int: you can do this by looping over values of t, and solving a separate LP for each dierent 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)?
1 of 2
CS/ECE/ISyE 524 Introduction to Optimization L. Roald, Spring 2020
3. [3 points] Electricity grid with storage. The town of Hamilton buys its electricity from the Powerco utility, which charges for electricity on an hourly basis. If less than 50 MWh is used during a given hour, then the cost is $100 per MWh. Any excess beyond 50 MWh used during the hour is charged at the higher rate of $400 per MWh. The maximum power that Powerco can provide in any given hour is 75 MWh. Here is what the average daily electricity demand looks like for Hamilton during the month of January:
Hour of day (AM)
1
2
3
4
5
6
7
8
9
10
11
12
Demand (MWh)
43
40
36
36
35
38
41
46
49
48
47
47
Hour of day (PM)
1
2
3
4
5
6
7
8
9
10
11
12
Demand (MWh)
48
46
45
47
50
63
75
75
72
66
57
50
The mayor of Hamilton is concerned because the high electricity use during evening hours is costing the city a lot of money. There is also risk of black-outs at around 7pm because the average demand is dangerously close to Powerco’s 75 MW limit.
To address these issues, the mayor purchased a large battery with a storage capacity of 30 MWh. The idea is that extra electricity could be purchased early in the day (at the lower rate), stored in the battery, and used later in the day when demand (and prices) are high.
a) How much money can the town of Hamilton save per day thanks to the battery? Assume that the battery begins the day completely drained.
b) How much money would be saved if the battery had an innite capacity? In this scenario, how much of the battery’s capacity is actually used? Should you be using duality here? Why, or why not?
c) Make a plot that shows (i) the typical energy demand vs time of day (ii) the electricity purchased using the strategy found in part a) vs time of day, and (iii) the battery capacity used as a function of time (draw all three plots on the same axes).
2 of 2
1 file (99.9KB)
