Knowledge that Transforms

This paper addresses a general class of capacity planning problems under uncertainty, which arises, for example, in semiconductor tool purchase planning. Using a scenario tree to model the evolution of the uncertainties, we develop a multistage stochastic integer programming formulation for the problem. In contrast to earlier two-stage approaches, the multistage model allows for revision of the capacity expansion plan as more information regarding the uncertainties is revealed. We provide analytical bounds for the value of multistage stochastic programming (VMS) afforded over the two-stage approach. By exploiting a special substructure inherent in the problem, we develop an efficient approximation scheme for the difficult multistage stochastic integer program and prove that the proposed scheme is asymptotically optimal. Computational experiments with realistic-scale problem instances suggest that the VMS for this class of problems is quite high; moreover, the quality and performance of the approximation scheme is very satisfactory. Fortunately, this is more so for instances for which the VMS is high.

In this paper, we propose a methodology for constructing uncertainty sets within the framework of robust optimization for linear optimization problems with uncertain parameters. Our approach relies on decision maker risk preferences. Specifically, we utilize the theory of coherent risk measures initiated by Artzner et al. (1999) [Artzner, P., F. Delbaen, J. Eber, D. Heath. 1999. Coherent measures of risk. Math. Finance 9 203–228.], and show that such risk measures, in conjunction with the support of the uncertain parameters, are equivalent to explicit uncertainty sets for robust optimization. We explore the structure of these sets in detail. In particular, we study a class of coherent risk measures, called distortion risk measures, which give rise to polyhedral uncertainty sets of a special structure that is tractable in the context of robust optimization. In the case of discrete distributions with rational probabilities, which is useful in practical settings when we are sampling from data, we show that the class of all distortion risk measures (and their corresponding polyhedral sets) are generated by a finite number of conditional value-at-risk (CVaR) measures. A subclass of the distortion risk measures corresponds to polyhedral uncertainty sets symmetric through the sample mean. We show that this subclass is also finitely generated and can be used to find inner approximations to arbitrary, polyhedral uncertainty sets.

As large-scale discrete-event stochastic simulation becomes a tool that is used routinely for the design and analysis of stochastic systems, the need for input-modeling support with the ability to represent complex interactions and interdependencies among the components of multivariate time-series input processes is more critical than ever. Motivated by the failure of independent and identically distributed random variables to represent such input processes, a comprehensive framework called Vector-Autoregressive-To-Anything (VARTA) has been introduced for multivariate time-series input modeling. Despite its flexibility in capturing a wide variety of distributional shapes, we show that VARTA falls short in representing dependence structures that arise in situations where extreme component realizations occur together. We demonstrate that it is possible to extend VARTA to work for such dependence structures via the use of the copula theory, which has been used primarily for random vectors in the simulation input-modeling literature, for multivariate time-series input modeling. We show that our copula-based multivariate time-series input model, which includes VARTA as a special case, allows the development of statistically valid fitting and fast sampling algorithms well suited for driving large-scale stochastic simulations.

We develop a robust optimization framework for dynamic empty repositioning problems modeled using time-space networks. In such problems, uncertainty arises primarily from forecasts of future supplies and demands for assets at different time epochs. The proposed approach models such uncertainty using intervals about nominal forecast values and a limit on the systemwide scaled deviation from the nominal forecast values. A robust repositioning plan is defined as one in which the typical flow balance constraints and flow bounds are satisfied for the nominal forecast values, and the plan is recoverable under a limited set of recovery actions. A plan is recoverable when feasibility can be reestablished for any outcome in a defined uncertainty set. We develop necessary and sufficient conditions for flows to be robust under this definition for three types of allowable recovery actions. When recovery actions allow only flow changes on inventory arcs, we show that the resulting problem is polynomially solvable. When recovery actions allow limited reactive repositioning flows, we develop feasibility conditions that are independent of the size of the uncertainty set. A computational study establishes the practical viability of the proposed framework.

