bluuebunny/crossref_metadata_2025 huggingface dataset:
A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints
Authors: Ahuja Ravindra K. , Orlin James B.
Published: December 2003

We consider the problem of minimizing Σj∈N Cj(xj), subject to the following chain constraints x1 ≤ x2 ≤ x3 ≤ … ≤ xn, where Cj(xj) is a convex function of xj for each j ∈ N = {1,2, … ,n}. This problem is a generalization of the isotonic regression problems with complete order, an important class of problems in regression analysis that has been examined extensively in the literature. We refer to this problem as the generalized isotonic regression problem. In this paper, we focus on developing a fast-scaling algorithm to obtain an integer solution of the generalized isotonic regression problem. Let U denote the difference between an upper bound on an optimal value of xn and a lower bound on an optimal value of x1. Under the assumption that the evaluation of any function Cj (xj) takes O(1) time, we show that the generalized isotonic regression problem can be solved in O(n log U) time. This improves by a factor of n the previous best running time of O(n2 log U) to solve the same problem. In addition, when our algorithm is specialized to the isotonic median regression problem (where Cj(xj) = cj|xj−aj|) for specified values of cjs and ajs, the algorithm obtains a real-valued optimal solution in O(n log n) time. This time bound matches the best available time bound to solve the isotonic median regression problem, but our algorithm uses simpler data structures and may be easier to implement.
Computing the Optimal Replenishment Policy for Inventory Systems with Random Discount Opportunities
Authors: Feng Y. , Sun J.
Published: December 2003

The paper considers the optimal control of a single-item continuous-review inventory system with random demand and discount opportunities. Items can always be purchased with the regular order setup and variable costs. However, when a discount opportunity occurs, they can also be purchased with a different setup cost and a lower variable cost. Demands for individual items and discount opportunities occur according to independent Poisson processes. The paper proposes an algorithm to compute the parameters of the optimal replenishment policy, which has been shown to be an (r, R, d, D) policy where r < R, r ≤ d, and d < D. Under an (r, R, d, D) policy, when the inventory position drops to the level r, an order is placed with the regular costs to increase the inventory position to R; and when a discount opportunity occurs at or below d, an order is placed with the discount costs to increase the inventory position to D. The algorithm is based on a bisection search procedure to minimize the long-run average cost and is finitely convergent.
A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands
Authors: Secomandi Nicola
Published: December 2003

The paper considers the single vehicle routing problem with stochastic demands. While most of the literature has studied the a priori solution approach, this work focuses on computing a reoptimization-type routing policy. This is obtained by sequentially improving a given a priori solution by means of a rollout algorithm. The resulting rollout policy appears to be the first computationally tractable algorithm for approximately solving the problem under the reoptimization approach. After describing the solution strategy and providing properties of the rollout policy, the policy behavior is analyzed by conducting a computational investigation. Depending on the quality of the initial solution, the rollout policy obtains 1% to 4% average improvements on the a priori approach with a reasonable computational effort.
An Illustrative Application of Idea (Imprecise Data Envelopment Analysis) to a Korean Mobile Telecommunication Company
Authors: Cooper William W. , Park Kyung Sam , Yu Gang
Published: December 2003

Data Envelopment Analysis (DEA) models, as ordinarily employed, assume that the data for all inputs and outputs are known exactly. In some applications, however, a number of factors may involve imprecise data, which take forms such as ordinal rankings and knowledge only of bounds. Here we provide an example involving a Korean mobile telecommunication company. The Imprecise Data Envelopment Analysis (IDEA) method we use permits us to deal not only with imprecise data and exact data but also with weight restrictions as in the (now) widely used “Assurance Region” (AR) and “cone-ratio envelopment” approaches to DEA. We also show how to transform AR bounds on the variables, obtained from managerial assessments, for instance, into data adjustments. This involves an extended IDEA model, which we refer to as AR-IDEA. All these uses are illustrated by an example application directed to evaluate efficiencies of branch offices of a telecommunication company in Korea.
Near-Optimal Pricing and Replenishment Strategies for a Retail/Distribution System
Authors: Chen Fangruo , Federgruen Awi , Zheng Yu-Sheng
Published: December 2003

