Search

Dial M for Simulation For years, systems of stochastic differential equations (SDEs) were simulated by discretization, inevitably introducing a bias, which can be difficult to quantify accurately. To circumvent this, some attempts have been made to simulate exactly various models from the SDE solution. These approaches prove capable of producing accurate results. A serious drawback of such an approach, nevertheless, is the implicit need to use extensive numerical methods, which make the entire simulation computationally heavy and quite impracticable. In the paper "Unified moment-based modeling of integrated stochastic processes," Kyriakou, Brignone, and Fusai present a methodological framework based on M(oments) for the simulation of such models that overcomes earlier limitations. Theoretical results and extensive numerical experiments show that the proposed approach allows accurate simulation of complex stochastic models with low computational effort. In this paper, we present a new method for simulating integrals of stochastic processes. We focus on the nontrivial case of time integrals, conditional on the state variable levels at the endpoints of a time interval through a moment-based probability distribution construction. We present different classes of models with important uses in finance, medicine, epidemiology, climatology, bioeconomics, and physics. The method is generally applicable in well-posed moment problem settings. We study its convergence, point out its advantages through a series of numerical experiments, and compare its performance against existing schemes. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.2422. [ABSTRACT FROM AUTHOR]

This paper builds a bridge between two area in optimization and machine learning by establishing a general connection between Wasserstein distributional robustness and variation regularization. It helps to demystify the empirical success of Wasserstein distributionally robust optimization and devise new regularization schemes for machine learning. Wasserstein distributionally robust optimization (DRO) is an approach to optimization under uncertainty in which the decision maker hedges against a set of probability distributions, specified by a Wasserstein ball, for the uncertain parameters. This approach facilitates robust machine learning, resulting in models that sustain good performance when the data are to some extent different from the training data. This robustness is related to the well-studied effect of regularization. The connection between Wasserstein DRO and regularization has been established in several settings. However, existing results often require restrictive assumptions, such as smoothness or convexity, that are not satisfied by many important problems. In this paper, we develop a general theory for the variation regularization effect of the Wasserstein DRO—a new form of regularization that generalizes total-variation regularization, Lipschitz regularization, and gradient regularization. Our results cover possibly nonconvex and nonsmooth losses and losses on non-Euclidean spaces and highlight the bias-variation tradeoff intrinsic in the Wasserstein DRO, which balances between the empirical mean of the loss and the variation of the loss. Example applications include multi-item newsvendor, linear prediction, neural networks, manifold learning, and intensity estimation for Poisson processes. We also use our theory of variation regularization to derive new generalization guarantees for adversarial robust learning. Funding: X. Chen is supported by the National Science Foundation [Grant IIS-1845444]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2383. [ABSTRACT FROM AUTHOR]

Heuristics and biases in probabilistic belief updating have typically been examined in simple two-state experimental settings. We argue that the two-state setting has probabilistic properties that do not extend to settings with more states. With three states, we find that individuals apply similar heuristics, such as representativeness and anchoring, when providing posterior probability distributions. However, because of the different normative benchmark, the use of these heuristics results in different biases for point estimates. In particular, we demonstrate that the well-known finding of stronger underinference for larger signal sets does not translate from the two-state to the three-state setting. Our findings caution against an indiscriminate transfer of updating biases observed in two-state settings to a broad set of real-world applications. This paper was accepted by Manel Baucells, behavioral economics and decision analysis. Funding: This work was supported by the Fritz Thyssen Stiftung [Grant 20.21.0.023WW]. Supplemental Material: The data and online appendix are available at https://doi.org/10.1287/mnsc.2022.00513. [ABSTRACT FROM AUTHOR]

When a firm selects an assortment of products to offer to customers, it uses a choice model to anticipate their probability of purchasing each product. In practice, the estimation of these models is subject to statistical errors, which may lead to significantly suboptimal assortment decisions. In "Randomized Assortment Optimization," Wang, Peura, and Wiesemann show that the standard approach of deterministically selecting a single assortment to offer is not always optimal in this setting: Instead, the firm can do better by selecting an assortment randomly according to a prudently designed probability distribution. The authors show how an optimal randomization strategy can be determined for common choice models, improving performance in realistic data-driven settings. The results suggest that more general versions of the assortment optimization problem—incorporating business constraints, more flexible choice models and/or more general forms of uncertainty—tend to be more receptive to the benefits of randomization. When a firm selects an assortment of products to offer to customers, it uses a choice model to anticipate their probability of purchasing each product. In practice, the estimation of these models is subject to statistical errors, which may lead to significantly suboptimal assortment decisions. Recent work has addressed this issue using robust optimization, where the true parameter values are assumed unknown and the firm chooses an assortment that maximizes its worst-case expected revenues over an uncertainty set of likely parameter values, thus mitigating estimation errors. In this paper, we introduce the concept of randomization into the robust assortment optimization literature. We show that the standard approach of deterministically selecting a single assortment to offer is not always optimal in the robust assortment optimization problem. Instead, the firm can improve its worst-case expected revenues by selecting an assortment randomly according to a prudently designed probability distribution. We demonstrate this potential benefit of randomization both theoretically in an abstract problem formulation as well as empirically across three popular choice models: the multinomial logit model, the Markov chain model, and the preference ranking model. We show how an optimal randomization strategy can be determined exactly and heuristically. Besides the superior in-sample performance of randomized assortments, we demonstrate improved out-of-sample performance in a data-driven setting that combines estimation with optimization. Our results suggest that more general versions of the assortment optimization problem—incorporating business constraints, more flexible choice models and/or more general uncertainty sets—tend to be more receptive to the benefits of randomization. Funding: Z. Wang acknowledges funding from the Imperial College President's PhD Scholarship programme. W. Wiesemann acknowledges funding from the Engineering and Physical Sciences Research Council [Grants EP/R045518/1, EP/T024712/1, and EP/W003317/1]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.0129. [ABSTRACT FROM AUTHOR]

Problem definition: We study customer service chat (CSC) systems, in which agents can serve multiple customers simultaneously, with generally distributed service and patience times. The multitasking capability of agents introduces idiosyncratic challenges when making routing and staffing decisions. Methodology/results: To determine the dynamic matching of arriving customers with available agents, we first formulate a routing linear program (LP) based on system primitives. Inspired by the optimal solution of the routing LP, we design a parsimonious dynamic routing policy that is independent of arrival rate and service capacity information. We also use the optimal solution to develop closed-form approximations for crucial performance metrics and show that a similar LP can be utilized to make staffing decisions. Through extensive simulation experiments, we showcase the efficacy of our approximations and staffing decisions. Furthermore, under our proposed policy, the CSC system exhibits a unique stationary fluid model in which the steady-state performance measures align with our approximations. Managerial implications: The extant literature primarily focuses on Markovian systems with exponential distributions. In this paper, customers' service and patience times are allowed to be generally distributed to agree with practical settings. Our findings indicate that the distributions have a significant impact on routing policies, staffing decisions, and system performance. Funding: Z. Long was supported by the National Natural Science Foundation of China [Grants 72101112, 72132005, and 72271119] and Jiangsu Province, China [Grant BK20210171]. J. Zhang was supported by the Hong Kong Research Grants Council, General Research Fund [Grants 16208120 and 16214121]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2022.0114. [ABSTRACT FROM AUTHOR]

In a world of increasingly extensive information, rational investors can make better decisions. However, reinforcement-oriented investors are also more likely to observe preferred signals close to their own perception. A focus on these signals distorts the perceived aggregate signal in the direction of the prior estimate. This reduces belief adaptation. Hence, the empirically well-documented selective exposure/reinforcement theory reduces the positive impact of greater information availability on price efficiency. Additional information can sometimes even decrease perception correctness. In a market with biased investors, managers have an incentive to announce more diffuse (fewer precise) signals in case of negative (positive) information. This results in postearnings-announcement drift and dispersion anomaly. Also, the distribution shape matters for information processing. For unimodal, symmetric distributions, agents' perceptions converge to the fundamental—even though at a reduced speed. For multimodal signal distributions, the estimate can diverge from the fundamental. This paper was accepted by Yan Chen, behavioral economics and decision analysis. Supplemental Material: The data files are available at https://doi.org/10.1287/mnsc.2023.4941. [ABSTRACT FROM AUTHOR]

