Multistage distributionally robust mixed-integer programming with decision-dependent moment-based ambiguity sets
- PDF / 893,339 Bytes
- 40 Pages / 439.37 x 666.142 pts Page_size
- 107 Downloads / 242 Views
Series B
Multistage distributionally robust mixed-integer programming with decision-dependent moment-based ambiguity sets Xian Yu1 · Siqian Shen1 Received: 24 February 2020 / Accepted: 9 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract We study multistage distributionally robust mixed-integer programs under endogenous uncertainty, where the probability distribution of stage-wise uncertainty depends on the decisions made in previous stages. We first consider two ambiguity sets defined by decision-dependent bounds on the first and second moments of uncertain parameters and by mean and covariance matrix that exactly match decision-dependent empirical ones, respectively. For both sets, we show that the subproblem in each stage can be recast as a mixed-integer linear program (MILP). Moreover, we extend the general moment-based ambiguity set in Delage and Ye (Oper Res 58(3):595–612, 2010) to the multistage decision-dependent setting, and derive mixed-integer semidefinite programming (MISDP) reformulations of stage-wise subproblems. We develop methods for attaining lower and upper bounds of the optimal objective value of the multistage MISDPs, and approximate them using a series of MILPs. We deploy the Stochastic Dual Dynamic integer Programming (SDDiP) method for solving the problem under the three ambiguity sets with risk-neutral or risk-averse objective functions, and conduct numerical studies on multistage facility-location instances having diverse sizes under different parameter and uncertainty settings. Our results show that the SDDiP quickly finds optimal solutions for moderate-sized instances under the first two ambiguity sets, and also finds good approximate bounds for the multistage MISDPs derived under the third ambiguity set. We also demonstrate the efficacy of incorporating decision-dependent distributional ambiguity in multistage decision-making processes. Keywords Multistage sequential decision-making · Distributionally robust optimization · Endogenous uncertainty · Mixed-integer semidefinite/linear programming · Stochastic dual dynamic integer programming (SDDiP)
The United States National Science Foundation Grants #1727618, #1709094, and Department of Engineering (DoE) Grant #DE-SC0018018. Extended author information available on the last page of the article
123
X. Yu, S. Shen
Mathematics Subject Classification 90C11 · 90C15 · 90C22
1 Introduction Data uncertainty appears ubiquitously in decision-making processes in practice, where system design and operational decisions are made sequentially and dynamically over a finite time horizon, to be adaptive to varying parameters (e.g., random customer demand, stochastic travel time). When using stochastic programming approaches, the goal is to optimize a certain measure of a random outcome (e.g., the expected cost of service operations) given a fully known distribution of uncertain parameter. We refer to, e.g., [6,36], for detailed discussions about applications, formulations, and so
Data Loading...