This paper integrates pricing and replenishment decisions for the following prototypical two-echelon distribution system with deterministic demands. A supplier distributes a single product to multiple retailers, who in turn sell it to consumers. The retailers serve geographically dispersed, heterogeneous markets. The demand in each retail market arrives continuously at a constant rate, which is a general decreasing function of the retail price in the market. The supplier replenishes its inventory through orders (purchases, production runs) from a source with ample capacity. The retailers replenish their inventories from the supplier. We develop efficient algorithms to determine optimal pricing and replenishment strategies for the following three channel structures. The first is the vertically integrated channel, where the system-wide pricing and replenishment strategies are determined by a central planner whose objective is to maximize the system-wide profits. The second structure is that of a vertically integrated channel in which pricing and operational decisions are made sequentially by separate functional departments. The third channel structure is decentralized, i.e., the supplier and the retailers are independent, profit-maximizing firms with the supplier acting as a Stackelberg game leader. We apply our algorithms to a set of numerical examples to quantify the supply chain inefficiencies due to functional segregation or uncoordinated decision making in a decentralized channel. We also gain insight into systematic differences in the associated pricing and operational patterns.
Generating Experimental Data for Computational Testing with Machine Scheduling Applications
Authors: Hall Nicholas G. , Posner Marc E.
Published: December 2003

The operations research literature provides little guidance about how data should be generated for the computational testing of algorithms or heuristic procedures. We discuss several widely used data generation schemes, and demonstrate that they may introduce biases into computational results. Moreover, such schemes are often not representative of the way data arises in practical situations. We address these deficiencies by describing several principles for data generation and several properties that are desirable in a generation scheme. This enables us to provide specific proposals for the generation of a variety of machine scheduling problems. We present a generation scheme for precedence constraints that achieves a target density which is uniform in the precedence constraint graph. We also present a generation scheme that explicitly considers the correlation of routings in a job shop. We identify several related issues that may influence the design of a data generation scheme. Finally, two case studies illustrate, for specific scheduling problems, how our proposals can be implemented to design a data generation scheme.
Generating Experimental Data for the Generalized Assignment Problem
Authors: Romeijn H. Edwin , Romero Morales Dolores
Published: December 2003

The Generalized Assignment Problem (GAP) is the problem of finding the minimal cost assignment of jobs to machines such that each job is assigned to exactly one machine, subject to capacity restrictions on the machines. We propose a new stochastic model for the GAP. A tight condition on this stochastic model under which the GAP is feasible with probability one when the number of jobs goes to infinity is derived. This new stochastic model enables us to analyze the adequacy of most of the random generators given for the GAP in the literature. We demonstrate that the random generators commonly used to test solution procedures for the GAP tend to create easier problem instances when the number of machines m increases. We describe a greedy heuristic for the GAP, and use it to illustrate the results from the paper.
Optimal Transmission Policies for Noisy Channels
Authors: Koole Ger , Liu Zhen , Righter Rhonda
Published: December 2003

We consider transmission policies for multiple users sharing a single wireless link to a base station. The noise, and hence the probability of correct transmission of a packet, depends on the state of the user receiving the packet. The state for each user is independent of the states of the other users and changes according to a two-state (good/bad) Markov chain. The state of a user is observed only when it transmits. We give conditions under which the optimal policy is the myopic policy, in which a packet is transmitted to the user that is most likely to be in the better of the two states. We do this by showing that the optimal value function is marginally linear in each of the users' probabilities of being in the good state. Our model also may be applied to flexible manufacturing systems with unreliable tools and networked computer systems.
Conditioning on One-Step Survival for Barrier Option Simulations
Authors: Glasserman Paul , Staum Jeremy
Published: December 2003

Pricing financial options often requires Monte Carlo methods. One particular case is that of barrier options, whose payoff may be zero depending on whether or not an underlying asset crosses a barrier during the life of the option. This paper develops variance reduction techniques that take advantage of the special structure of barrier options, and are appropriate for general simulation problems with similar structure. We use a change of measure at each step of the simulation to reduce the variance arising from the possibility of a barrier crossing at each monitoring date. The paper details the theoretical underpinnings of this method, and evaluates alternative implementations when exact distributions conditional on one-step survival are available and when not available. When these one-step conditional distributions are unavailable, we introduce algorithms that combine change of measure and estimation of conditional probabilities simultaneously. The methods proposed are more generally applicable to terminal reward problems on Markov processes with absorbing states.
A Multiplicative Decomposition Property of the Screening-and-Selection Procedures of Nelson et al.
Authors: Wilson James R.
Published: December 2003

