Description
1 Polyhedral uncertainty and extreme points
minimize cT x + max qT y(b) b∈U
subjectto Tx+Wy(b)≥b, ∀b∈U.
Let U ⊆ Rn be a polyhedron and denote its extreme points by ext(U).
Show that the objective value of Problem (1) is equal to that of minimize cT x + max qT y(b)
b∈ext(U )
subjectto Tx+Wy(b)≥b, ∀b∈ext(U)
Hint 1: Problem (1) is equivalent to
minimize cT x + max Q(x, b)
b∈U
where the second-stage cost function is given by
Q(x, b) = minimize qT y subjectto Tx+Wy≥b.
(1)
(2)
Hint 2: You may use the fact that maximizing a convex function over a polyhedron P is equivalent to maximizing over ext(P).
2 Feasibility of LDRs
Consider the two-stage adaptive optimization problem
minimize subject to
0
y1(b) + y2(b) ≤ 1
y1(b) ≥ b1
y1(b) ≥ −b1 (3) y2(b) ≥ b2
y2(b) ≥ −b2
∀b ∈ U 1
where the uncertainty set is
U =b∈R2 :∥b∥1 ≤1.
First, show that Problem (3) has a feasible solution. Then, show that Problem (3) becomes infeasible if we restrict to linear decision rules.
3 Adaptive Facility Location Problem
In this problem, we will explore a canonical example of adaptive robust opti- mization, which is the facility location problem. The nominal problem is given by the following, and is provided in HW4 facilityLocation.jl, along with the plot solution method which will allow you to compare your results.
min
y(·),x
s.t.
nmn cijyij +fixi
i=1 j=1 n
yij ≥dj, i=1
m
yij ≤ sixi, j=1
i=1
∀d∈D, ∀j∈[m],
∀i ∈ [n],
yij ≥0, ∀i∈[n], ∀j∈[m],
x ∈ {0,1}n.
i ∈ [n] is a possible location for a facility, and j ∈ [m] is a demand node. ci,j is the cost of transportation of goods from facility i to destination j, and si is the capacity of facility i. It costs fi to construct facility i, and the demand at location j is dj and uncertain, lying within uncertainty set D. The binary construction decisions x precede the delivery decisions y, and thus the problem may be formulated as an adaptive robust optimization problem.
3.1
Please solve the nominal optimization problem using the provided code in HW4 facilityLocation.jl. Provide the plot using the plot solution func- tion provided, as well as total, facility and transportation costs.
3.2
We want to account for uncertainties in demand. Assume we know that our demand uncertainty is correlated among nodes based on pairwise distances be- tween nodes i, j with the following rule:
2
0.2exp(− 1 Di,j), if Di,j ≤ RD
Pi,j = RD 0,
otherwise
where Di,j is the Euclidian distance between nodes i and j, and where (Pz)j is the uncertain perturbation on demand dj at node j, and RD is the radius of influence. We will assume that z belongs to a budget uncertainty with ||z||∞ ≤ 1 and ||z||1 ≤ 5.
Using this set, please formulate in JuMP/JuMPeR the robust facility loca- tion problem with fixed recourse, where y(z) = y. Solve it with RD = 0.25, providing the plot, the facility cost and transportation cost.
Please provide intuition about the choice of 1 and 5 as safety factors to the uncertainty set, especially considering the shape of Pi,j.
3.3
We are exploring the network effects of the radius of influence RD on our facility locations and transportation costs. Please solve the fixed recourse problem for RD ∈ {ε : 0.05 : 0.6}, providing the following tabulated data:
• Value of RD
• Sum of all values in matrix P
• Total cost
• Facility cost
• Transportation cost
• Number of nonzero elements of P • Optimal number of facilities
(Note the ε to avoid the singularity at 0. ε = 10−5 should be sufficient.) Provide network plots of all unique resulting facility configurations.
Assess the results and explain your intuition about the influence of RD. Do the results make sense? How is RD related to the uncertainty set/scenarios?
3.4
Please formulate in JuMP/JuMPeR the adaptive robust problem with linear policies, where y(z) = Yz + Y0. Solve (or try to solve) the problem for the nominal RD = 0.25.
(Note: This problem will take a lot longer to solve. Give it time; depending on your machine it might take 24 hours or more. Solving the problem within your terminal instead of a jupyter notebook will allow you to track its conver- gence through the Gurobi log. This will give some value insight into what is happening; we encourage you to optimize at least until the first feasible integer
3
solution, given by an asterisk in the log. No worries if you don’t have the time or patience for this; we would like to see that you can formulate the problem.)
We have provided the network plot as well as the costs below: • Total cost: 36.716
• Facility cost: 23.323
• Transportation cost: 13.393
Figure 1: The adaptive facility location result
How do our facility allocations change? Why might affine decision rules confer a big cost reduction compared to fixed recourse in this case? (Hint: think about the server optimization problem from HW2.)
3.5
Please provide your source code.
3.6 Extra credit (10 points)
In practice, we didn’t solve the binary ARO problem directly, since the solution did not converge after over 24 hours on an 8-core i7 machine. We used an inexact but good heuristic to dramatically speed up the solution process, which reduced solution time to less than a minute. Come up with a method to speed up the solution of the binary ARO problem, and present the results.
3.7 Extra credit (15 points)
Thinking about the relationship between ∀i,j Pi,j, Γ and total cost, it is clear that the possible uncertain scenarios grow as the radius of influence increases. This means that we are not doing an apples-to-apples comparison of our loca- tions as we change RD (and thus P ) at the same safety factors ρ and Γ. Devise
4
and present a method to scale P (and optionally ρ and Γ) so that (1) your scaled {P ̄, ρ ̄, Γ ̄ : RD = 0.25} is the same as the nominal case, (2) the inverse exponential properties in P with pairwise distances are preserved, and (3) the comparison is more fair.
Assess your new results by solving the fixed recourse problem for RD ∈ {ε : 0.05 : 0.6} and providing the same tabulated data as in 3.3. Provide the unique facility configurations as well. Does your facility allocation change in this new comparison? Does the behavior of allocations with respect to RD fit your intu- ition?
As always, please come to office hours or use the Discussion thread if you have any questions.
5