Optimal stopping is a fundamental class of stochastic dynamic optimization problems with numerous applications in finance and operations management. In "A nonparametric algorithm for optimal stopping based on robust optimization," the author introduces an approach based on robust optimization for computing near-optimal solutions for computationally demanding stochastic optimal stopping problems with known probability distributions. Through this new use of robust optimization, the paper develops new algorithms for solving stochastic optimal stopping problems that are practical and can outperform state-of-the-art simulation-based algorithms in the context of pricing high-dimensional financial options. Optimal stopping is a fundamental class of stochastic dynamic optimization problems with numerous applications in finance and operations management. We introduce a new approach for solving computationally-demanding stochastic optimal stopping problems with known probability distributions. The approach uses simulation to construct a robust optimization problem that approximates the stochastic optimal stopping problem to any arbitrary accuracy; we then solve the robust optimization problem to obtain near-optimal Markovian stopping rules for the stochastic optimal stopping problem. In this paper, we focus on designing algorithms for solving the robust optimization problems that approximate the stochastic optimal stopping problems. These robust optimization problems are challenging to solve because they require optimizing over the infinite-dimensional space of all Markovian stopping rules. We overcome this challenge by characterizing the structure of optimal Markovian stopping rules for the robust optimization problems. In particular, we show that optimal Markovian stopping rules for the robust optimization problems have a structure that is surprisingly simple and finite-dimensional. We leverage this structure to develop an exact reformulation of the robust optimization problem as a zero-one bilinear program over totally unimodular constraints. We show that the bilinear program can be solved in polynomial time in special cases, establish computational complexity results for general cases, and develop polynomial-time heuristics by relating the bilinear program to the maximal closure problem from graph theory. Numerical experiments demonstrate that our algorithms for solving the robust optimization problems are practical and can outperform state-of-the-art simulation-based algorithms in the context of widely-studied stochastic optimal stopping problems from high-dimensional option pricing. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2023.2461. [ABSTRACT FROM AUTHOR]

Consider the problem of allocating indivisible goods among agents with additive valuations, where monetary payments are not allowed. When randomization is allowed, it is possible to achieve compelling notions of fairness such as EV, which states that no agent should prefer any other agent's allocation to their own. When allocations must be deterministic, achieving exact fairness is impossible but approximate notions such as EV up to one good can be guaranteed. In "Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation," H. Aziz, R. Freeman, N. Shah, and R. Vaish ask whether it is possible to achieve both types of guarantees simultaneously. More specifically, they ask whether there exists a probability distribution over deterministic allocations such that every deterministic allocation is envy-free up to one good and the distribution is exactly envy-free in expectation. The main result of the paper answers this question in the affirmative, showing that ex ante and ex post fairness need not be in conflict. We study the problem of allocating indivisible goods among agents with additive valuations. When randomization is allowed, it is possible to achieve compelling notions of fairness such as envy-freeness, which states that no agent should prefer any other agent's allocation to their own. When allocations must be deterministic, achieving exact fairness is impossible but approximate notions such as envy-freeness up to one good can be guaranteed. Our goal in this work is to achieve both simultaneously, by constructing a randomized allocation that is exactly fair ex ante (before the randomness is realized) and approximately fair ex post (after the randomness is realized). The key question we address is whether ex ante envy-freeness can be achieved in combination with ex post envy-freeness up to one good. We settle this positively by designing an efficient algorithm that achieves both properties simultaneously. The algorithm can be viewed as a desirable way to instantiate a lottery for the probabilistic serial rule. If we additionally require economic efficiency, we obtain three impossibility results that show that ex post or ex ante Pareto optimality is impossible to achieve in conjunction with combinations of fairness properties. Hence, we slightly relax our ex post fairness guarantees and present a different algorithm that can be viewed as a fair way to instantiate a lottery for the maximum Nash welfare allocation rule. Funding: This work was supported by the Office of Naval Research [Grant N00014-17-1-2621] and DST INSPIRE [Grant DST/INSPIRE/04/2020/000107]. [ABSTRACT FROM AUTHOR]

This paper studies the investor's investment decision in a standard financial contracting model. The investor chooses among entrepreneurs with heterogeneous production technologies who generate different probability distributions of cash flow under effort. I provide a complete characterization of optimal contracts, agency rents, and the investor's investment decision. Differences in entrepreneurs' production technologies imply differences in optimal contracts and agency rents across equally productive entrepreneurs, which biases and potentially distorts the investor's investment decision. The results provide a complete characterization of entrepreneurs' financial constraints in the presence of heterogeneous production technologies and uncover a fundamental link between production technologies, financial contracts, and financial constraints. This paper was accepted by Gustavo Manso, finance. Funding: This work was supported by the Swedish House of Finance. [ABSTRACT FROM AUTHOR]

Assortment optimization has received significant attention in recent revenue management and combinatorial optimization literature. In "The Approximability of Assortment Optimization Under Ranking Preferences," A. Aouad, V. Farias, R. Levi, and D. Segev provide best-possible approximability bounds for this problem under an almost general model specification, where preferences are expressed as a distribution over rankings. This paper shows how this optimization problem relates to the computational task of detecting large independent sets in graphs, allowing the establishment of strong complexity lower bounds with respect to various problem parameters. These findings are complemented by a number of algorithms that attain essentially best-possible approximation factors, proving that the hardness results are tight up to lower-order terms. Surprisingly, their results imply that a simple and widely studied policy, known as revenue-ordered assortments, achieves the best possible performance guarantee with respect to prices. The main contribution of this paper is to provide best-possible approximability bounds for assortment planning under a general choice model, where customer choices are modeled through an arbitrary distribution over ranked lists of their preferred products, subsuming most random utility choice models of interest. From a technical perspective, we show how to relate this optimization problem to the computational task of detecting large independent sets in graphs, allowing us to argue that general ranking preferences are extremely hard to approximate with respect to various problem parameters. These findings are complemented by a number of approximation algorithms that attain essentially best-possible factors, proving that our hardness results are tight up to lower-order terms. Surprisingly, our results imply that a simple and widely studied policy, known as revenue-ordered assortments, achieves the best possible performance guarantee with respect to the price parameters. [ABSTRACT FROM AUTHOR]

Traditional clustering algorithms such as k-means and vanilla spectral clustering are known to deteriorate significantly in the presence of outliers. Several previous works in literature have proposed robust variants of these algorithms; however, they do not provide any theoretical guarantees. Extending previous clustering literature on Gaussian mixture models, in their paper "A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers," Prateek R. Srivastava, Purnamrita Sarkar, and Grani A. Hanasusanto developed a new spectral clustering algorithm and provided error bounds for the algorithm under a general sub-Gaussian mixture model setting with outliers. Surprisingly, their derived error bound matches with the best-known bound for semidefinite programs under the same setting without outliers. Numerical experiments on a variety of simulated and real-world data sets further demonstrate that their algorithm is less sensitive to outliers compared with other state-of-the-art algorithms. We consider the problem of clustering data sets in the presence of arbitrary outliers. Traditional clustering algorithms such as k-means and spectral clustering are known to perform poorly for data sets contaminated with even a small number of outliers. In this paper, we develop a provably robust spectral clustering algorithm that applies a simple rounding scheme to denoise a Gaussian kernel matrix built from the data points and uses vanilla spectral clustering to recover the cluster labels of data points. We analyze the performance of our algorithm under the assumption that the "good" data points are generated from a mixture of sub-Gaussians (we term these "inliers"), whereas the outlier points can come from any arbitrary probability distribution. For this general class of models, we show that the misclassification error decays at an exponential rate in the signal-to-noise ratio, provided the number of outliers is a small fraction of the inlier points. Surprisingly, this derived error bound matches with the best-known bound for semidefinite programs (SDPs) under the same setting without outliers. We conduct extensive experiments on a variety of simulated and real-world data sets to demonstrate that our algorithm is less sensitive to outliers compared with other state-of-the-art algorithms proposed in the literature. Funding: G. A. Hanasusanto was supported by the National Science Foundation Grants NSF ECCS-1752125 and NSF CCF-2153606. P. Sarkar gratefully acknowledges support from the National Science Foundation Grants NSF DMS-1713082, NSF HDR-1934932 and NSF 2019844. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2317. [ABSTRACT FROM AUTHOR]

