15.094 Homework 2 Solved

1 General Convex Uncertainty Sets 1.1

Let

h(z)=􏰄r αi|(di)Tz−βi|pi, i=1 pi

whereαi >0andpi >1,foralli.
Derive the robust counterpart of the constraint

(a+Pz)Tx≤b, ∀z∈Z={z:h(z)≤Γ}. (Hint: You may use the results from the textbook without proof).

1.2

The so-called entropy uncertainty set is defined as

􏰁 􏰀􏰀 􏰄L 􏰂 L

Z= z∈R 􏰀􏰀∥z∥∞≤1, {(1+zi)log(1+zi)+(1−zi)log(1−zi)}≤β ,

􏰀

i=1
where log denotes the natural logarithm or logarithm in base e.

Derive the robust counterpart of the constraint (a+Pz)Tx≤b, ∀z∈Z

2 Cloud computing system

(Please use the code provided in HW2 CloudComputing.jl/ipynb for this ques- tion. Data generation functions, cost vectors and plotting tools are provided.)

Consider a cloud computing system over a finite time horizon t ∈ {1, . . . , T }, with a set of servers, s ∈ {1,…,S}. To lower verbosity, we will use S inter- changeably to refer to set {1, . . . , S}. Each server s ∈ S has a finite amount of resources indexed by i ∈ {1,…,I}.

1

ri,s ∈R+, ∀i∈I, s∈Sisthefixedcapacityofresourceiatservers. It costs a constant Fi to maintain one unit of resource i at server s in each time period t. The optimization problem is to find the cost-minimizing value of fixed resources ri,s subject to uncertain demand.

The demand is represented in time period t with Di,s,t jobs arriving at the facility, requesting resource i from server s to complete. We must never fail to satisfy demand, since folks need their Netflix! There are three ways to complete each job:

• Serve Di,s,t in the current server using fixed capacity ri,s.
• Serve Di,s,t in the current server by temporarily expanding ri,s of server

s in time t by ei,s,t, while incurring an additional cost of Vi per unit.
• Transfer some or part of the job (ui,s1,s2,t) from server s1 to server s2 with

spare capacity in resource i, costing Ci for a transfer from server s1 to s2.

There are some additional constraints on the system. Expansions ei,s,t result in increases in the temperature of each server. Our temperature surrogate is hs,t, which is the three time step moving average of expansions in all resources (moving average of 􏰃i∈I ei,s,t) for each server s at each time t. hs,t cannot exceed 1. Assume that the temperature of each server is zero at all time periods before t = 1.

To keep it simple, we will assume that servers may complete fractional jobs, and capacities of resources are continuously variable.

2.1

Please formulate the nominal linear optimization problem, minimizing the sum of fixed, expansion and reallocation costs subject to demand and temperature constraints.

2.2

Use JuMP/JuMPeR to solve the nominal capacity allocation problem, using the generate data function provided, with I = 6 resources, S = 5 servers, over T = 25 periods. Please include the plot for matrix r (your fixed capacity allocation), your optimal cost, the time-statistics plots of expansions e, as well as the temperature plot. (Please use the plotting functions provided for your convenience. There should be four plots total.) Examine the temperature plot. Does your system anticipate peaks? How can you tell?

2.3

Solve the nominal problem, but without the ability to transfer jobs (ui,s1,s2,t = 0, ∀ i, s1, s2, t). Provide the same four plots as above. How does this affect the cost and the allocation of r and e? What is the intuition behind it? As far as

2

the system temperature, can the system anticipate peak demand? How is the system temperature response different compared to the problem with transfers?

2.4

Write the robust version of the capacity allocation problem by adding uncer- tainty d to demands (Di,s,t + di,s,t) in your optimization problem. The uncer- tainty in demand is decoupled for each server; assume that uncertain variables d1:I,s,1:T for each server s lie in a budget uncertainty with bounded support [−1, 1] so that we are guaranteed to be feasible for %95 of uncertain outcomes. Please provide the form of your uncertainty sets as well as computations for the safety factors.

2.5

Solve the RO problem in JuMPeR/JuMP with and without job transfers. (The robust counterpart will take a lot longer to solve.) Please provide plots of r and the temperature, as well as the costs. (There should be four plots). How do your r, cost and the temperature plots change? How are the robust solutions similar or different? What do the results say about the ability of server farms to buffer variable demand?

2.6

Include the source code for the nominal and robust formulations in your prob- lem set.

As always, please come to office hours if you have any questions or concerns.

3