Recently, Nelson et al. (2001a, b) formulated a class of combined screening-and-selection procedures for identifying the simulated system with optimal expected response when the number of alternatives is finite, but large enough to render conventional ranking-and-selection procedures impractical. Under a certain key assumption, they derived an additive decomposition lemma that provides a lower bound on the correct-selection probability when either the original or group-screening version of their combined screening-and-selection procedure is applied to randomly sampled normal populations with unknown and unequal variances. For both these procedures, we establish an improved lower bound on the correct-selection probability that is the product of (a) the probability that the best alternative will survive the first-stage screening procedure, and (b) the probability that the second-stage sampling-and-selection procedure will correctly identify the best alternative starting from the full set of alternatives. This multiplicative decomposition property offers a different perspective on the probabilistic structure of the entire class of combined screening-and-selection procedures developed by Nelson et al., and it does not require the key assumption of their additive decomposition lemma.
Perspectives on the Evolution of Simulation
Authors: Nance Richard E. , Sargent Robert G.
Published: December 2003

Simulation is introduced in terms of its different forms and uses, but the focus on discrete event modeling for systems analysis is dominant as it has been during the evolution of the technique within operations research and the management sciences. This evolutionary trace of over almost fifty years notes the importance of bidirectional influences with computer science, probability and statistics, and mathematics. No area within the scope of operations research and the management sciences has been affected more by advances in computing technology than simulation. This assertion is affirmed in the review of progress in those technical areas that collectively define the art and science of simulation. A holistic description of the field must include the roles of professional societies, conferences and symposia, and publications. The closing citation of a scientific value judgment from over 30 years in the past hopefully provides a stimulus for contemplating what lies ahead in the next 50 years.
Solving Real-World Linear Programs: A Decade and More of Progress
Authors: Bixby Robert E.
Published: December 2003

This paper is an invited contribution to the 50th anniversary issue of the journal Operations Research, published by the Institute of Operations Research and Management Science (INFORMS). It describes one person's perspective on the development of computational tools for linear programming. The paper begins with a short personal history, followed by historical remarks covering the some 40 years of linear-programming developments that predate my own involvement in this subject. It concludes with a more detailed look at the evolution of computational linear programming since 1987.
Abraham Charnes and W. W. Cooper (et al.): A Brief History of a Long Collaboration in Developing Industrial Uses of Linear Programming
Authors: Cooper W. W.
Published: December 2003

This paper describes a research strategy and its results, which guided a 40+ year collaboration between Abraham Charnes and William W. Cooper, which was initiated in a research center established at the (then) new Graduate School of Industrial Administration at Carnegie Institute of Technology (now Carnegie Mellon University). Initiated in collaboration with Bob Mellon of Gulf Oil Company, this strategy involved on-site collaborations with company personnel in more than 100 different companies and government agencies. An appendix to this paper describes the efforts of another team working from the same research center. This team, consisting of Charles Holt, Franco Modigliani, John Muth, and Herbert A. Simon, used a different research strategy with an accompanying application that also had important impacts on operations research/management science and other disciplines.
War and Peace: The First 25 Years of or in Great Britain
Authors: Haley K. Brian
Published: December 2003

This paper identifies a number of events and circumstances, which contributed in Great Britain during the period 1938–1963 to the development and adoption of OR outside the military and defence concerns. I show how the OR club formed a focus for industrial activity and the development of the subject. The early growth in education and training provision will also be traced to indicate its influence on the direction of OR and its acceptance as an academic discipline.
Energy Modeling for Policy Studies
Authors: Hogan William W.
Published: December 2003

Energy policy modeling owes a great debt to the disciplines of operations research. Valuable modeling tools were available when the energy crisis struck unexpectedly. In turn, the immediate response to problem-driven policy modeling produced methodological challenges and innovations that have application outside the domain of energy. The early days of the explosive growth of energy modeling for policy studies provide illustrations of the interaction of problem identification, model formulation, problem analysis, and policy implementation in the tradition of operations research.
Survival Analysis Methods for Personal Loan Data
Authors: Stepanova Maria , Thomas Lyn
Published: December 2003

Credit scoring is one of the most successful applications of quantitative analysis in business. This paper shows how using survival-analysis tools from reliability and maintenance modeling allows one to build credit-scoring models that assess aspects of profit as well as default. This survival-analysis approach is also finding favor in credit-risk modeling of bond prices. The paper looks at three extensions of Cox's proportional hazards model applied to personal loan data. A new way of coarse-classifying of characteristics using survival-analysis methods is proposed. Also, a number of diagnostic methods to check adequacy of the model fit are tested for suitability with loan data. Finally, including time-by-characteristic interactions is proposed as a way of possible improvement of the model's predictive power.
A Criterion for Burn-in that Balances Mean Residual Life and Residual Variance
Authors: Block Henry W. , Savits Thomas H. , Singh Harshinder
Published: December 2003