Customer behavior is often assumed to follow weak rationality, which implies that adding a product to an assortment will not increase the choice probability of another product in that assortment. However, an increasing amount of research has revealed that customers are not necessarily rational when making decisions. In this paper, we propose a new nonparametric choice model that relaxes this assumption and can model a wider range of customer behavior, such as decoy effects between products. In this model, each customer type is associated with a binary decision tree, which represents a decision process for making a purchase based on checking for the existence of specific products in the assortment. Together with a probability distribution over customer types, we show that the resulting model—a decision forest—is able to represent any customer choice model, including models that are inconsistent with weak rationality. We theoretically characterize the depth of the forest needed to fit a data set of historical assortments and prove that with high probability, a forest whose depth scales logarithmically in the number of assortments is sufficient to fit most data sets. We also propose two practical algorithms—one based on column generation and one based on random sampling—for estimating such models from data. Using synthetic data and real transaction data exhibiting nonrational behavior, we show that the model outperforms both rational and nonrational benchmark models in out-of-sample predictive ability. This paper was accepted by Chung Piaw Teo, optimization. [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]

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]

One of the basic facts known for discrete-time Markov decision processes is that, if the probability distribution of an initial state is fixed, then for every policy it is easy to construct a (randomized) Markov policy with the same marginal distributions of state-action pairs as for the original policy. This equality of marginal distributions implies that the values of major objective criteria, including expected discounted total costs and average rewards per unit time, are equal for these two policies. This paper investigates the validity of the similar fact for continuous-time jump Markov decision processes (CTJMDPs). It is shown in this paper that the equality of marginal distributions takes place for a CTJMDP if the corresponding Markov policy defines a nonexplosive jump Markov process. If this Markov process is explosive, then at each time instance, the marginal probability, that a state-action pair belongs to a measurable set of state-action pairs, is not greater for the described Markov policy than the same probability for the original policy. These results are applied in this paper to CTJMDPs with expected discounted total costs and average costs per unit time. It is shown for these criteria that, if the initial state distribution is fixed, then for every policy, there exists a Markov policy with the same or better value of the objective function. [ABSTRACT FROM AUTHOR]

Suppose a target is hidden in one of the vertices of an edge-weighted graph according to a known probability distribution. Starting from a fixed root node, an expanding search visits the vertices sequentially until it finds the target, where the next vertex can be reached from any of the previously visited vertices. That is, the time to reach the next vertex equals the shortest-path distance from the set of all previously visited vertices. The expanding search problem then asks for a sequence of the nodes, so as to minimize the expected time to finding the target. This problem has numerous applications, such as searching for hidden explosives, mining coal, and disaster relief. In this paper, we develop exact algorithms and heuristics, including a branch-and-cut procedure, a greedy algorithm with a constant-factor approximation guarantee, and a local search procedure based on a spanning-tree neighborhood. Computational experiments show that our branch-and-cut procedure outperforms existing methods for instances with nonuniform probability distributions and that both our heuristics compute near-optimal solutions with little computational effort. Summary of Contribution: This paper studies new algorithms for the expanding search problem, which asks to search a graph for a target hidden in one of the nodes according to a known probability distribution. This problem has applications such as searching for hidden explosives, mining coal, and disaster relief. We propose several new algorithms, including a branch-and-cut procedure, a greedy algorithm, and a local search procedure; and we analyze their performance both experimentally and theoretically. Our analysis shows that the algorithms improve on the performance of existing methods and establishes the first constant-factor approximation guarantee for this problem. [ABSTRACT FROM AUTHOR]

This paper considers a class of two-stage stochastic mixed-integer optimization problems where, for a given first-stage solution, we can determine the optimal values of recourse variables sequentially. This class of problems arises in a wide variety of applications. In the case of multivariate discrete distributions for uncertain parameters, a standard stochastic programming formulation of these problems involves an exponential number of scenarios, therefore an exponential number of variables and constraints. We propose a new mixed-integer programming modeling approach where the number of variables and constraints is independent of the number of scenarios and scales at most pseudopolynomially with the problem size. The proposed modeling approach relies on state variables that track the system's state as the uncertainty realizes sequentially. We demonstrate the advantages of the proposed approach in two applications arising in project scheduling and operating room allocation. Summary of Contribution: This paper proposes a new modeling approach for a class of two-stage stochastic optimization problems that is computationally more efficient than the traditional scenario-based stochastic integer programming models. The proposed modeling approach relies on state variables that track the system's state as the uncertainty realizes sequentially. We demonstrated the efficiency of the proposed approach by computational results on two applications in project scheduling and operating room allocation. [ABSTRACT FROM AUTHOR]

We extend the notion of globalized robustness to consider distributional information beyond the support of the ambiguous probability distribution. We propose the globalized distributionally robust counterpart that disallows any (respectively, allows limited) constraint violation for distributions residing (respectively, not residing) in the ambiguity set. By varying its inputs, our proposal recovers several existing perceptions of parameter uncertainty. Focusing on the type 1 Wasserstein distance, we show that the globalized distributionally robust counterpart has an insightful interpretation in terms of shadow price of globalized robustness, and it can be seamlessly integrated with many popular optimization models under uncertainty without incurring any extra computational cost. Such computational attractiveness also holds for other ambiguity sets, including the ones based on probability metric, optimal transport, ϕ-divergences, or moment conditions, as well as the event-wise ambiguity set. Numerical studies on an adaptive network lot-sizing problem demonstrate the modeling flexibility of our proposal and its emphases on globalized robustness to constraint violation. History: Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: Z. Chen was supported by [General Research Fund Grant 9043424, NSFC/RGC Joint Research Scheme N_CityU105/21] from the Hong Kong Research Grants Council. S. Wang was supported by the National Natural Science Foundation of China [Grants 71922020, 72171221, and 71988101, entitled "Econometric Modeling and Economic Policy Studies"] and the Fundamental Research Funds for the Central Universities [Grant UCAS-E2ET0808X2]. 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.0274) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0274). 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]

Agribusiness firms, with an eye toward increasing population and evolving weather patterns, are investing heavily into developing new varieties of staple crops that can provide higher yields and are robust to weather fluctuations. In this paper, we describe a multiyear effort at Dow Agrosciences (now Corteva) to manage its seed corn portfolio, which includes several hundred seeds and is valued at more than $1 billion. The effort had two mutually interacting parts: (1) developing a decision-analytic theory to estimate the production yield distributions for new seed varieties from discrete quantile judgments provided by plant biology experts and (2) developing an optimization protocol to determine Dow's annual production plan for the seed portfolio with the flexibility of backup production in South America, under production yield uncertainty. The first part, owned by the research and development (R&D) function, provides yield probability distributions as inputs to the optimization protocol of the second part, which the production function owns. The results of the optimization problem, which include information about the attractiveness of specific future varieties, are returned to R&D. Both parts incorporate contextual details specific to this industry. In this paper, we show the optimality of linear policies for both problems. Additionally, the linear policies have many attractive structural properties that continue to hold for the more complex instances of the problems. A major strength of the theory we developed is that it is implementable in a transparent fashion, providing managers with a user-friendly, real-time decision support tool. The implementation of the theory developed has led to significant monetary and managerial benefits at Dow. [ABSTRACT FROM AUTHOR]

