Search

This paper studies a distributionally robust multi-item newsvendor problem, where the demand distribution is unknown but specified with a general event-wise ambiguity set. Using the event-wise affine decision rules, we can obtain a conservative approximation formulation of the problem, which can typically be further reformulated as a linear program. In order to efficiently solve the resulting large-scale linear program, we develop a column generation-based decomposition scheme and speed up the computational efficiency by exploiting a special column selection strategy and stopping early based on a Karush-Kuhn-Tucker condition test. Focusing on the Wasserstein ambiguity set and the event-wise mean absolute deviation set, a computational study demonstrates both the computational efficiency of the proposed algorithm, which significantly outperforms a commercial solver and a Benders decomposition method, and the out-of-sample superiority of distributionally robust solutions relative to their sample average approximation counterparts. History: Accepted by Nicola Secomandi, Area Editor for Stochastic Models & Reinforcement Learning. Funding: This work was supported by the Natural Sciences and Engineering Research Council of Canada [492997-2016, RGPIN-2016-05208], the National Natural Science Foundation of China [71972012], Alliance de recherche numérique du Canada, and Canada Research Chairs [CRC-2018-00105]. It was also supported by Groupe d'études et de recherche en analyse des décisions (GERAD). Finally, this research was enabled in part by support provided by Digital Research Alliance of Canada (https://alliancecan.ca/en). 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.0010) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0010). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We study two-stage stochastic optimization problems with random recourse, where the coefficients of the adaptive decisions involve uncertain parameters. To deal with the infinite-dimensional recourse decisions, we propose a scalable approximation scheme via piecewise linear and piecewise quadratic decision rules. We develop a data-driven distributionally robust framework with two layers of robustness to address distributional uncertainty. We also establish out-of-sample performance guarantees for the proposed scheme. Applying known ideas, the resulting optimization problem can be reformulated as an exact copositive program that admits semidefinite programming approximations. We design an iterative decomposition algorithm, which converges under some regularity conditions, to reduce the runtime needed to solve this program. Through numerical examples for various known operations management applications, we demonstrate that our method produces significantly better solutions than the traditional sample-average approximation scheme especially when the data are limited. For the problem instances for which only the recourse cost coefficients are random, our method exhibits slightly inferior out-of-sample performance but shorter runtimes compared with a competing approach. History: Accepted by Nicola Secomandi, Area Editor for Stochastic Models & Reinforcement Learning. Funding: This work was supported by the National Science Foundation [Grants 2342505 and 2343869]. 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.0306) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0306). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

In this paper, we propose a decision criterion that characterizes an enveloping bound on monetary risk measures and is computationally friendly. We start by extending the classical value at risk (VaR) measure. Whereas VaR evaluates the threshold loss value such that the loss from the risk position exceeding that threshold is at a given probability level, it fails to indicate a performance guarantee at other probability levels. We define the probabilistic enveloping measure (PEM) to establish the bound information for the tail probability of the loss at all levels. Using a set of normative properties, we then generalize the PEM to the risk enveloping measure (REM) such that the bound on the general monetary risk measures at all levels of risk aversion are captured. The coherent version of the REM (CREM) is also investigated. We demonstrate its applicability by showing how the coherent REM can be incorporated in distributionally robust optimization. Specifically, we apply the CREM criterion in surgery block allocation problems and provide a formulation that can be efficiently solved. Based on this application, we report favorable computational results from optimizing over the CREM criterion. Summary of Contribution: Our paper studies a fundamental problem in operations research: what criteria to optimize when uncertainties are involved. Extending from the classical chance constraint model, we propose a new decision criterion by an axiomatization approach. We then investigate the computing issue in the corresponding distributionally robust optimization problem. In particular, we provide solution methods for continuous and discrete optimization. After that, we apply it to a practical operations problem, surgery allocation decisions in healthcare management. The computational studies demonstrate the appealing performance of our proposed approach on this surgery allocation problem. [ABSTRACT FROM AUTHOR]

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]

Aggregation of heating, ventilation, and air conditioning (HVAC) loads can provide reserves to absorb volatile renewable energy, especially solar photo-voltaic (PV) generation. In this paper, we decide HVAC control schedules under uncertain PV generation, using a distributionally robust chance-constrained (DRCC) building load control model under two typical ambiguity sets: the moment-based and Wasserstein ambiguity sets. We derive mixed integer linear programming (MILP) reformulations for DRCC problems under both sets. Especially, for the Wasserstein ambiguity set, we use the right-hand side (RHS) uncertainty to derive a more compact MILP reformulation than the commonly known MILP reformulations with big-M constants. All the results also apply to general individual chance constraints with RHS uncertainty. Furthermore, we propose an adjustable chance-constrained variant to achieve tradeoff between the operational risk and costs. We derive MILP reformulations under the Wasserstein ambiguity set and second-order conic programming (SOCP) reformulations under the moment-based set. Using real-world data, we conduct computational studies to demonstrate the efficiency of the solution approaches and the effectiveness of the solutions. Summary of Contribution: The problem studied in this paper is motivated by a building load control problem that uses the aggregation of heating, ventilation, and air conditioning (HVAC) loads as flexible reserves to absorb uncertain solar photovoltaic (PV) generation. The problem is formulated as distributionally robust chance-constrained (DRCC) programs with right-hand side (RHS) uncertainty. In addition, we propose a risk-adjustable variant of the DRCC programs, where the risk level, instead of being predetermined, is treated as a decision variable. The paper aims to provide tractable reformulations and solution algorithms for both the (general) DRCC and the (general) adjustable DRCC models with RHS uncertainty. [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]

Randomized decision making refers to the process of making decisions randomly according to the outcome of an independent randomization device, such as a dice roll or a coin flip. The concept is unconventional, and somehow counterintuitive, in the domain of mathematical programming, in which deterministic decisions are usually sought even when the problem parameters are uncertain. However, it has recently been shown that using a randomized, rather than a deterministic, strategy in nonconvex distributionally robust optimization (DRO) problems can lead to improvements in their objective values. It is still unknown, though, what is the magnitude of improvement that can be attained through randomization or how to numerically find the optimal randomized strategy. In this paper, we study the value of randomization in mixed-integer DRO problems and show that it is bounded by the improvement achievable through its continuous relaxation. Furthermore, we identify conditions under which the bound is tight. We then develop algorithmic procedures, based on column generation, for solving both single- and two-stage linear DRO problems with randomization that can be used with both moment-based and Wasserstein ambiguity sets. Finally, we apply the proposed algorithm to solve three classical discrete DRO problems: the assignment problem, the uncapacitated facility location problem, and the capacitated facility location problem and report numerical results that show the quality of our bounds, the computational efficiency of the proposed solution method, and the magnitude of performance improvement achieved by randomized decisions. Summary of Contribution: In this paper, we present both theoretical results and algorithmic tools to identify optimal randomized strategies for discrete distributionally robust optimization (DRO) problems and evaluate the performance improvements that can be achieved when using them rather than classical deterministic strategies. On the theory side, we provide improvement bounds based on continuous relaxation and identify the conditions under which these bound are tight. On the algorithmic side, we propose a finitely convergent, two-layer, column-generation algorithm that iterates between identifying feasible solutions and finding extreme realizations of the uncertain parameter. The proposed algorithm was implemented to solve distributionally robust stochastic versions of three classical optimization problems and extensive numerical results are reported. The paper extends a previous, purely theoretical work of the first author on the idea of randomized strategies in nonconvex DRO problems by providing useful bounds and algorithms to solve this kind of problems. [ABSTRACT FROM AUTHOR]