Search

We take a novel approach to decision problems involving binary activity-selection decisions competing for scarce resources. The literature approaches such problems by forming an optimal portfolio of activities. However, often practitioners instead form a rank-ordered list of activities and select those with the highest priority. We account for both viewpoints. We rank activities considering both the uncertainty in the problem parameters and the optimal portfolio that will be obtained once the uncertainty is revealed. We use stochastic integer programming as a modeling framework, and we apply our approach to a facility location problem and a multidimensional knapsack problem. We develop two sets of cutting planes to improve computation. Data, as supplemental material, are available at http://dx.doi.org/10.1287/mnsc.2013.1865. Keywords: priority lists; activity-selection problem; stochastic programming; cutting planes History : Received December 20, 2011; accepted February 17, 2013, by Dimitris Bertsimas, optimization. Published online in Articles in Advance May 15, 2014., 1. Introduction Resource-constrained activity-selection problems (RCASPs) involve binary activity-selection decisions, which compete for scarce resources. The bulk of the current literature approaches RCASPs by forming an optimal portfolio of activities [...]

We consider capital investments under uncertainty. A typical approach to this problem, when the problem parameters are assumed known, is via a multi-knapsack model. This model takes as input annual budgets as well as the cost streams and profit--i.e., net present value (NPV)--of each project. Its output is a portfolio of projects with the highest total NPV, observing yearly budget constraints. We argue that such a portfolio fails to hedge against uncertainties in the budgets, the cost streams, and the profits. As an alternative, we propose a model that forms an optimal priority list of projects, incorporating multiple scenarios for these input parameters. We apply our approach to two sets of example projects from the South Texas Project Nuclear Operating Company. DOI: 10.1080/00137910903338545, INTRODUCTION When practitioners plan for capital budgeting they often form a priority list of candidate projects, by scoring the projects individually, using economic measures like net present value, benefit-investment ratio, [...]

We describe two stochastic network interdiction models for thwarting nuclear smuggling. In the first model, the smuggler travels through a transportation network on a path that maximizes the probability of evading detection, and the interdictor installs radiation sensors to minimize that evasion probability. The problem is stochastic because the smuggler's origin-destination pair is known only through a probability distribution at the time when the sensors are installed. In this model, the smuggler knows the locations of all sensors and the interdictor and the smuggler 'agree' on key network parameters, namely the probabilities the smuggler will be detected while traversing the arcs of the transportation network. Our second model differs in that the interdictor and smuggler can have differing perceptions of these network parameters. This model captures the case in which the smuggler is aware of only a subset of the sensor locations. For both models, we develop the important special case in which the sensors can only be installed at border crossings of a single country so that the resulting model is defined on a bipartite network. In this special case, a class of valid inequalities reduces the computation time for the identical-perceptions model. Keywords: Network interdiction, integer programming, stochastic programming, 1. Introduction We develop stochastic network interdiction models designed to locate radiation sensors, which detect gamma and neutron emissions from nuclear material, at critical border crossings in the Former Soviet [...]

We develop a class of lower bounds on the expectation of a convex function. The bounds utilize the first two moments of the underlying random variable, whose support is contained [...]

Bayesian forecasting models provide distributional estimates for random parameters, and relative to classical schemes, have the advantage that they can rapidly capture changes in nonstationary systems using limited historical data. Unlike deterministic optimization, stochastic programs explicitly incorporate distributions for random parameters in the model formulation, and thus have the advantage that the resulting solutions more fully hedge against future contingencies. In this paper, we exploit the strengths of Bayesian prediction and stochastic programming in a rolling-horizon approach that can be applied to solve real-world problems. We illustrate the methodology on an employee production scheduling problem with uncertain up-times of manufacturing equipment and uncertain production rates. Computational results indicate the value of our approach., 1. Introduction We consider a production planning problem in which a nominal weekday employee schedule is published at the beginning of each month in the face of uncertain production rates [...]