Microtask crowdsourcing platforms provide an online marketplace where task requesters can submit microtasks for a crowd of workers to complete. As the information collected from a crowd can be prone to errors, additional algorithmic techniques are needed to infer the ground truth labels. In this paper, we present a variety of new approaches for modeling label dependency and worker quality in the context of multi-label crowdsourcing. To capture label dependency, we introduce three methods based on a Bayesian mixture of Bernoulli distributions, its Dirichlet process extension, and a multivariate logit-normal distribution. We also propose two distinct generative models for characterizing shared and hierarchical structures of worker quality. Efficient variational inference algorithms are then developed to jointly infer ground truth labels and worker quality. Extensive experiments show that the models based on integrating Bernoulli mixtures and shared structure of worker quality achieve the best performance. Our study clearly highlights that joint and effective modeling of label dependency and worker quality is crucial to a multi-label crowdsourcing system. The proposed framework also has great potential to be extended to a broader range of applications, where different opinions need to be combined to measure multiple perspectives of an object. Microtask crowdsourcing has emerged as a cost-effective approach for obtaining large-scale labeled data. Crowdsourcing platforms, such as MTurk, provide an online marketplace where task requesters can submit a batch of microtasks for a crowd of workers to complete for a small monetary compensation. As the information collected from a crowd can be prone to errors, additional algorithmic techniques are needed to infer the ground truth labels from noisy annotations by workers with heterogeneous quality. Moreover, it would be very beneficial to identify and possibly filter out low-quality workers to foster the creation of a healthy and sustainable crowdsourcing ecosystem. Much of the existing literature on crowd labeling has focused on the single-label setting. However, in many application domains, it is common that each item to be annotated can be assigned to multiple categories simultaneously. In this paper, we present a variety of new approaches for modeling label dependency and worker quality in the context of multi-label crowdsourcing. To capture label dependency, we introduce three methods based on a Bayesian mixture of Bernoulli distributions, its Dirichlet process extension, and a multivariate logit-normal distribution. We also propose two distinct generative models for characterizing shared and hierarchical structures of worker quality. Efficient collapsed and Laplace variational inference algorithms are then developed to jointly infer ground truth labels and worker quality. Extensive simulation and MTurk experiments show that the models based on integrating Bernoulli mixtures and shared structure of worker quality achieve a significant improvement over other state-of-the-art methods. Our study clearly highlights that joint and effective modeling of label dependency and worker quality is crucial to the design of a multi-label crowdsourcing system. The proposed framework also has great potential to be extended to a broader range of applications, in which different opinions need to be combined to measure multiple perspectives of an object. [ABSTRACT FROM AUTHOR]

This research proposes and analyzes new models for a stochastic resource allocation problem that arises in a variety of operations contexts. One of the primary contributions of the paper lies in providing a succinct, robust, and general model that can address a range of different risk-based objectives and cost assumptions under uncertainty. Although the model expression is relatively simple, it embeds a reasonably high degree of underlying complexity, as the analysis shows. In addition, in-depth analysis of the model, both in its general form and under various specific risk measures, uncovers some interesting and powerful insights regarding the problem trade-offs. Furthermore, this analysis leads to a highly efficient class of heuristic algorithms for solving the problem, which we demonstrate via numerical experimentation to provide close-to-optimal solutions. This computational benefit is a critical element for solving a class of broadly applicable larger problems for which our problem arises as a subproblem that requires repeated solution. This paper considers a single-resource allocation problem for multiple items with random, independent resource consumption values, known as the static stochastic knapsack problem (SSKP). Whereas the existing SSKP literature generally assumes a risk-neutral objective using an expected value approach, such an approach can maximize expected profit while admitting the possibility of very high losses in some unfavorable scenarios. Because of this, we consider two popular risk measures, conditional value-at-risk (CVaR) and a mean-standard deviation trade-off, in order to address risk within this problem class. Optimizing the trade-offs associated with these risk measures presents significant modeling and computational challenges. To address these challenges, we first provide mixed-integer linear programming models using a scenario-based approach, which can be exploited to provide exact solutions for discrete distributions. For general distributions, a sample average approximation method provides approximate solutions. We then propose a general mixed integer nonlinear optimization modeling approach for the special case of normally distributed resource requirements. This modeling approach incorporates a new class of normalized penalty functions that account for both the expected costs and risks associated with uncertainty, and it can be specialized to a broad class of risk measures, including CVaR and mean-standard deviation. Our results characterize key optimality properties for the associated continuous relaxation of the proposed general model and provide insights on valuable rank-ordering mechanisms for items with uncertain resource needs under different risk measures. For this broadly applicable case, we present a class of efficient and high-performing asymptotically optimal heuristic methods based on these optimality conditions. An extensive numerical study evaluates the efficiency and quality of the proposed solution methods, identifies optimal item selection strategies, and examines the sensitivity of the solution to varying levels of risk, excess weight penalty values, and knapsack capacity values. Summary of Contribution: This research proposes and analyzes new models for a stochastic resource allocation problem that arises in a variety of operations contexts. One of the primary contributions of the paper lies in providing a succinct, robust, and general model that can address a range of different risk-based objectives and cost assumptions under uncertainty. While the model expression is relatively simple, it embeds a reasonably high degree of underlying complexity, as the analysis shows. In addition, in-depth analysis of the model, both in its general form and under various specific risk measures, uncovers some interesting and powerful insights regarding the problem tradeoffs. Furthermore, this analysis leads to a highly efficient class of heuristic algorithms for solving the problem, which we demonstrate via numerical experimentation to provide close-to-optimal solutions. This computational benefit is a critical element for solving a class of broadly applicable larger problems for which our problem arises as a subproblem that requires repeated solution. [ABSTRACT FROM AUTHOR]

Distributionally robust optimization is increasingly becoming a popular methodology to deal with uncertainty in optimization problems. Although the methodology optimizes for the worst-case distribution, a better understanding of the prescriptions from the models important from a practical perspective. In the paper "On the heavy-tail behavior of the distributionally robust newsvendor," B. Das, A. Dhara, and K. Natarajan provide a novel analysis for the problem in the newsvendor setting with moment information. They show that the distributionally robust newsvendor by planning for the worst possible demand distribution with moment information will remains optimal if the true demand distribution is heavy-tailed. The prescribed optimal solution has a heavy-tail optimality' property for free. Since the seminal work of Scarf (A min-max solution of an inventory problem) in 1958 on the newsvendor problem with ambiguity in the demand distribution, there has been a growing interest in the study of the distributionally robust newsvendor problem. The model is criticized at times for being conservative because the worst-case distribution is discrete with a few support points. However, it is the order quantity prescribed by the model that is of practical relevance. Interestingly, the order quantity from Scarf's model is optimal for a heavy-tailed distribution. In this paper, we generalize this observation by showing a heavy-tail optimality property of the distributionally robust order quantity for an ambiguity set where information on the first and the αth moment is known, for any real α > 1. We show that the optimal order quantity for the distributionally robust newsvendor is also optimal for a regularly varying distribution with parameter α. In the high service level regime, when the original demand distribution is given by an exponential or a lognormal distribution and contaminated with a regularly varying distribution, the distributionally robust order quantity is shown to outperform the optimal order quantity of the original distribution, even with a small amount of contamination. [ABSTRACT FROM AUTHOR]

The dynamic programming principle (DPP) is fundamental for control and optimization, including Markov decision problems (MDPs), reinforcement learning (RL), and, more recently, mean-field controls (MFCs). However, in the learning framework of MFCs, the DPP has not been rigorously established, despite its critical importance for algorithm designs. In this paper, we first present a simple example in MFCs with learning where the DPP fails with a misspecified Q function and then propose the correct form of Q function in an appropriate space for MFCs with learning. This particular form of Q function is different from the classical one and is called the IQ function. In the special case when the transition probability and the reward are independent of the mean-field information, it integrates the classical Q function for single-agent RL over the state-action distribution. In other words, MFCs with learning can be viewed as lifting the classical RLs by replacing the state-action space with its probability distribution space. This identification of the IQ function enables us to establish precisely the DPP in the learning framework of MFCs. Finally, we illustrate through numerical experiments the time consistency of this IQ function. [ABSTRACT FROM AUTHOR]

Distributionally robust stochastic optimization (DRSO) is an approach to optimization under uncertainty in which, instead of assuming that there is a known true underlying probability distribution, one hedges against a chosen set of distributions. In this paper, we first point out that the set of distributions should be chosen to be appropriate for the application at hand and some of the choices that have been popular until recently are, for many applications, not good choices. We next consider sets of distributions that are within a chosen Wasserstein distance from a nominal distribution. Such a choice of sets has two advantages: (1) The resulting distributions hedged against are more reasonable than those resulting from other popular choices of sets. (2) The problem of determining the worst-case expectation over the resulting set of distributions has desirable tractability properties. We derive a strong duality reformulation of the corresponding DRSO problem and construct approximate worst-case distributions (or an exact worst-case distribution if it exists) explicitly via the first-order optimality conditions of the dual problem. Our contributions are fourfold. (i) We identify necessary and sufficient conditions for the existence of a worst-case distribution, which are naturally related to the growth rate of the objective function. (ii) We show that the worst-case distributions resulting from an appropriate Wasserstein distance have a concise structure and a clear interpretation. (iii) Using this structure, we show that data-driven DRSO problems can be approximated to any accuracy by robust optimization problems, and thereby many DRSO problems become tractable by using tools from robust optimization. (iv) Our strong duality result holds in a very general setting. As examples, we show that it can be applied to infinite dimensional process control and intensity estimation for point processes. [ABSTRACT FROM AUTHOR]

