15.094- Homework 4 Solved

1           Polyhedral uncertainty and extreme points
                                       minimize        cTx + maxqTy(b)

b∈U                      (1) subaject to       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        cTx +     max     qTy(b)

b∈ext(U)

(2)

                                   subject to       Tx + Wy(b) ≥ b,        ∀b ∈ ext(U)

Hint 1: Problem (1) is equivalent to

minimize                  cTx + maxQ(x,b) b∈U

where the second-stage cost function is given by

Q(x,b) =        minimize qTy subject to       Tx + Wy ≥ b.

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
0
 
subject to
y1(b) + y2(b) ≤ 1 y1(b) ≥ b1
 
 
y1(b) ≥ −b1 y2(b) ≥ b2 y2(b) ≥ −b2

∀b ∈ U
(3)
where the uncertainty set is

.

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 optimization, 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.

,

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 function 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 between nodes i, j with the following rule:

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 location 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 , 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.  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 convergence 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 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 
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 
Thinking about the relationship between P∀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 locations as we change RD (and thus P) at the same safety factors ρ and Γ. Devise 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: 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 intuition?

As always, please come to office hours or use the Discussion thread if you have any questions.