Optimum burn-in times have been determined for a variety of criteria such as mean residual life and conditional survival. In this paper we consider a residual coefficient of variation that balances mean residual life with residual variance. To study this quantity, we develop a general result concerning the preservation ofbathtub distributions. Using this result, we give a condition so that the residual coefficient of variation is bathtub-shaped. Furthermore, we show that it attains its optimum value at a time that occurs after the mean residual life function attains its optimum value, but not necessarily before the change point of the failure rate function.
Short-Term Generation Asset Valuation: A Real Options Approach
Authors: Tseng Chung-Li , Barz Graydon
Published: December 2003

This paper discusses using real options to value power plants with unit commitment constraints over a short-term period. We formulate the problem as a multistage stochastic problem and propose a solution procedure that integrates forward-moving Monte Carlo simulation with backward-moving dynamic programming. We assume that the power plant operator maximizes expected profit by deciding in each hour whether or not to run the unit, that a certain lead time for commitment and decommitment decisions is necessary to start up and shut down a unit, and that these commitment decisions, once made, are subject to physical constraints such as minimum uptime and downtime. We also account for the costs associated with starting up and shutting down a unit. Last, we assume that there are hourly markets for both electricity and the fuel used by the generator and that their prices follow Ito processes. Using numerical simulation, we show that failure to consider physical constraints may significantly overvalue a power plant.
Searching for an Agent Who May OR May Not Want to be Found
Authors: Alpern Steve , Gal Shmuel
Published: December 2003

There is an extensive theory regarding optimal continuous path search for a mobile or immobile “target.” The traditional theory assumes that the target is one of three types: (i) an object with a known distribution of paths, (ii) a mobile or immobile hider who wants to avoid or delay capture, or (iii) a rendezvouser who wants to find the searcher. This paper introduces a new type of search problem by assuming that aims of the target are not known to the searcher. The target may be either a type (iii) cooperator (with a known cooperation probability c) or a type (ii) evader. This formulation models search problems like that for a lost teenager who may be a “runaway,” or a lost intelligence agent who may be a defector. In any given search context, it produces a continuum of search problems τ(c), 0 ≤ c ≤ 1, linking a zero-sum search game (with c = 0) to a rendezvous problem (with c = 1). These models thus provide a theoretical bridge between two previously distinct parts of search theory, namely search games and rendezvous search.
Analysis of a Least Recently Used Cache Management Policy for Web Browsers
Authors: Mookerjee Vijay S. , Tan Yong
Published: December 2003

Experience shows that document caching by a web browser is a cheap and effective way to improve the performance of the World Wide Web. This study analyzes a LRU (Least Recently Used) policy for cache management in a web browser. In this policy, the cache is filled with documents based upon a document's “age,” defined as the time elapsed since the document was last accessed. The user's preference for a document is modeled as a general function that declines with the document's age. Two popular measures—the expected delay per document access, and the hit-ratio—are used to evaluate the LRU policy. Unlike many previous studies that evaluate caching policies using simulation methods, this study derives analytical expressions to evaluate performance. The study also presents an approximate, easy-to-compute method to evaluate performance. Numerical tests show this approximation to be extremely accurate. A variety of other numerical results are presented that help describe the behavior ofthe LRU policy under different situations (e.g., when the documents need to be updated periodically). We also compare the LRU policy with other caching policies (both static and dynamic) for small problems. Our comparison suggests that finding a good caching policy that is conscious of document size and delay may be difficult.
On the Relation Between Option and Stock Prices: A Convex Optimization Approach
Authors: Bertsimas Dimitris , Popescu Ioana
Published: December 2003

The idea of investigating the relation of option and stock prices based just on the no-arbitrage assumption, but without assuming any model for the underlying price dynamics, has a long history in the financial economics literature. We introduce convex and, in particular semidefinite optimization methods, duality, and complexity theory to shed new light on this relation. For the single stock problem, given moments of the prices of the underlying assets, we show that we can find best-possible bounds on option prices with general payoff functions efficiently, either algorithmically (solving a semidefinite optimization problem) or in closed form. Conversely, given observable option prices, we provide best-possible bounds on moments of the prices of the underlying assets, as well as on the prices of other options on the same asset by solving linear optimization problems. For options that are affected by multiple stocks either directly (the payoff of the option depends on multiple stocks) or indirectly (we have information on correlations between stock prices), we find nonoptimal bounds using convex optimization methods. However, we show that it is NP-hard to find best possible bounds in multiple dimensions. We extend our results to incorporate transactions costs.
Flexible Service Capacity: Optimal Investment and the Impact of Demand Correlation
Authors: Netessine Serguei , Dobson Gregory , Shumsky Robert A.
Published: December 2003

