Robust Stochastic Facility Location: Sensitivity Analysis and Exact Solution

作     者：Liu, Tianqi Saldanha-da-Gama, Francisco Wang, Shuming Mao, Yuchen 

作者机构：Univ Chinese Acad Sci Sch Econ & Management Beijing 100190 Peoples R China Univ Lisbon Dept Stat & Operat Res P-1649004 Lisbon Portugal Chinese Acad Sci Key Lab Big Data Min & Knowledge Management Beijing 100049 Peoples R China 

出 版 物：《INFORMS JOURNAL ON COMPUTING》 (INFORMS J. Comput.)

年 卷 期：2022年第34卷第5期

页      面：2776-2803页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：FCTFundacao para a Ciencia e Tecnologia, Portugal [UIDB/04561/2020] National Natural Science Foundation of China [71922020, 72171221, 71988101] Fundamental Research Funds for the Central Universities 

主　　题：stochastic facility location robust optimization state-wise distributional uncertainty Benders decomposition 

摘      要：This work focuses on a broad class of facility location problems in the context of adaptive robust stochastic optimization under the state-dependent demand uncertainty. The demand is assumed to be significantly affected by related state information, such as the seasonal or socio-economic information. In particular, a state-wise ambiguity set is adopted for modeling the distributional uncertainty associated with the demand in different states. The conditional distributional characteristics in each state are described by a support, as well as by mean and dispersion measures, which are assumed to be conic representable. A robust sensitivity analysis is performed, in which, on the one hand, we analyze the impact of the change in ambiguity-set parameters (e.g., state probabilities, mean value abounds, and dispersion bounds in different states) onto the optimal worst-case expected total cost using the ambiguity dual variables. On the other hand, we analyze the impact of the change in location design onto the worst-case expected second-stage cost and show that the sensitivity bounds are fully described as the worst-case expected shadow-capacity cost. As for the solution approach, we propose a nested Benders decomposition algorithm for solving the model exactly, which leverages the subgradients of the worst-case expected second-stage cost at the location decisions formed insightfully by the associated worst-case distributions. The nested Benders decomposition approach ensures a finite-step convergence, which can also be regarded as an extension of the classic L-shaped algorithm for two-stage stochastic programming to our state-wise, robust stochastic facility location problem with conic representable ambiguity. Finally, the results of a series of numerical experiments are presented that justify the value of the state-wise distributional information incorporated in our robust stochastic facility location model, the robustness of the model, and the performance of the exact so