36901 Stochastic Optimization – Winter 2019
John R. Birge, The University of Chicago Booth School of Business
You have three days (until 5:00PM, Monday, February 18, 2019) to complete this exam and return your solutions online in Canvas (or, if you want to submit hard copy only, turn into my box
in the faculty lounge). You may use the text and external references but
you should not collaborate with others and should cite any outside reference that you use. For numerical solutions, you may use any solver of your choice.
1. (20 total) Consider an online retailer who is trying to decide on products to offer to online customers where there are j = 1, . . . , n different products with unit cost cj . The retailer has a budget restriction to pay no more than b for all products they purchase. Each product j for sale has an associated selling price qj. Demand for the products is given by a vector d, which is not known until after the retailer has determined their order quantity. Any leftover items after the sales period are salvaged at value vj.
(a) [5] Formulate a model to minimize net expected total cost as a two-stage stochastic program.
(b) [5] Suppose the demand has a continuous distribution. Provide a set of optimality conditions that can be solved to obtain an optimal solution to this model.
(c) [5] Consider a setting with 3 products with prices p = (7,5,9), costs c = (5,2,6), salvage values v = (4, 1, 4), and where the demand is normally distributed with means μ = (10, 20, 15), standard deviations (10, 20, 15), and correlations of 0.5 between every pair of products. Suppose the budget is b = 150. Solve for an optimal recourse problem solution.
(d) [5] Find the EVPI and VSS for th
is model.
2. (15) In his presentation in the OM/MS seminar, Levi Devalve discussed an approximate solution to the K-matching problem:
max E [fω (A)], A||A|≤K
where A ⊂ U is a set of locations and fω(A) is the cost of matching supply and demand nodes through these locations. He showed that this problem cannot be solved directly by the linear relaxation. As a simpler example, consider a case where there is unit cost ci for supplying potential supply locations i = 1, . . . , m with a single unit of a product. These supply decisions must be made in advance of observing random demand d(ω)j at a set of locations j = 1, . . . , n. The demand can be satisfied (without delay costs) from any locations i with unit transportation costs qij. If some demand cannot be satisfied from any of the locations, then there is a cost q0 per unit of unsatisfied demand.
(a) [5] Suppose demand is given by a set of scenarios, dk , k = 1, . . . , N each with probabilities pk. Formulate this as a two-stage stochastic program.
(b) [5] Show that an optimal solution to your model exists in which min(n,m) locations have strictly positive supply.
1
(c) [5] We would like to know if the linear relaxation of a model in which the initial supply decisions are restricted to be integers can yield an integer solution. A result on total unimodularity of a matrix is the following:
An m×n matrix A is totally unimodular if and only if for each J ⊂ {1,…,n}, there exists a partition (J1,J2) of J such that j∈J1 aij − j∈J2 aij| ≤ 1 for i = 1,…,m.
Use this result to show that a linear relaxation has an integral optimal solution if all initial data are integral.
3. (20) Consider an investment problem with a mean-CVaR objective, i.e., the objective is to minimize the sum of the negative of expected return and the CVaR risk measure. Suppose there are n investments with returns that are normally distributed with mean return vector μ and covariance matrix Σ,the CVaR tail probability is α, and the weight on the CVaR risk term is γ relative to the weight on the negative expected return. Assume that you cannot take short positions so that all investment amounts are non-negative and that you begin with one unit of wealth to invest.
(a) [5] Formulate this model as a stochastic program to obtain an optimal solution x∗.
(b) [5] Prove conditions for a solution of your stochastic model to be optimal and simplify
them as much as you can.
(c) [5] Suppose you solve the sample-average approximation of this model with a set of
observed return vectors ri,i = 1,…,N. Formulate this model to obtain a solution xN.
(d) [5] Derive the distribution of u such that √N(xN − x∗) converges to u as N → ∞.
2