We consider a firm that provides multiple services using both specialized and flexible capacity. The problem is formulated as a two-stage, single-period stochastic program. The firm invests in capacity before the actual demand is known and optimally assigns capacity to customers when demand is realized. Sample applications include a car rental company's use of mid-sized cars to satisfy unexpectedly high demand for compact cars and an airline's use of business-class seats to satisfy economy-class demand. We obtain an analytical solution for a particular case, when services may be upgraded by one class. The simple form of the solution allows us to compare the optimal capacities explicitly with a solution that does not anticipate flexibility. Given that demand follows a multivariate normal distribution, we analytically characterize the effects of increasing demand correlation on the optimal solution. For the case with two customer classes, the effects of demand correlation are intuitive: Increasing correlation induces a shift from flexible to dedicated capacity. When there are three or more classes, there are also adjustments to the resources not directly affected by the correlation change. As correlation rises, these changes follow an alternating pattern (for example, if the optimal capacity of one resource rises, then the optimal capacity of the adjacent resource falls). These results make precise conjectures based on numerical experiments that have existed in the literature for some time.
An Inverse Problem of the Lanchester Square Law in Estimating Time-Dependent Attrition Coefficients
Authors: Chen Hsi-Mei
Published: December 2003

This paper considers the inverse problem of estimating time-varying attrition coefficients in Lanchester's square law with reinforcements, using observed data on some or all of the battle's strength histories and the reinforcement schedules. The method employed is a nonparametric extension of the parametric conjugate gradient method (P-CGM). We use hypothetical strength histories and reinforcement schedules that are known to be without error at several points in time to illustrate the method. However, the method has application in other circumstances. The problem of estimating the time-dependent attrition coefficients that best fit a set of given strength histories is inherently a nonparametric inverse problem. In this paper we cast it into a nonlinear optimization problem, and show how to solve it numerically by using a nonparametric conjugate gradient method (NP-CGM). Two numerical test cases are provided to illustrate the application of the method.
Double Auctions Across a Constrained Transmission Line
Authors: Singer Joel I.
Published: December 2003

Auctions are a common price-setting mechanism in many areas of the economy. Certain auctions, for example those in deregulated electric power networks, require that there exist sufficient capacity along the power lines connecting the buyers and the sellers. We investigate how auction participants modify their bidding strategies depending on the influence and behavior of a transmission line owner. We also investigate optimal strategic behavior when multiple buyers and sellers are separated by a possibly-constrained channel, and show that both sides’ strategies converge to truth-telling behavior as the number of market participants increases, and price-taking behavior also emerges as the number of participants increases. We show that limited transmission capacity increases participants’ misrepresentation and increases auction inefficiency, as players modify their bidding strategies in an attempt to increase their profit.
A Stochastic Convergence Model for Portfolio Selection
Authors: Puelz Amy V.
Published: December 2003

Portfolio selection techniques must provide decision makers with a dynamic model framework that incorporates realistic assumptions regarding financial markets, risk preferences, and required portfolio characteristics. Unfortunately, multistage stochastic programming (SP) models for portfolio selection very quickly become intractable as assumptions are relaxed and uncertainty is introduced. In this paper, I present an alternative model framework for portfolio selection, stochastic convergence (SC), that systematically incorporates uncertainty under a realistic assumption set. The optimal portfolio is derived through an iterative procedure, where portfolio plans are evaluated under many possible future scenarios then revised until the model converges to the optimal plan. This approach allows for scenario analysis over all stochastic components, requires no limitation on the structural form of the objective or constraints, and permits evaluation over any length planning horizon while maintaining model tractability by aggregating the scenario tree at each stage in the solution process. Through focused aggregation schemes, the SC approach allows for the implementation of a lower partial variance riskmetric, which is preferred in investment selection. In simulated tests, the SC model, with scenario aggregation, generated portfolios exhibiting performance similar to those generated using the SP model form with no aggregation. Empirical tests using historical fund returns show that a multiperiod SC decision strategy outperforms various benchmarkstrate gies over a long-term test horizon under both asset-liability matching and return maximization frameworks.
Using Supply Functions for Offering Generation into an Electricity Market
Authors: Anderson E. J. , Philpott A. B.
Published: December 2003

