Search

We study a pessimistic stochastic bilevel program in the context of sequential two-player games, where the leader makes a binary here-and-now decision, and the follower responds with a continuous wait-and-see decision after observing the leader's action and revelation of uncertainty. We assume that only the information regarding the mean, covariance, and support is known. We formulate the problem as a distributionally robust (DR) two-stage problem. The pessimistic DR bilevel program is shown to be equivalent to a generic two-stage distributionally robust stochastic (nonlinear) program with both a random objective and random constraints under proper conditions of ambiguity sets. Under continuous distributions, using linear decision rule approaches, we construct upper bounds on the pessimistic DR bilevel program based on (1) a 0-1 semidefinite programming (SDP) approximation and (2) an exact 0-1 copositive programming reformulation. When the ambiguity set is restricted to discrete distributions, an exact 0-1 SDP reformulation is developed, and explicit construction of the worst-case distribution is derived. To further improve the computation of the proposed 0-1 SDPs, a cutting-plane framework is developed. Moreover, based on a mixed-integer linear programming approximation, another cutting-plane algorithm is proposed. Extensive numerical studies are conducted to demonstrate the effectiveness of the proposed approaches on a facility location problem. History: Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0168) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0168). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We study adjustable distributionally robust optimization problems, where their ambiguity sets can potentially encompass an infinite number of expectation constraints. Although such ambiguity sets have great modeling flexibility in characterizing uncertain probability distributions, the corresponding adjustable problems remain computationally intractable and challenging. To overcome this issue, we propose a greedy improvement procedure that consists of solving, via the (extended) linear decision rule approximation, a sequence of tractable subproblems—each of which considers a relaxed and finitely constrained ambiguity set that can be iteratively tightened to the infinitely constrained one. Through three numerical studies of adjustable distributionally robust optimization models, we show that our approach can yield improved solutions in a systematic way for both two-stage and multistage problems. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: Financial support by the Early Career Scheme from the Hong Kong Research Grants Council [Project No. CityU 21502820], the CityU Start-Up Grant [Project No. 9610481], the CityU Strategic Research Grant [Project No. 7005688], the National Natural Science Foundation of China [Project No. 72032005], and Chow Sang Sang Group Research Fund sponsored by Chow Sang Sang Holdings International Limited [Project No. 9229076] is gratefully acknowledged. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0181), as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0181). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Distributionally robust optimization (DRO) is a modeling framework in decision making under uncertainty in which the probability distribution of a random parameter is unknown although its partial information (e.g., statistical properties) is available. In this framework, the unknown probability distribution is assumed to lie in an ambiguity set consisting of all distributions that are compatible with the available partial information. Although DRO bridges the gap between stochastic programming and robust optimization, one of its limitations is that its models for large-scale problems can be significantly difficult to solve, especially when the uncertainty is of high dimension. In this paper, we propose computationally efficient inner and outer approximations for DRO problems under a piecewise linear objective function and with a moment-based ambiguity set and a combined ambiguity set including Wasserstein distance and moment information. In these approximations, we split a random vector into smaller pieces, leading to smaller matrix constraints. In addition, we use principal component analysis to shrink uncertainty space dimensionality. We quantify the quality of the developed approximations by deriving theoretical bounds on their optimality gap. We display the practical applicability of the proposed approximations in a production–transportation problem and a multiproduct newsvendor problem. The results demonstrate that these approximations dramatically reduce the computational time while maintaining high solution quality. The approximations also help construct an interval that is tight for most cases and includes the (unknown) optimal value for a large-scale DRO problem, which usually cannot be solved to optimality (or even feasibility in most cases). Summary of Contribution: This paper studies an important type of optimization problem, that is, distributionally robust optimization problems, by developing computationally efficient inner and outer approximations via operations research tools. Specifically, we consider several variants of such problems that are practically important and that admit tractable yet large-scale reformulation. We accordingly utilize random vector partition and principal component analysis to derive efficient approximations with smaller sizes, which, more importantly, provide a theoretical performance guarantee with respect to low optimality gaps. We verify the significant efficiency (i.e., reducing computational time while maintaining high solution quality) of our proposed approximations in solving both production–transportation and multiproduct newsvendor problems via extensive computing experiments. [ABSTRACT FROM AUTHOR]

To use simulation models to study the behaviors of stochastic systems, one needs to specify the distribution of the input random variables. However, specifying this distribution precisely is typically difficult and even impossible in practice. The issue is known as input uncertainty in the simulation literature, and it has been considered and studied extensively in recent years. In this paper, we model the uncertainty by an ambiguity set that is defined based on the likelihood ratio between the true (unknown) distribution and the nominal distribution (i.e., the best estimate), and develop a robust simulation (RS) approach that estimates the worst-case values of performance measures of the random simulation output when the true distribution varies in the ambiguity set. We show that the RS approach is computationally tractable, and the corresponding results reveal important information of the stochastic systems and help decision makers make better decisions. [ABSTRACT FROM AUTHOR]