Robust p-median problem with vector autoregressive demands

Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work Robust p-median problem with vector autoregressive demands Emilio Carrizosaa, Alba V. Olivares-Nadal aand Pepa Ram´ırez-Cobob aUniversity of Sevilla bUniversity of C´adiz 28th November 2015 E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work 1Motivation and Background State of the art VAR 2Problem formulation 3Theoretical findings 4Concluding remarks and future work E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR 1Motivation and Background State of the art VAR 2Problem formulation 3Theoretical findings 4Concluding remarks and future work E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR Classic p-median problem min x,y n X i=1 wi m X j=1 cij xij s.t                    m X j=1 xij = 1 ∀j xij ≤yi∀i,j m X j=1 yj=p yj,xij ∈ {0,1} (p-median) E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR Classic p-median problem min x,y n X i=1 wi m X j=1 cij xij s.t                    m X j=1 xij = 1 ∀j xij ≤yi∀i,j m X j=1 yj=p yj,xij ∈ {0,1} (p-median) Uncertain in practice E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR Background Robust location problems Uncertainty over the demand: Distributional assumptions Scenario analysis Given nominal values for future demands Construct uncertainty sets for the demand around nominal value E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR Background Robust location problems Uncertainty over the demand: Distributional assumptions Scenario analysis Given nominal values for future demands Construct uncertainty sets for the demand around nominal value E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR Background Robust location problems Uncertainty over the demand: Distributional assumptions Scenario analysis Given nominal values for future demands Construct uncertainty sets for the demand around nominal value E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR Uncertainty set around nominal value E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR Example: Baron et al. (2011) uncertainty sets 5 10 15 20 0 50 100 150 200 Baron Uncertainty Sets AR(1) demand εt=0.15+(1−0.15)εt−1 Feasible realizations sd= 45 sd= 45.06 sd= 44.56 E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR Example: Baron et al. (2011) uncertainty sets 5 10 15 20 0 5 10 15 20 25 Baron Uncertainty Sets MA(1) demand εt=0.15+(1−0.15)εt−1 Feasible realizations sd= 5.27 sd= 4.75 sd= 4.54 E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR Motivation Differences with Baron et al. (2011) Given nominal values for the demand →VAR coefficients Demand realization for time tdoes not depend on the realization of the demand for time t−1→realization of the demand must preserve inner behaviour We have already used robustness+AR processes with very good results: Carrizosa, E., Olivares-Nadal, A.V., & Ram´ırez-Cobo, P. Robust newsvendor problem with autoregressive demand. To appear in Computers & Operations Research. E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR Motivation Differences with Baron et al. (2011) Given nominal values for the demand →VAR coefficients Demand realization for time tdoes not depend on the realization of the demand for time t−1→realization of the demand must preserve inner behaviour We have already used robustness+AR processes with very good results: Carrizosa, E., Olivares-Nadal, A.V., & Ram´ırez-Cobo, P. Robust newsvendor problem with autoregressive demand. To appear in Computers & Operations Research. E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR 1Motivation and Background State of the art VAR 2Problem formulation 3Theoretical findings 4Concluding remarks and future work E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR Vector Autoregressive Models of order p(VAR(p)) Multivariate time series: correlation along time and between clients. VAR(p) wt=α α α+ p X k=1 Akwt−k+  t wt=w1 t, ..., wn t0: the demands of all clients at time t, known up to time T, A1, ..., Ap∈Rn×n,α α α∈Rn: VAR parameters, given or estimated.   t: random term, shocks. E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work State of the art VAR Vector Autoregressive Models of order p(VAR(p)) Multivariate time series: correlation along time and between clients. VAR(p) wt=α α α+ p X k=1 Akwt−k+  t wt=w1 t, ..., wn t0: the demands of all clients at time t, known up to time T, A1, ..., Ap∈Rn×n,α α α∈Rn: VAR parameters, given or estimated.   t: random term, shocks. E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work 1Motivation and Background State of the art VAR 2Problem formulation 3Theoretical findings 4Concluding remarks and future work E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work Robust p-median problem min x,y∈Rmax w∈Uw0F(x) (Robust p-median) U: uncertainty set for the demand Fi(x) = Pm j=1 cij xij : cost function R: feasible region of problem (p-median) E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work Uncertainty sets Demand following a VAR U˜ w={˜ w:M˜ w−˜   =b,˜ w≥0} Bounding the errors U˜   ={˜   :k˜   k ≤ δ} k·kis a matrix norm min x,y∈Rmax ˜ w∈U˜ w ˜   ∈U˜    ˜ wF(x) E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work Advantages of the new formulation Gets rid of the minmax formulation: now only minimize Convex objective function: linear term plus a regularization term Uncertainty sets disappear E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work Sensitivity Analysis Corollary Let (x0,y0)be the solution of the deterministic p-median problem (p-median). Then, the maximum δsuch that the solution to the robust p-median problem (1) is still (x0,y0)is: δ0= min x,y∈R λ λ λ≥0 ˆ w0(F(x)−F(x0)) k(M−1)0(F(x0) + λ λ λ)k∗− k(M−1)0(F(x) + λ λ λ)k∗, where ˆ w=M−1bis the estimation of the demand via the VAR model. E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work 1Motivation and Background State of the art VAR 2Problem formulation 3Theoretical findings 4Concluding remarks and future work E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work Remark All results can be extended to Uncapacitated Facility Location Problem (UFLP) Preliminary results!!! This is a working paper, in development Future work Empirically test the performance of our approach Compare against Baron et al. (2011) E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands Motivation and Background Problem formulation Theoretical findings Concluding remarks and future work Thank you for your attention! [email protected] E. Carrizosa, A. Olivares-Nadal, P. Ram´ırez-Cobo Robust p-median problem with vector autoregressive demands