In this paper, we study strategies for generators making offers into electricity markets in circumstances where demand is unknown in advance. We concentrate on a model with smooth supply functions and derive conditions under which a single supply function can represent an optimal response to the offers of the other market participants over a range of demands. In order to apply this approach in practice, it may be necessary to approximate the supply functions of other players. We derive bounds on the loss in revenue that occurs in comparison with the exact supply function response, when a generator uses an approximation both for its own supply function and for the supply functions of other players. We also demonstrate the existence of symmetric supply-function equilibria.
Policy Model for Pollution Control in the Copper Industry, Including a Model for the Sulfuric Acid Market
Authors: Caldentey René , Mondschein Susana
Published: December 2003

In this paper we develop a policy model for pollution control investment and operational decisions in the copper industry. The system consists of (i) a nonlinear integer model to optimize smelter operations, including the investment decisions relating to smelting capacity and pollution control plants that complies with environmental regulations, and (ii) a network flow model to describe the economic behavior of the sulfuric acid market, which considers the sulfuric acid produced at the pollution abatement stages in the smelting process. This second model solves for an equilibrium among spatially separated markets, that determines the price and distribution of acid in each demand and supply region. The two models interact through the input each receives from the other. Thus, the smelter model uses the sulfuric acid price at each smelter to find optimal operational and investment decisions, whereas the sulfuric acid market model considers sulfuric acid output at the smelters as part of the supply input to find the price of this product at each smelter location. The solution given by the policy model is the global equilibrium obtained when this iterative process between the two models converges. Thus, the price of the sulfuric acid, which is the central component when deciding when and where to locate a sulfuric acid plant, is determined endogenously, rather than assumed exogenous as in most models of this type. Computational experiments show that expected profits associated with the copper industry can increase significantly when the problem is solved in aggregate, as compared with the smelters making their decisions independently. Several applications of the policy model are described.
Optimal Lot-Sizing/Vehicle-Dispatching Policies Under Stochastic Lead Times and Stepwise Fixed Costs
Authors: Alp Osman , Erkip Nesim K. , Güllü Refik
Published: December 2003

We characterize optimal policies of a dynamic lot-sizing/vehicle-dispatching problem under dynamic deterministic demands and stochastic lead times. An essential feature of the problem is the structure of the ordering cost, where a fixed cost is incurred every time a batch is initiated (or a vehicle is hired) regardless of the portion of the batch (or vehicle) utilized. Moreover, for every unit of demand not satisfied on time, holding and backorder costs are incurred. Under mild assumptions we show that the demand of a period is satisfied from at most three distinct production (dispatching) epochs. We devise a dynamic programming algorithm to compute the production/dispatching quantities and times.
Strategic Operations Research and the Edelman Prize Finalist Applications 1989–1998
Authors: Bell Peter C. , Anderson Chris K. , Kaiser Stephen P.
Published: December 2003

In an earlier study we examined the available evidence on the Edelman Prize finalist applications 1989–1998. This study concluded that 13 of the 42 private sector applications provide examples of strategic operations research (SOR) when SOR is defined as operations research that creates a sustainable competitive advantage. In a follow-up study we tested our classifications, gathering longitudinal information on the continued success of the Edelman applications. We contacted people who were familiar with all the private sector applications that were Edelman finalists 1989–1996 and had at least five years of history since the competition. We describe the post-Edelman history of these applications and use this data to reassess their strategic role. We found that the longitudinal data provides evidence to support our original classification, but also suggests that several additional applications were more strategic than was originally apparent. We conclude that almost 60% (20 of 34) of these applications created a sustainable competitive advantage for their firms and provide examples of SOR.
A New Approach to Estimating the Probability of Winning the Presidency
Authors: Kaplan Edward H. , Barnett Arnold
Published: December 2003

As the 2000 election so vividly showed, it is Electoral College standings rather than national popular votes that determine who becomes President. But current pre-election polls focus almost exclusively on the popular vote. Here we present a method by which pollsters can achieve both point estimates and margins of error for a presidential candidate's electoral-vote total. We use data from both the 2000 and 1988 elections to illustrate the approach. Moreover, we indicate that the sample sizes needed for reliable inferences are similar to those now used in popular-vote polling.
Auctions for Procuring Options
Authors: Schummer James , Vohra Rakesh V.
Published: December 2003