The discrete moment problem aims to find a worst-case discrete distribution that satisfies a given set of moments. This paper studies the discrete moment problems with additional shape constraints that guarantee the worst-case distribution is either log-concave (LC) or has an increasing failure rate (IFR) or increasing generalized failure rate (IGFR). These classes are useful in practice, with applications in revenue management, reliability, and inventory control. The authors characterize the structure of optimal extreme point distributions and show, for example, that an optimal extreme point solution to a moment problem with m moments and LC shape constraints is piecewise geometric with at most m pieces. Using this optimality structure, they design an exact algorithm for computing optimal solutions in a low-dimensional space of parameters. The authors leverage this structure to study a robust newsvendor problem with shape constraints and compute optimal solutions. The discrete moment problem is a foundational problem in distribution-free robust optimization, where the goal is to find a worst-case distribution that satisfies a given set of moments. This paper studies the discrete moment problems with additional shape constraints that guarantee the worst-case distribution is either log-concave (LC), has an increasing failure rate (IFR), or increasing generalized failure rate (IGFR). These classes of shape constraints have not previously been studied in the literature, in part due to their inherent nonconvexities. Nonetheless, these classes are useful in practice, with applications in revenue management, reliability, and inventory control. We characterize the structure of optimal extreme point distributions under these constraints. We show, for example, that an optimal extreme point solution to a moment problem with m moments and LC shape constraints is piecewise geometric with at most m pieces. This optimality structure allows us to design an exact algorithm for computing optimal solutions in a low-dimensional space of parameters. We also leverage this structure to study a robust newsvendor problem with shape constraints and compute optimal solutions. [ABSTRACT FROM AUTHOR]

Nonlinear usage-based pricing is applied extensively in software markets. Customers of software products usually cannot vary their required usage volume, a property we label local demand inelasticity. For instance, a client firm that needs a sales force automation software either buys one user license for every salesperson or does not buy at all. It is unlikely to buy licenses for some but not all salespersons. This demand feature violates a critical assumption of the standard nonlinear pricing literature that consumers are flexible with their usage volume, and their valuation changes smoothly with usage volume. Consequently, standard nonlinear pricing solutions are inapplicable to many software products. This paper studies the optimal nonlinear usage-based pricing of software when customers' demand is locally inelastic. This unique demand feature necessitates a new approach to solve the nonlinear pricing problem. We show that under a weak ordering condition of customer types, this complex pricing problem can be decomposed into a set of much simpler subproblems with known solutions. Our pricing solution is easily implementable and applicable to a broad range of demand systems, including those described by the families of exponential and normal distributions. Moreover, local demand inelasticity has a critical impact on key efficiency results. Nonlinear usage-based pricing is applied extensively in software markets. Different from other products, customers of software products usually cannot vary their required usage volume, a property we label local demand inelasticity. For instance, a client firm that needs a sales force automation software either buys one user license for every salesperson in its organization or does not buy at all. It is unlikely to buy licenses for some salespersons but not the others. This demand feature violates a critical assumption of the standard nonlinear pricing literature that consumers are flexible with their usage volume, and their valuation changes smoothly with usage volume. Consequently, standard nonlinear pricing solutions are inapplicable to many software products. This paper studies the optimal nonlinear usage-based pricing of software when customers' demand is locally inelastic. This unique demand feature necessitates a new approach to solve the nonlinear pricing problem. We provide the solution to a complicated nonlinear pricing problem with discontinuous and inelastic individual demand functions, with virtually no restriction on demand distribution, and no single-crossing restriction on valuation functions. We show that under a weak ordering condition of customer types, this complex pricing problem can be decomposed into a set of much simpler subproblems with known solutions. Our pricing solution is easily implementable and applicable to a broad range of demand systems, including those described by the families of exponential and normal distributions. Moreover, local demand inelasticity has a critical impact on key efficiency results. Although in standard nonlinear pricing models, the optimal pricing schedule typically involves distortion (deviation from the first best) at all but one point, this is no longer the case with local demand inelasticity. We characterize the conditions under which the optimal nonlinear pricing strategy involves quantity discounts and compare nonlinear usage-based pricing with flat-fee (for unlimited usage) pricing strategies. [ABSTRACT FROM AUTHOR]

The question of aggregating pairwise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g., MSR's TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In most settings, in addition to obtaining a ranking, finding 'scores' for each object (e.g., player's rating) is of interest for understanding the intensity of the preferences. In this paper, we propose Rank Centrality, an iterative rank aggregation algorithm for discovering scores for objects (or items) from pairwise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with an edge present between a pair of objects if they are compared; the score, which we call Rank Centrality, of an object turns out to be its stationary probability under this random walk. To study the efficacy of the algorithm, we consider the popular Bradley-Terry-Luce (BTL) model (equivalent to the Multinomial Logit (MNL) for pairwise comparisons) in which each object has an associated score that determines the probabilistic outcomes of pairwise comparisons between objects. In terms of the pairwise marginal probabilities, which is the main subject of this paper, the MNL model and the BTL model are identical. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. In particular, the number of samples required to learn the score well with high probability depends on the structure of the comparison graph. When the Laplacian of the comparison graph has a strictly positive spectral gap, e.g., each item is compared to a subset of randomly chosen items, this leads to dependence on the number of samples that is nearly order optimal. Experimental evaluations on synthetic data sets generated according to the BTL model show that our algorithm performs as well as the maximum likelihood estimator for that model and outperforms other popular ranking algorithms. [ABSTRACT FROM AUTHOR]

In this work we consider a seller who sells an item via second-price auctions with a reserve price. By controlling the reserve price, the seller can influence the revenue from the auction, and in this paper, we propose a method for learning optimal reserve prices. We study a limited information setting where the probability distribution of the bids from bidders is unknown and the values of the bids are not revealed to the seller. Furthermore, we do not assume that the seller has access to a historical data set with bids. Our main contribution is a method that incorporates knowledge about the rules of second-price auctions into a multiarmed bandit framework for optimizing reserve prices in our limited information setting. The proposed method can be applied in both stationary and nonstationary environments. Experiments show that the proposed method outperforms state-of-the-art bandit algorithms. In stationary environments, our method outperforms these algorithms when the horizon is short and performs as good as they do for longer horizons. Our method is especially useful if there is a high number of potential reserve prices. In addition, our method adapts quickly to changing environments and outperforms state-of-the-art bandit algorithms designed for nonstationary environments. Summary of Contribution: A key challenge in online advertising is the pricing of advertisements in online auctions. The scope of our study is second-price auctions with a focus on the reserve price optimization problem from a seller's point of view. This problem is motivated by the real-life practice of small and medium-sized web publishers. However, the proposed solution approach is applicable to any seller who sells an item via second-price auctions and wants to optimize its reserve price during these auctions. Our solution approach is based on techniques from machine learning and operations research, and it would be beneficial especially for sellers who start the selling process without any historical data and can collect the data on the outcomes of the auctions while making reserve price decisions over time. History: Accepted by RamRamesh, Area Editor for Data Science & Machine Learning. Supplemental Material: The supplementary material is available at https://doi.org/10.1287/ijoc.2022.1199. [ABSTRACT FROM AUTHOR]

In this paper we consider the notion of rectangularity of a set of probability measures from a somewhat different point of view. We define rectangularity as a property of dynamic decomposition of a distributionally robust stochastic optimization problem and show how it relates to the modern theory of coherent risk measures. Consequently, we discuss robust formulations of multistage stochastic optimization problems in frameworks of stochastic programming, stochastic optimal control, and Markov decision processes. [ABSTRACT FROM AUTHOR]

The Bayesian persuasion paradigm of strategic communication models interaction between a privately informed sender and an ignorant but rational receiver. The goal is typically to design a (near-)optimal communication (or signaling) scheme for the sender. It enables the sender to disclose information to the receiver in a way as to incentivize her to take an action that is preferred by the sender. Finding the optimal signaling scheme is known to be computationally difficult in general. This hardness is further exacerbated when the message space is constrained, leading to NP-hardness of approximating the optimal sender utility within any constant factor. In this paper, we show that in several natural and prominent cases the optimization problem is tractable even when the message space is limited. In particular, we study signaling under a symmetry or an independence assumption on the distribution of utility values for the actions. For symmetric distributions, we provide a novel characterization of the optimal signaling scheme. It results in a polynomial-time algorithm to compute an optimal scheme for many compactly represented symmetric distributions. In the independent case, we design a constant-factor approximation algorithm, which stands in marked contrast to the hardness of approximation in the general case. [ABSTRACT FROM AUTHOR]