We analyze a planning model for a firm or public organization that needs to cover uncertain demand for a given item by procuring supplies from multiple sources. The necessity to employ multiple suppliers arises from the fact that when an order is placed with any of the suppliers, only a random fraction of the order size is usable. The model considers a single demand season with a given demand distribution, where all supplies need to be ordered simultaneously before the start of the season. The suppliers differ from one another in terms of their yield distributions, their procurement costs, and capacity levels. The planning model determines which of the potential suppliers are to be retained and what size order is to be placed with each. We consider two versions of the planning model: in the first, the service constraint model (SCM), the orders must be such that the available supply of usable units covers the random demand during the season with (at least) a given probability. In the second version of the model, the total cost model (TCM), the orders are determined so as to minimize the aggregate of procurement costs and end-of-the-season inventory and shortage costs. In the classical inventory model with a single, fully reliable supplier, these two models are known to be equivalent, but the equivalency breaks down under multiple suppliers with unreliable yields. For both the service constraint and total cost models, we develop a highly efficient procedure that generates the optimal set of suppliers as well as the optimal orders to be assigned to each. Most importantly, these procedures generate a variety of important qualitative insights, for example, regarding which sets of suppliers allow for a feasible solution, both when they have ample supply and when they are capacitated, and how various model parameters influence the selected set of suppliers, the aggregate order size, and the optimal cost values.

In this paper, we introduce the extended affinely adjustable robust counterpart to modeling and solving multistage uncertain linear programs with fixed recourse. Our approach first reparameterizes the primitive uncertainties and then applies the affinely adjustable robust counterpart proposed in the literature, in which recourse decisions are restricted to be linear in terms of the primitive uncertainties. We propose a special case of the extended affinely adjustable robust counterpart—the splitting-based extended affinely adjustable robust counterpart—and illustrate both theoretically and computationally that the potential of the affinely adjustable robust counterpart method is well beyond the one presented in the literature. Similar to the affinely adjustable robust counterpart, our approach ends up with deterministic optimization formulations that are tractable and scalable to multistage problems.

This paper considers the worst-case Conditional Value-at-Risk (CVaR) in the situation where only partial information on the underlying probability distribution is available. The minimization of the worst-case CVaR under mixture distribution uncertainty, box uncertainty, and ellipsoidal uncertainty are investigated. The application of the worst-case CVaR to robust portfolio optimization is proposed, and the corresponding problems are cast as linear programs and second-order cone programs that can be solved efficiently. Market data simulation and Monte Carlo simulation examples are presented to illustrate the proposed approach.

The purpose of this paper is to introduce the reader to the field of closed-loop supply chains with a strong business perspective, i.e., we focus on profitable value recovery from returned products. It recounts the evolution of research in this growing area over the past 15 years, during which it developed from a narrow, technically focused niche area to a fully recognized subfield of supply chain management. We use five phases to paint an encompassing view of this evolutionary process for the reader to understand past achievements and potential future operations research opportunities.

We study an oligopoly consisting of M leaders and N followers that supply a homogeneous product (or service) noncooperatively. Leaders choose their supply levels first, knowing the demand function only in distribution. Followers make their decisions after observing the leader supply levels and the realized demand function. We term the resulting equilibrium a stochastic multiple-leader Stackelberg-Nash-Cournot (SMS) equilibrium. We show the existence and uniqueness of SMS equilibrium under mild assumptions. We also propose a computational approach to find the equilibrium based on the sample average approximation method and analyze its rate of convergence. Finally, we apply this framework to model competition in the telecommunication industry.

During the past few years, there has been a trend to enrich traditional revenue management models built upon the independent demand paradigm by accounting for customer choice behavior. This extension involves both modeling and computational challenges. One way to describe choice behavior is to assume that each customer belongs to a segment, which is characterized by a consideration set, i.e., a subset of the products provided by the firm that a customer views as options. Customers choose a particular product according to a multinomial-logit criterion, a model widely used in the marketing literature. In this paper, we consider the choice-based, deterministic, linear programming model (CDLP) of Gallego et al. (2004) [Gallego, G., G. Iyengar, R. Phillips, A. Dubey. 2004. Managing flexible products on a network. Technical Report CORC TR-2004-01, Department of Industrial Engineering and Operations Research, Columbia University, New York], and the follow-up dynamic programming decomposition heuristic of van Ryzin and Liu (2008) [van Ryzin, G. J., Q. Liu. 2008. On the choice-based linear programming model for network revenue management. Manufacturing Service Oper. Management 10(2) 288–310]. We focus on the more general version of these models, where customers belong to overlapping segments. To solve the CDLP for real-size networks, we need to develop a column generation algorithm. We prove that the associated column generation subproblem is indeed NP-hard and propose a simple, greedy heuristic to overcome the complexity of an exact algorithm. Our computational results show that the heuristic is quite effective and that the overall approach leads to high-quality, practical solutions.