We examine the mechanism-design problem for a single buyer to procure purchase options for a homogeneous good when that buyer is required to satisfy an unknown future demand. Suppliers have two-dimensional types in the form of commitment costs and production costs. The efficient schedule of options depends on the distribution of demand. To implement an efficient outcome, we introduce a class of mechanisms which are essentially pivotal mechanisms (Vickrey-Clarke-Groves) with respect to the expected costs of the suppliers. We show that the computational task of running such mechanisms is not burdensome. Our discussion uses electricity markets as an example.
Wavelength Routing and Assignment in a Survivable WDM Mesh Network
Authors: Kennington Jeffery , Olinick Eli , Ortynski Augustyn , Spiride Gheorghe
Published: December 2003

All-optical networks with wavelength division multiplexing (WDM) capabilities are prime candidates for future wide-area backbone networks. The simplified processing and management of these very high bandwidth networks make them very attractive. A procedure for designing low cost WDM networks is the subject of this investigation.

In the literature, this design problem has been referred to as the routing and wavelength assignment problem. Our proposed solution involves a three-step process that results in a low-cost design to satisfy a set of static point-to-point demands. Our strategy simultaneously addresses the problem of routing working traffic, determining backup paths for single node or single link failures, and assigning wavelengths to both working and restoration paths.

An integer linear program is presented that formally defines the routing and wavelength assignment problem (RWA) being solved along with a simple heuristic procedure. In an empirical analysis, the heuristic procedure successfully solved realistically sized test cases in under 30 seconds on a Compaq AlphaStation. CPLEX 6.6.0 using default settings required over 1,000 times longer to obtain only slightly better solutions than those obtained by our new heuristic procedure.
A Mixed Complementarity Model of Hydrothermal Electricity Competition in the Western United States
Authors: Bushnell James
Published: December 2003

This paper presents a modeling framework for analyzing competition between multiple firms that each possess a mixture of hydroelectric and thermal generation resources. Based upon the concept of a Cournot oligopoly with a competitive fringe, the model characterizes the Cournot equilibrium conditions of a multiperiod hydrothermal scheduling problem. Using data from the western United States electricity market, this framework is implemented as a mixed linear complementarity model. The results show that some firms may find it profitable to allocate considerably more hydro production to off-peak periods then they would under perfect competition. This strategy is a marked contrast to the optimal hydroschedules that would arise if no firms were acting strategically. These results highlight the need to explicitly consider profit-maximizing behavior when examining the impact of regulatory and environmental policies on electricity market outcomes.
Flow Management to Optimize Retail Profits at Theme Parks
Authors: Rajaram Kumar , Ahmadi Reza
Published: December 2003

In many theme parks, stores are located within major attractions to sell related merchandise. Sales at such stores form a significant portion of theme park profits. Typically, store sales depend upon visitor flows through the attraction, customer satisfaction with the attraction, and the merchandise at the store. In addition, such stores constitute a unique retail environment, as visitor flows to attractions can be managed and stores are not competitors, but belong to the same parent company. This provides the opportunity to increase store sales by interfacing park operations, which manages visitor flows by setting schedules and capacity of attractions, with the store-level merchandising process, which determines which and how much product to order.

Motivated by a study at Universal Studios Hollywood (USH), we develop a flow management model to link park operations with store-level merchandising. This model sets the capacities and schedules of the major attractions to increase visitor flows to high-profit retail areas subject to visitor satisfaction, capacity, scheduling, and flow-balance constraints. In addition, this model serves as an important tool to generate and evaluate various strategies aimed at increasing theme park profitability at USH.
Order Fill Rate, Leadtime Variability, and Advance Demand Information in an Assemble-to-Order System
Authors: Lu Yingdong , Song Jing-Sheng , Yao David D.
Published: December 2003

We study an assemble-to-order system with stochastic leadtimes for component replenishment. There are multiple product types, of which orders arrive at the system following batch Poisson processes. Base-stock policies are used to control component inventories. We analyze the system as a set of queues driven by a common, multiclass batch Poisson input, and derive the joint queue-length distribution. The result leads to simple, closed-form expressions of the first two moments, in particular the covariances, which capture the dependence structure of the system. Based on the joint distribution and the moments, we derive easy-to-compute approximations and bounds for the order fulfillment performance measures. We also examine the impact of demand and leadtime variability, and investigate the value of advance demand information.
Minimization of the Number of Tool Magazine Setups on Automated Machines: A Lagrangean Decomposition Approach
Authors: Denizel Meltem
Published: December 2003