This paper has two main goals: (a) establish several statistical properties—consistency, asymptotic distributions, and convergence rates—of stationary solutions and values of a class of coupled nonconvex and nonsmooth empirical risk-minimization problems and (b) validate these properties by a noisy amplitude-based phase-retrieval problem, the latter being of much topical interest. Derived from available data via sampling, these empirical risk-minimization problems are the computational workhorse of a population risk model that involves the minimization of an expected value of a random functional. When these minimization problems are nonconvex, the computation of their globally optimal solutions is elusive. Together with the fact that the expectation operator cannot be evaluated for general probability distributions, it becomes necessary to justify whether the stationary solutions of the empirical problems are practical approximations of the stationary solution of the population problem. When these two features, general distribution and nonconvexity, are coupled with nondifferentiability that often renders the problems "non-Clarke regular," the task of the justification becomes challenging. Our work aims to address such a challenge within an algorithm-free setting. The resulting analysis is, therefore, different from much of the analysis in the recent literature that is based on local search algorithms. Furthermore, supplementing the classical global minimizer-centric analysis, our results offer a promising step to close the gap between computational optimization and asymptotic analysis of coupled, nonconvex, nonsmooth statistical estimation problems, expanding the former with statistical properties of the practically obtained solution and providing the latter with a more practical focus pertaining to computational tractability. [ABSTRACT FROM AUTHOR]

We examine the dynamic inventory liquidation problem, in which a retailer liquidates a fixed number of identical items over a time period by strategically setting prices periodically according to knowledge about stochastic demand. We propose to solve the liquidation problem by deriving a deterministic representation of stochastic demand. Assuming that customer arrival and valuations follow known statistical distributions (e.g., estimated from past transaction data), the expected arrivals and expected order statistics of valuation distributions represent informative and advantageous approximations of demand. Under the deterministic demand representation, we develop a greedy heuristic for finding the optimal liquidation strategy that result in maximum total revenue. The heuristic approach is computationally highly efficient and provides optimal solutions under deterministic demand representation when customer valuation follows various typical statistical distributions. Compared with two simple and commonly used liquidation strategies (i.e., the fixed-price strategy and the fixed-quantity strategy), our heuristic yields higher liquidation revenue. Compared with sophisticated approaches that can find optimal liquidation strategies under stochastic demand (e.g., stochastic dynamic programming), our approach runs several magnitudes faster and still yields near optimal expected revenue. Therefore, the heuristic approach can serve as a useful tool for managers to make liquidation-related decisions in realistic, stochastic demand scenarios. We develop efficient computational strategies for the inventory liquidation problem, which is characterized by a retailer disposing of a fixed amount of inventory over a period of time. Liquidating end-of-cycle products optimally represents a challenging problem owing to its inherent stochasticity. The growing scale of liquidation problems further increases the need for solutions that are revenue- and time-efficient. We propose to address the inventory liquidation problem by deriving deterministic representations of stochastic demand, which provides significant theoretical and practical benefits as well as an intuitive understanding of the problem and the proposed solution. First, this paper develops a dynamic programming approach and a greedy heuristic approach to find the optimal liquidation strategy under deterministic demand representation. Importantly, we show that our heuristic approach is optimal under realistic conditions and is computationally less complex than dynamic programming. Second, we explore the relationships between liquidation revenue and several key elements of the liquidation problem via both computational experiments and theoretical analyses. We derive multiple managerial implications and demonstrate how the proposed heuristic approach can serve as an efficient decision support tool for inventory managers. Third, under stochastic demand, we conduct a comprehensive set of simulation experiments to benchmark the performance of our proposed heuristic approach with alternatives, including other simple approaches (e.g., the fixed-price strategy) as well as advanced stochastic approaches (e.g., stochastic dynamic programming). In particular, we consider a strategy that uses the proposed greedy heuristic to determine prices iteratively throughout the liquidation period. Computational experiments demonstrate that such iterative strategy stably produces higher total revenue than other alternatives and produces near-optimal total revenue in expectation while maintaining significant computational efficiency, compared with advanced techniques that solve the liquidation problem directly under stochastic demand. Our work advances the computational design for inventory liquidation and provides practical insights. The online supplement is available at https://doi.org/10.1287/isre.2018.0819. [ABSTRACT FROM AUTHOR]

Discrete approximation of probability distributions is an important topic in stochastic programming. In this paper, we extend the research on this topic to distributionally robust optimization (DRO), where discretization is driven by either limited availability of empirical data (samples) or a computational need for improving numerical tractability. We start with a one-stage DRO where the ambiguity set is defined by generalized prior moment conditions and quantify the discrepancy between the discretized ambiguity set and the original one by employing the Kantorovich/Wasserstein metric. The quantification is achieved by establishing a new form of Hoffman's lemma for moment problems under a general class of metrics—namely, ζ-structures. We then investigate how the discrepancy propagates to the optimal value in one-stage DRO and discuss further the multistage DRO under nested distance. The technical results lay down a theoretical foundation for various discrete approximation schemes to be applied to solve one-stage and multistage distributionally robust optimization problems. [ABSTRACT FROM AUTHOR]

Worst-case risk measures provide a means of calculating the largest value of risk when only partial information of the underlying distribution is available. For popular risk measures such as value-at-risk (VaR) and conditional value-at-risk (CVaR) it is now known that their worst-case counterparts can be evaluated in closed form when only the first two moments are known. We show in this paper that closed-form solutions exist for a general class of law invariant coherent risk measures, which consist of spectral risk measures (and thus CVaR also) as special cases. Moreover, we provide worst-case distributions characterized in terms of risk spectrums, which can take any form of distribution bounded from below. As applications of the closed-form results, new formulas are derived for calculating the worst-case values of higher order risk measures and higher order semideviation, and new robust portfolio optimization models are provided. The online appendix is available at https://doi.org/10.1287/opre.2018.1736. [ABSTRACT FROM AUTHOR]

On Modeling the Probability Distribution of Stochastic Sums In the "Technical Note—On Matrix Exponential Differentiation with Application to Weighted Sum Distributions," Das, Tsai, Kyriakou, and Fusai propose an efficient methodology for approximating the unknown probability distribution of a weighted stochastic sum or time integral. Resulting from earlier contributions based on continuous-time Markov chain approximations of one-dimensional Markov processes is the Laplace transform of the unknown distribution available in exponential matrix form. In this paper, the authors develop a bona fide Pearson curve-fitting approach to this distribution based on the moments, which they recover from the derivatives of the Laplace transform. Motivated by the computational hurdles toward this, they derive computationally efficient closed-form expressions for the derivatives of the matrix exponential. They then apply to pricing average-based options. In this note, we revisit the innovative transform approach introduced by Cai, Song, and Kou [(2015) A general framework for pricing Asian options under Markov processes. Oper. Res. 63(3):540–554] for accurately approximating the probability distribution of a weighted stochastic sum or time integral under general one-dimensional Markov processes. Since then, Song, Cai, and Kou [(2018) Computable error bounds of Laplace inversion for pricing Asian options. INFORMS J. Comput. 30(4):625–786] and Cui, Lee, and Liu [(2018) Single-transform formulas for pricing Asian options in a general approximation framework under Markov processes. Eur. J. Oper. Res. 266(3):1134–1139] have achieved an efficient reduction of the original double to a single-transform approach. We move one step further by approaching the problem from a new angle and, by dealing with the main obstacle relating to the differentiation of the exponential of a matrix, we bypass the transform inversion. We highlight the benefit from the new result by means of some numerical examples. [ABSTRACT FROM AUTHOR]

Taking Advantage of the Lead Time Randomness in Supply Chains Randomness in lead times is a major—and increasingly important—issue of inventory management, as a variety of risk factors motivate companies to diversify their supply sources and rely on distributed networks of suppliers. In "Exploiting Random Lead Times for Significant Inventory Cost Savings," A. Stolyar and Q. Wang show that, surprisingly, instead of being a damaging factor to supply chain performance, randomness may be harnessed for potentially very substantial reductions of inventory costs. Specifically, the theoretical analysis and simulation results in the paper demonstrate that, under certain conditions, appropriately designed novel policies can significantly outperform the conventional base stock policies. We study the classical single-item inventory system in which unsatisfied demands are backlogged. Replenishment lead times are random, independent identically distributed, causing orders to cross in time. We develop a new inventory policy to exploit implications of lead time randomness and order crossover, and evaluate its performance by asymptotic analysis and simulations. Our policy does not follow the basic principle of constant base stock (CBS) policy, or more generally, (s , S) and (R , q) policies, which is to keep the inventory position within a fixed range. Instead, it uses the current inventory level (= inventory-on-hand minus backlog) to set a dynamic target for inventory in-transit, and place orders to follow this target. Our policy includes CBS policy as a special case, under a particular choice of a policy parameter. We show that our policy can significantly reduce the average inventory cost compared with CBS policy. Specifically, we prove that if the lead time is exponentially distributed, then under our policy, with properly chosen policy parameters, the expected (absolute) inventory level scales as o (r) , as the demand rate r → ∞. In comparison, it is known to scale as Θ (r) under CBS policy. In particular, this means that, as r → ∞ , the average inventory cost under our policy vanishes in comparison with that under CBS policy. Furthermore, our simulations show that the advantage of our policy remains to be substantial under nonexponential lead time distributions, and may even be greater than under exponential distribution. We also use simulations to compare the average cost under our policy with that achieved under an optimal policy for some cases where computing the optimal cost is tractable. The results show that our policy removes a majority of excess costs of CBS policy over the minimum cost, leading to much smaller optimality gaps. [ABSTRACT FROM AUTHOR]

Much research on advice taking examines how people revise point estimates given input from others. This work has established that people often egocentrically discount advice. If they were to place more weight on advice, their point estimates would be more accurate. Yet the focus on point estimates and accuracy has resulted in a narrow conception of what it means to heed advice. We distinguish between revisions of point estimates and revisions of attendant probability distributions. Point estimates represent a single best guess; distributions represent the probabilities that people assign to all possible answers. A more complete picture of advice taking is provided by considering revisions of distributions, which reflect changes in both confidence and best guesses. We capture this using a new measure of advice utilization: the influence of advice. We observe that, when input from a high-quality advisor largely agrees with a person's initial opinion, it engenders little change in one's point estimate and, hence, little change in accuracy yet significantly increases confidence. This pattern suggests more advice taking than generally suspected. However, it is not necessarily beneficial. Because people are typically overconfident to begin with, receiving advice that agrees with their initial opinion can exacerbate overconfidence. In several experiments, we manipulate advisor quality and measure the extent to which advice agrees with a person's initial opinion. The results allow us to pinpoint circumstances in which heeding advice is beneficial, improving accuracy or reducing overconfidence, as well as circumstances in which it is harmful, hurting accuracy or exacerbating overconfidence. This paper was accepted by Yuval Rottenstreich, judgment and decision making. [ABSTRACT FROM AUTHOR]

Ann likes oranges much more than apples; Bob likes apples much more than oranges. Tomorrow they will receive one fruit that will be an orange or an apple with equal probability. Giving one half to each agent is fair for each realization of the fruit. However, agreeing that whatever fruit appears will go to the agent who likes it more gives a higher expected utility to each agent and is fair in the average sense: in expectation, each agent prefers the allocation to the equal division of the fruit; that is, the agent gets a fair share. We turn this familiar observation into an economic design problem: upon drawing a random object (the fruit), we learn the realized utility of each agent and can compare it to the mean of the agent's distribution of utilities; no other statistical information about the distribution is available. We fully characterize the division rules using only this sparse information in the most efficient possible way while giving everyone a fair share. Although the probability distribution of individual utilities is arbitrary and mostly unknown to the manager, these rules perform in the same range as the best rule when the manager has full access to this distribution. This paper was accepted by Ilia Tsetlin, behavioral economics and decision analysis. [ABSTRACT FROM AUTHOR]

In many engineered systems, optimization is used for decision making at time scales ranging from real-time operation to long-term planning. This process often involves solving similar optimization problems over and over again with slightly modified input parameters, often under tight latency requirements. We consider the problem of using the information available through this repeated solution process to learn important characteristics of the optimal solution as a function of the input parameters. Our proposed method is based on learning relevant sets of active constraints, from which the optimal solution can be obtained efficiently. Using active sets as features preserves information about the physics of the system, enables interpretable results, accounts for relevant safety constraints, and is easy to represent and encode. However, the total number of active sets is also very large, as it grows exponentially with system size. The key contribution of this paper is a streaming algorithm that learns the relevant active sets from training samples consisting of the input parameters and the corresponding optimal solution, without any restrictions on the problem type, problem structure or probability distribution of the input parameters. The algorithm comes with theoretical performance guarantees and is shown to converge fast for problem instances with a small number of relevant active sets. It can thus be used to establish simultaneously learn the relevant active sets and the practicability of the learning method. Through case studies in optimal power flow, supply chain planning, and shortest path routing, we demonstrate that often only a few active sets are relevant in practice, suggesting that active sets provide an appropriate level of abstraction for a learning algorithm to target. [ABSTRACT FROM AUTHOR]

In this paper, we develop a zonal-based flexible bus services (ZBFBS) by considering both passenger demands' spatial (origin-destination or OD) and volume stochastic variations. Service requests are grouped by zonal OD pairs and number of passengers per request, and aggregated into demand categories which follow certain probability distributions. A two-stage stochastic program is formulated to minimize the expected operating cost of ZBFBS, in which the zonal visit sequences of vehicles are determined in stage 1, whereas in stage 2, service requests are assigned to either regular routes determined in stage 1 or ad hoc services that incur additional costs. Demand volume reliability and detour time reliability are introduced to ensure quality of the services and separate the problem into two phases for efficient solutions. In phase 1, given the reliability requirements, we minimize the cost of operating the regular services. In phase 2, we optimize the passenger assignment to vehicles to minimize the expected ad hoc service cost. The reliabilities are then optimized by a gradient-based approach to minimize the sum of the regular service operating cost and expected ad hoc service cost. We conduct numerical studies on vehicle capacity, detour time limit and demand volume to demonstrate the potential of ZBFBS, and apply the model to Chengdu, China, based on real data to illustrate its applicability. [ABSTRACT FROM AUTHOR]

This paper develops novel mathematical models to maximize the benefits derived from the distribution of critical supplies to populations in need after a disaster. The formulations are based on welfare economics and the use of social costs, which are incurred by the segments of society involved in, and impacted by, the relief distribution strategy. The costs to the relief group are assessed as logistical costs, whereas the impacts to the beneficiaries are measured as the effects that the relief distribution has on their deprivation costs, which are the economic value of human suffering resulting from the lack of access to a good or service. The impacts on beneficiaries take into account two components: the reduction in deprivation costs for the recipients of the aid and the increase in deprivation costs for those individuals who do not receive the aid at a delivery epoch (the opportunity costs of the delivery strategy). The paper develops an inventory-allocation-routing model for the optimal assignment of critical supplies that minimizes social costs, designs suitable heuristic solution approaches, and assesses the performance of the heuristics using numerical experiments. The results, coupled with the insight gained from the models developed, are used to establish conclusions and policy recommendations. [ABSTRACT FROM AUTHOR]

In this paper, we develop a distributionally robust optimization model for the design of rail transit tactical planning strategies and disruption tolerance enhancement under downtime uncertainty. First, a novel performance function evaluating the rail transit disruption tolerance is proposed. Specifically, the performance function maximizes the worst-case expected downtime that can be tolerated by rail transit networks over a family of probability distributions of random disruption events given a threshold commuter outflow. This tolerance function is then applied to an optimization problem for the planning design of platform downtime protection and bus-bridging services given budget constraints. In particular, our implementation of platform downtime protection strategy relaxes standard assumptions of robust protection made in network fortification and interdiction literature. The resulting optimization problem can be regarded as a special variation of a two-stage distributionally robust optimization model. In order to achieve computational tractability, optimality conditions of the model are identified. This allows us to obtain a linear mixed-integer reformulation that can be solved efficiently by solvers like CPLEX. Finally, we show some insightful results based on the core part of Singapore Mass Rapid Transit Network. [ABSTRACT FROM AUTHOR]