This paper addresses the parts-grouping problem that arises in automated manufacturing environments where appropriate cutting tools must be loaded on Computer Numerical Control (CNC) machines to process a variety of parts. Since tool-loading times may be considerably long and reduce available machine processing times, it is important to find a mutually exclusive grouping of parts such that the total number of tools required by each group does not exceed the tool-magazine capacity and the number of groups is minimized. We present an integer programming formulation of the problem and develop a lower bounding procedure using Lagrangean decomposition. We then introduce valid inequalities to improve the quality of the lower bounds obtained from the relaxed problem. Our solution procedure for the lower bounding problem requires only one set of Lagrange multipliers, which reduces the required computational effort significantly. We also modify the lower bound solution heuristically to find an upper bound. The lower and upper bounds are then incorporated in a branch-and-bound scheme to search for an optimal solution. Our computational comparisons with the best existing solution procedures from the literature show that our procedure performs better on average, and for the majority of test problems within the scope of our experiments.
Inventory Models with Fixed Costs, Forecast Updates, and Two Delivery Modes
Authors: Sethi Suresh P. , Yan Houmin , Zhang Hanqin
Published: December 2003

This paper is concerned with a periodic review inventory system with fast and slow delivery modes, fixed ordering cost, and regular demand forecast updates. At the beginning of each period, on-hand inventory and demand information are updated. At the same time, decisions on how much to order using fast and slow delivery modes are made. Fast and slow orders are delivered at the end of the current period and at the end of the next period, respectively. A forecast-update-dependent (s, S)-type policy is shown to be optimal. Also shown are some monotonicity properties of the policy parameters with respect to the costs and information updates.
Enterprise-Wide Optimization of Total Landed Cost at a Grocery Retailer
Authors: Erhun Feryal , Tayur Sridhar
Published: December 2003

We describe an enterprise-wide tool for tactical planning at a grocery retailer. The tool enables a “total landed cost” perspective by coordinating decisions across functions of the supply chain. It dynamically optimizes across logistics, purchasing, and warehouse management, while considering the necessary joint replenishment economies and accounting for a wide variety of complexities, such as discounts on total order quantity, intermittent demand, multiple distribution centers, vendor deals and forward buys, and promotions. The application combines appropriate operations research techniques to solve the problem; furthermore, it is created in the newly available information technology infrastructure. The entire application “sits above” and coordinates existing execution tools from commercial vendors by setting key operating targets and providing operational guidance.

Within weeks of a pilot, we observed a reduction in on-hand inventories, an increase in service levels, and substantial improvements in logistics decisions. The total landed cost is substantially lower—with an improvement of 20.8% of operating costs, or 11.6% of net profits—while providing superior fulfillment to the stores.
Programmatic Risk Analysis for Critical Engineering Systems Under Tight Resource Constraints
Authors: Dillon Robin L. , Paté-Cornell M. Elisabeth , Guikema Seth D.
Published: December 2003

Managers of complex engineering development projects face a challenge when deciding how to allocate scarce resources to minimize the risks of project failure. As resource constraints become tighter, balancing these failure risks is more critical, less intuitive, and can benefit from the power of quantitative analysis. This paper describes the Advanced Programmatic Risk Analysis and Management model (APRAM), a decision-support framework for the management of the risk of failures of dependent engineering projects within programs. Our goal is to guide the management of the design, the development, and the budget of dependent projects. Considering first a single project, our approach is to optimize the use of the budget reserves and of the funds dedicated to the system itself for each possible budget allocation. This phase involves separate optimizations of the system design and a strategy for resolving development problems based on a chosen objective function. The model also allows checking that specified thresholds of maximum acceptable risks are met, and if not, indicates how much is required to satisfy them. It is then extended to include project dependencies within a program. Finally, it allows checking that the level of resources available is appropriate by computing the shadow “risk cost” of the budget constraint. The NASA Jet Propulsion Laboratory has supported the development of this model, so each step of APRAM is illustrated by the schematic case of an unmanned space program involving two dependent projects. Also, where applicable, we discuss our experiences working with the APRAM concepts for the management of unmanned space missions.
Offer Stack Optimization in Electricity Pool Markets
Authors: Neame Philip J. , Philpott Andrew B. , Pritchard Geoffrey
Published: December 2003

We consider a generator making offers of energy into an electricity pool market. For a given time period, it must submit an offer stack, consisting of a fixed number of quantities of energy and prices at which it wants these quantities dispatched. We assume that the generator cannot offer enough power to substantially affect the market price, so the optimal response would be to offer energy at marginal cost. However, the market rules do not permit an arbitrary function, so the problem is to find an offer stack approximating marginal cost in a way that maximizes its profit. We give optimality conditions for this problem and derive an optimization procedure based on dynamic programming. This procedure is illustrated by applying it to several examples with different costs of production.