Joint chance-constrained optimization problems under discrete distributions arise frequently in financial management and business operations. These problems can be reformulated as mixed-integer programs. The size of reformulated integer programs is usually very large even though the original problem is of medium size. This paper studies an augmented Lagrangian decomposition method for finding high-quality feasible solutions of complex optimization problems, including nonconvex chance-constrained problems. Different from the current augmented Lagrangian approaches, the proposed method allows randomness to appear in both the left-hand-side matrix and the right-hand-side vector of the chance constraint. In addition, the proposed method only requires solving a convex subproblem and a 0-1 knapsack subproblem at each iteration. Based on the special structure of the chance constraint, the 0-1 knapsack problem can be computed in quasi-linear time, which keeps the computation for discrete optimization subproblems at a relatively low level. The convergence of the method to a first-order stationary point is established under certain mild conditions. Numerical results are presented in comparison with a set of existing methods in the literature for various real-world models. It is observed that the proposed method compares favorably in terms of the quality of the best feasible solution obtained within a certain time for large-size problems, particularly when the objective function of the problem is nonconvex or the left-hand-side matrix of the constraints is random. [ABSTRACT FROM AUTHOR]

In portfolio decision analysis, features comprise the objectives, alternatives, physics, and information that define a decision context. By modeling features, decision analysts forecast the expected utilities of the alternatives. A model is complete if it contains all the features. A model is well-calibrated if it correctly predicts the probability distributions of each alternative's utility, whereas ill-calibrated models, like those that suffer the optimizer's curse, do not. Friction identifies qualities of a situation that prevent decision analysts from creating complete, well-calibrated models. When friction is significant, can maximizing expected utility be a suboptimal decision rule? Is satisfying decision theory's axioms a necessary or sufficient condition for good decision making? Can rules that violate the axioms outperform rules that satisfy them? A simulation study of how unbiased, imprecise forecasts of payoffs affect project selection finds that, for the example tested, the answers are yes, no, and yes, which suggests that further studies of friction may be worthwhile. Discussions of friction bookend the study, starting the paper by defining friction and concluding by presenting three frameworks, each one from a different field of study, that provide mathematical tools for studying friction. [ABSTRACT FROM AUTHOR]

This paper proposes a method to recover an unknown probability distribution given a censored or truncated sample from that distribution. The proposed method is a novel and conceptually simple detruncation method based on sampling the observed data according to weights learned by solving a simulation-based optimization problem; this method is especially appropriate in cases where little analytic information is available but the truncation process can be simulated. The proposed method is compared with the ubiquitous maximum likelihood estimation (MLE) method in a variety of synthetic validation experiments, where it is found that the proposed method performs slightly worse than perfectly specified MLE and competitively with slightly misspecified MLE. The practical application of this method is then demonstrated via a pair of case studies in which the proposed detruncation method is used alongside a car-sharing service simulator to estimate demand for round-trip car-sharing services in the Boston and New York metropolitan areas. [ABSTRACT FROM AUTHOR]

In this paper, we study distributionally robust optimization approaches for a one-stage stochastic minimization problem, where the true distribution of the underlying random variables is unknown but it is possible to construct a set of probability distributions, which contains the true distribution and optimal decision is taken on the basis of the worst-possible distribution from that set. We consider the case when the distributional set (which is also known as the ambiguity set) varies and its impact on the optimal value and the optimal solutions. A typical example is when the ambiguity set is constructed through samples and we need to look into the impact of increasing the sample size. The analysis provides a unified framework for convergence of some problems where the ambiguity set is approximated in a process with increasing information on uncertainty and extends the classical convergence analysis in stochastic programming. The discussion is extended briefly to a stochastic Nash equilibrium problem where each player takes a robust action on the basis of the worst subjective expected objective values. [ABSTRACT FROM AUTHOR]

The sparse inverse covariance matrix is used to model conditional dependencies between variables in a graphical model to fit a multivariate Gaussian distribution. Estimating the matrix from data are well known to be computationally expensive for large-scale problems. Sparsity is employed to handle noise in the data and to promote interpretability of a learning model. Although the use of a convex ℓ1 regularizer to encourage sparsity is common practice, the combinatorial ℓ0 penalty often has more favorable statistical properties. In this paper, we directly constrain sparsity by specifying a maximally allowable number of nonzeros, in other words, by imposing an ℓ0 constraint. We introduce an efficient approximate Newton algorithm using warm starts for solving the nonconvex ℓ0-constrained inverse covariance learning problem. Numerical experiments on standard data sets show that the performance of the proposed algorithm is competitive with state-of-the-art methods. Summary of Contribution: The inverse covariance estimation problem underpins many domains, including statistics, operations research, and machine learning. We propose a scalable optimization algorithm for solving the nonconvex ℓ0-constrained problem. [ABSTRACT FROM AUTHOR]

Accounting for travel time correlations when dispatching a fleet of vehicles Travel times on a road network are commonly affected by some degree of uncertainty. The duration of vehicle routes may then vary according to the observed travel time realizations. For managerial reasons, however, a fleet operator is generally interested in designing routes whose duration is not too dispersed with respect to their expected value. In this context, correlations among travel times play an important role, and failing to account for them might result in a large underestimation of the variance of the route duration. In "Branch-Price-and-Cut Algorithms for the Vehicle Routing Problem with Stochastic and Correlated Travel Times," B. Rostami, G. Desaulniers, F. Errico, and A. Lodi adopt a mean-variance model leading to a quadratic binary program. The authors propose two alternative set partitioning reformulations, which are then solved by branch-price-and-cut algorithms. The obtained solutions significantly reduce the time variability when compared with solutions of the classical vehicle routing problem. In this paper, we consider a version of the capacitated vehicle routing problem (CVRP) where travel times are assumed to be uncertain and statistically correlated (CVRP-SCT). In particular, we suppose that travel times follow a multivariate probability distribution whose first and second moments are known. The main purpose of the CVRP-CST is to plan vehicle routes whose travel times are reliable, in the sense that observed travel times are not excessively dispersed with respect to their expected value. To this scope we adopt a mean-variance approach, where routes with high travel time variability are penalized. This leads to a parametric binary quadratic program for which we propose two alternative set partitioning reformulations and show how to exploit the structure of the correlation matrix when there is correlation only between adjacent links. For each model, we develop an exact branch-price-and-cut algorithm, where the quadratic component is dealt with either in the column generation master problem or in its subproblem. We tested our algorithms on a rich collection of instances derived from well-known data sets. Computational results show that our algorithms can efficiently solve problem instances with up to 75 customers. Furthermore, the obtained solutions significantly reduce the time variability when compared with standard CVRP solutions. [ABSTRACT FROM AUTHOR]

Computing and minimizing the worst-case bound on the expected shortfall risk of a portfolio given partial information on the distribution of the asset returns is an important problem in risk management. One such bound that been proposed is for the worst-case distribution that is "close" to a reference distribution where closeness in distance among distributions is measured using φ -divergence. In this paper, we advocate the use of such ambiguity sets with a tree structure on the univariate and bivariate marginal distributions. Such an approach has attractive modeling and computational properties. From a modeling perspective, this provides flexibility for risk management applications where there are many more choices for bivariate copulas in comparison with multivariate copulas. Bivariate copulas form the basis of the nested tree structure that is found in vine copulas. Because estimating a vine copula is fairly challenging, our approach provides robust bounds that are valid for the tree structure that is obtained by truncating the vine copula at the top level. The model also provides flexibility in tackling instances when the lower dimensional marginal information is inconsistent that might arise when multiple experts provide information. From a computational perspective, under the assumption of a tree structure on the bivariate marginals, we show that the worst-case expected shortfall is computable in polynomial time in the input size when the distributions are discrete. The corresponding distributionally robust portfolio optimization problem is also solvable in polynomial time. In contrast, under the assumption of independence, the expected shortfall is shown to be #P-hard to compute for discrete distributions. We provide numerical examples with simulated and real data to illustrate the quality of the worst-case bounds in risk management and portfolio optimization and compare it with alternate probabilistic models such as vine copulas and Markov tree distributions. [ABSTRACT FROM AUTHOR]