bluuebunny/crossref_metadata_2025 huggingface dataset:
A General Framework for the Study of Decentralized Distribution Systems
Authors: Anupindi Ravi , Bassok Yehuda , Zemel Eitan
Published: December 2003

We develop a general framework for the analysis of decentralized distribution systems. We carry the analysis in terms of a simplified model which entails N retailers who face stochastic demands and hold stocks locally and/or at one or more central locations. An exogenously specified fraction of any unsatisfied demand (demand greater than locally available stock) at a retailer could be satisfied using excess stocks at other retailers and/or stocks held at a central location. We consider inventory ordering and allocation decisions. The operational decisions of inventory and allocation of stocks and the financial decision of allocation of revenues/costs must be made in a way consistent with the individual incentives of the various independent retailers. We develop a “coopetitive” framework for the sequential decisions of inventory and allocation. We introduce the notion of claims that allows us to separate the ownership (with decision rights) and the location of inventories in the system. For the cooperative shipping and allocation decision, we use the concept of core and develop sufficient conditions for the existence of the core. For the inventory decision, we develop conditions for the existence of a pure strategy Nash Equilibrium. For this decentralized system, we show that there exists an allocation mechanism that achieves the first-best solution for inventory deployment and allocation. We develop conditions under which the first-best equilibrium will be unique. Our model can be easily generalized to include complicated ownership structures such as “super dealers,” partnerships, “inventory speculators,” and situations in retail e-commerce settings such as “click-through arrangements,” separation of “demand generators,” and “fulfillment houses,” etc. It can also be applied to situations involving capacity allocations and product substitutions.
Heuristic Methods for Centralized Control of One-Warehouse, N-Retailer Inventory Systems
Authors: Axsäter Sven , Marklund Johan , Silver Edward A.
Published: December 2003

This paper considers a periodic-review, two-echelon inventory system with one central warehouse and several retailers facing stochastic demand. The retailers replenish their stock from the warehouse, which in turn places orders at an outside supplier with infinite capacity. Transportation times and costs are constant. No ordering costs are considered, but warehouse replenishments must be multiples of a given batch quantity. The objective is to find policies that minimize holding and backorder costs. The standard approach to approximately solve this problem is to use a “balance” assumption, meaning that negative stock allocations to the retailers are possible. This approach may lead to considerable errors for problems with large differences between the retailers in terms of service requirements and demand characteristics. To handle such situations we suggest and evaluate two computationally tractable heuristics: the Virtual Assignment ordering rule for warehouse replenishments and the Two-step Allocation rule for allocating stock from the warehouse to the retailers. Numerical evidence shows that, especially when combining these heuristics, we obtain considerable improvements for many problems over the standard approach. Savings of up to 50% have been recorded.
On the Complementary Value of Accurate Demand Information and Production and Supplier Flexibility
Authors: Milner Joseph M. , Kouvelis Panos
Published: December 2003

We study the value of information, production flexibility, and supplier flexibility for a good for which an initial and a subsequent order may be placed. We consider a Bayesian model of demand in which the unknown mean demand rate is assumed to have a prior, which is a mixture of two normal distributions corresponding to the demand forecast for an innovative (fashion) good. We develop three models of production flexibility: a static model requiring initial placement of both orders, a partially dynamic model requiring a fixing of the time that the second order will be made, and a fully dynamic model with no restrictions on ordering. Supplier flexibility is modeled through supply lead times. We observe that the magnitude of the savings from the static to the fully flexible model, corresponding to the sum of the values of information and production flexibility, reflects all sources of variability: differences between demand means of the prior mixture, variability within each prior, and variability about the observed mean. We observe that as the difference between high and low demand cases increases, the value of information increases, though for long lead times, production flexibility is required to take advantage of the updated information. Further, we observe that the greater the uncertainty within each prior distribution, the greater the value of information relative to the value of production flexibility, particularly for long lead times. However, the greater the uncertainty around the mean demand, which is the uncertainty that cannot be resolved through observation, the lower the value of information. Finally, we observe that the value of supply flexibility grows initially in a concave then convex manner as a function of the supply lead times.
Analysis of a Decentralized Production-Inventory System
Authors: Caldentey René , Wein Lawrence M.
Published: December 2003

We model an isolated portion of a competitive supply chain as a M/M/1 make-to-stock queue. The retailer carries finished goods inventory to service a Poisson demand process, and specifies a policy for replenishing his inventory from an upstream supplier. The supplier chooses the service rate, i.e., the capacity of his manufacturing facility, which behaves as a single-server queue with exponential service times. Demand is backlogged and both agents share the backorder cost. In addition, a linear inventory holding cost is charged to the retailer, and a linear cost for building production capacity is incurred by the supplier. The inventory level, demand rate, and cost parameters are common knowledge to both agents. Under the continuous-state approximation where the M/M/1 queue has an exponential rather than geometric steady-state distribution, we characterize the optimal centralized and Nash solutions, and show that a contract with linear transfer payments replicates a cost-sharing agreement and coordinates the system. We also compare the total system costs, the agents' decision variables, and the customer service levels of the centralized versus Nash versus Stackelberg solutions.
Telephone Call Centers: Tutorial, Review, and Research Prospects
Authors: Gans Noah , Koole Ger , Mandelbaum Avishai
Published: December 2003

Telephone call centers are an integral part of many businesses, and their economic role is significant and growing. They are also fascinating sociotechnical systems in which the behavior of customers and employees is closely intertwined with physical performance measures. In these environments traditional operational models are of great value—and at the same time fundamentally limited—in their ability to characterize system performance.

We review the state of research on telephone call centers. We begin with a tutorial on how call centers function and proceed to survey academic research devoted to the management of their operations. We then outline important problems that have not been addressed and identify promising directions for future research.
An Overview of Pricing Models for Revenue Management
Authors: Bitran Gabriel , Caldentey René
Published: December 2003

In this paper, we examine the research and results of dynamic pricing policies and their relation to revenue management. The survey is based on a generic revenue management problem in which a perishable and nonrenewable set of resources satisfy stochastic price sensitive demand processes over a finite period of time. In this class of problems, the owner (or the seller) of these resources uses them to produce and offer a menu of final products to the end customers. Within this context, we formulate the stochastic control problem of capacity that the seller faces: How to dynamically set the menu and the quantity of products and their corresponding prices to maximize the total revenue over the selling horizon.
Scheduling with Fixed Delivery Dates
Authors: Hall Nicholas G. , Lesaoana 'Maseka , Potts Chris N.
Published: December 2003

In most classical scheduling models, it is assumed that a job is dispatched to a customer immediately after its processing completes. In many practical situations, however, a set of delivery dates may be fixed before any jobs are processed. This is particularly relevant where delivery is an expensive or complicated operation, for example, as with heavy machinery. A similar situation arises where customers find deliveries disruptive and thus require them to be made within a limited time interval that repeats periodically. A third possibility is that a periodic business function, for example, the supplier's billing cycle, effectively defines a delivery date, and includes all jobs that have been completed since the previous billing cycle. These situations are not adequately represented by classical scheduling models. We consider a variety of deterministic scheduling problems in which a job is dispatched to a customer at the earliest fixed delivery date that is no earlier than the completion time of its processing. Problems where the number of delivery dates is constant, and others where it is specified as part of data input, are studied. For almost all problems considered, we either provide an efficient algorithm or establish that such an algorithm is unlikely to exist. By doing so, we permit comparisons between the solvability of these fixed delivery date problems and of the corresponding classical scheduling problems.
Reducing Delay in Preemptive Repeat Priority Queues
Authors: Drekic Steve , Stanford David A.
Published: December 2003

The classical model of the preemptive repeat priority queue assumes that there is a single distribution from which service times for a given class are selected, regardless of the number of preemptions. This paper presents three alternatives for improving service progressively to preempted customers: (1) changing the service distribution, (2) preventing further preemptions, and (3) promoting customers to the next higher priority class. The Laplace-Stieltjes transform of the flow time distribution is found for each class in a model that can employ these three alternatives in arbitrary combinations.
Exact Evaluation of Batch-Ordering Inventory Policies in Two-Echelon Supply Chains with Periodic Review
Authors: Cachon Gérard P.
Published: December 2003

This paper studies a two-echelon supply chain with stochastic and discrete consumer demand, batch order quantities, periodic inventory review, and deterministic transportation times. Reorder point policies manage inventories at every location. Average inventory, backorders and fill rates are evaluated exactly for each location. Safety stock is evaluated exactly at the lower echelon and a good approximation is detailed for the upper echelon. Numerical data are presented to demonstrate the model's utility. It is found that system costs generally increase substantially if the upper echelon is restricted to carry no inventory, of if the upper echelon is required to provide a high fill rate. In many cases it is optimal to set the upper echelon's reorder point to yield near zero safety stock, yet in some cases this simple heuristic can significantly increase supply chain operating costs. Finally, policies selected under the assumption of continuous inventory review can perform poorly if implemented in an environment with periodic review.
Octane: A New Heuristic for Pure 0–1 Programs
Authors: Balas Egon , Ceria Sebastián , Dawande Milind , Margot Francois , Pataki Gábor
Published: December 2003

We propose a new heuristic for pure 0–1 programs, which finds feasible integer points by enumerating extended facets of the octahedron, the outer polar of the unit hypercube. We give efficient algorithms to carry out the enumeration, and we explain how our heuristic can be embedded in a branch-and-cut framework. Finally, we present computational results on a set of pure 0–1 programs taken from MIPLIB and other sources.
Solving Large Nonconvex Water Resources Management Models Using Generalized Benders Decomposition
Authors: Cai Ximing , McKinney Daene C. , Lasdon Leon S. , Watkins David W.
Published: December 2003

Nonconvex nonlinear programming (NLP) problems arise frequently in water resources management, e.g., reservoir operations, groundwater remediation, and integrated water quantity and quality management. Such problems are usually large and sparse. Existing software for global optimization cannot cope with problems of this size, while current local sparse NLP solvers, e.g., MINOS (Murtagh and Saunders 1987), or CONOPT (Drud 1994) cannot guarantee a global solution. In this paper, we apply the Generalized Benders Decomposition (GBD) algorithm to two large nonconvex water resources models involving reservoir operations and water allocation in a river basin, using an approximation to the GBD cuts proposed by Floudas et al. (1989) and Floudas (1995). To ensure feasibility of the GBD subproblem, we relax its constraints by introducing elastic slack variables, penalizing these slacks in the objective function. This approach leads to solutions with excellent objective values in run times much less than the GAMS NLP solvers MINOS5 and CONOPT2, if the complicating variables are carefully selected. Using these solutions as initial points for MINOS5 or CONOPT2 often leads to further improvements.
Grade Selection and Blending to Optimize Cost and Quality
Authors: Karmarkar Uday S. , Rajaram Kumar
Published: December 2003

In many chemical process applications, a large mix of products is produced by blending them from a much smaller set of basic grades. The basic grades themselves are typically produced on the same process equipment and inventoried in batches. Decisions that arise in this process include selecting the set of basic grades, determining how much of each basic grade to produce, and how to blend basic grades to meet final product demand. We model this problem as a nonlinear mixed-integer program, which minimizes total grade inclusion, batching, blending, and quality costs subject to meeting quality and demand constraints for these products. Heuristics and lower bounds are developed and tested. The methods are applied to data from Europe's leading manufacturer of wheat- and starch-based products. Our results suggest that this model could potentially reduce annual costs by a minimum of 7%, translates to annual savings of around $5 million.
Performance Evaluation in Stochastic Environments Using Mean-Variance Data Envelopment Analysis
Authors: Post Thierry
Published: December 2003

Traditional Data Envelope Analysis (DEA) neglects uncertainty for the input-output variables by treating the observations as if they were the true input-output variables to select reference units for efficiency estimation and performance benchmarking. In stochastic environments, the traditional framework may include stochastically dominated reference units and exclude stochastically undominated ones. To incorporate uncertainty for the input-output variables in DEA, we propose a mean-variance framework derived from the theory of stochastic dominance. From that framework an extension to the traditional model is derived that prevents the selection of stochastically dominated reference units. In addition, within the mean-variance approach, variance restrictions can be specified that reduce the uncertainty for the performance of the evaluated unit relative to its reference unit.
Dynamic Economic Lot Size Models with Period-Pair-Dependent Backorder and Inventory Costs
Authors: Hsu Vernon Ning , Lowe Timothy J.
Published: December 2003

Inventory and backorder cost functions in the classical Wagner-Whitin economic lot size (ELS) models are typically period-pair-independent (pp-independent) in the sense that inventoried units carried (or backorders in existence) in a given period are treated the same regardless of the periods in which they are produced (placed) or the periods in which they are used (filled). We consider versions of the problem where inventory and backorder costs are pp-dependent, as well as versions where backorder costs, but not inventory costs, are pp-dependent. Recognizing that the problems considered are NP-hard, we provide cases where the cost structure allows polynomial solvability via dynamic programming.
Reconsidering the Philosophical Basis of OR/MS
Authors: Meredith Jack R.
Published: December 2003

Many in Operations Research/Management Science (OR/MS) have long predicted a major contraction in the field. Given the recent trends in OR/MS hiring, this contraction may have finally arrived, both in academia, as well as in industry. This study maintains that part of this contraction is because we drifted from the field's broad, real-world roots due to a limited philosophical foundation of the field, our realist view of reality. If our commonly held realist philosophy has, in the ironic fashion described herein, given rise to the “academic drift” in the field, the recognition of a relativist philosophy that emphasizes understanding over problem solving could help return the field to its roots.
Aggregation and Mixed Integer Rounding to Solve MIPs
Authors: Marchand Hugues , Wolsey Laurence A.
Published: December 2003

In this paper, we discuss the use of mixed integer rounding (MIR) inequalities to solve mixed integer programs. MIR inequalities are essentially Gomory mixed integer cuts. However, as we wish to use problem structure, we insist that MIR inequalities be generated from constraints or simple aggregations of constraints of the original problem. This idea is motivated by the observation that several strong valid inequalities based on specific problem structure can be derived as MIR inequalities.

Here we present and test a separation routine for such MIR inequalities that includes a heuristic row aggregation procedure to generate a single knapsack plus continuous variables constraint, complementation of variables, and finally the generation of an MIR inequality. Inserted in a branch-and-cut system, the results suggest that such a routine is a useful additional tool for tackling a variety of mixed integer programming problems.
Hedging Derivative Securities and Incomplete Markets: An ε-Arbitrage Approach
Authors: Bertsimas Dimitris , Kogan Leonid , Lo Andrew W.
Published: December 2003

Given a European derivative security with an arbitrary payoff function and a corresponding set of underlying securities on which the derivative security is based, we solve the optimal-replication problem: Find a self-financing dynamic portfolio strategy—involving only the underlying securities—that most closely approximates the payoff function at maturity. By applying stochastic dynamic programming to the minimization of a mean-squared error loss function under Markov-state dynamics, we derive recursive expressions for the optimal-replication strategy that are readily implemented in practice. The approximation error or “ε” of the optimal-replication strategy is also given recursively and may be used to quantify the “degree” of market incompleteness. To investigate the practical significance of these ε-arbitrage strategies, we consider several numerical examples, including path-dependent options and options on assets with stochastic volatility and jumps.
Improved Dynamic Programming Methods for Optimal Control of Lumped-Parameter Stochastic Systems
Authors: Philbrick C. Russell , Kitanidis Peter K.
Published: December 2003

New dynamic programming methods are developed to solve stochastic control problems with a larger number of state variables than previously possible. These methods apply accurate interpolation to numerical approximation of continuous cost-to-go functions, greatly reducing the number of discrete states that must be evaluated. By efficiently incorporating information on first and second derivatives, the approximation reduces computational effort by several orders of magnitude over traditional methods. Consequently, it is practical to apply dynamic programming to complex stochastic problems with a larger number of state variables than traditionally possible. Results are presented for hypothetical reservoir control problems with up to seven state variables and two random inputs.
A Class of Label-Correcting Methods for the K Shortest Paths Problem
Authors: Guerriero Francesca , Musmanno Roberto , Lacagnina Valerio , Pecorella Antonio
Published: December 2003

In this paper we deal with the problem of finding the first K shortest paths from a single origin node to all other nodes of a directed graph. In particular, we define the necessary and sufficient conditions for a set of distance label vectors, on the basis of which we propose a class of methods which can be viewed as an extension of the generic label-correcting method for solving the classical single-origin all-destinations shortest path problem. The data structure used is characterized by a set of K lists of candidate nodes, and the proposed methods differ in the strategy used to select the node to be extracted at each iteration. The computational results show that: 1. some label-correcting methods are generally much faster than the double sweep method of Shier (1979); 2. the most efficient node selection strategies, used for solving the classical single-origin all-destinations shortest path problem, have proved to be effective also in the case of the K shortest paths.
Pathwise Properties and Performance Bounds for a Perishable Inventory System
Authors: Cooper William L.
Published: December 2003

We study a perishable inventory system under a fixed-critical number order policy. By using an appropriate transformation of the state vector, we derive several key sample-path relations. We obtain bounds on the limiting distribution of the number of outdates in a period, and we derive families of upper and lower bounds for the long-run number of outdates per unit time. Analysis of the bounds on the expected number of outdates shows that at least one of the new lower bounds is always greater than or equal to previously published lower bounds, whereas the new upper bounds are sometimes lower than and sometimes higher than the existing upper bounds. In addition, using an expected cost criterion, we compare optimal policies and different choices of critical-number policies.
Multistage Lot Sizing Problems via Randomized Rounding
Authors: Teo Chung-Piaw , Bertsimas Dimitris
Published: December 2003

We study the classical multistage lot sizing problem that arises in distribution and inventory systems. A celebrated result in this area is the 94% and 98% approximation guarantee provided by power-of-two policies. In this paper, we propose a simple randomized rounding algorithm to establish these performance bounds. We use this new technique to extend several results for the capacitated lot sizing problems to the case with submodular ordering cost. For the joint replenishment problem under a fixed base period model, we construct a 95.8% approximation algorithm to the (possibly dynamic) optimal lot sizing policy. The policies constructed are stationary but not necessarily of the power-of-two type. This shows that for the fixed based planning model, the class of stationary policies is within 95.8% of the optimum, improving on the previously best known 94% approximation guarantee.
An Economic Model for Evaluating Mining and Manufacturing Ventures with Output Yield Uncertainty
Authors: Kamrad Bardia , Ernst Ricardo
Published: December 2003

This paper develops an operational risk management model for evaluating production efforts in manufacturing and mining industries where the resource to be exploited is nonhomogenous. Using a contingent claims methodology now commonly encountered in financial applications, we formulate a production control model in an environment characterized by market and process uncertainty. In our analysis, market risk is depicted by the output price while process uncertainty is captured by the random variability inherent in the output's yield. In this light, adjustments to the rate of production are viewed as a sequence of (nested) real options affording operating flexibility. We account for an optimal sequence of production adjustments, over a preestablished production horizon, by taking the production rate as an adapted positive real-valued process. Accordingly, techniques of stochastic control theory and contingent claims analysis (CCA) are employed to ensure value maximizing production policies are rendered in a manner consistent with an equilibrium price structure.
Dynamic Control of a Queue with Adjustable Service Rate
Authors: George Jennifer M. , Harrison J. Michael
Published: December 2003

We consider a single-server queue with Poisson arrivals, where holding costs are continuously incurred as a nondecreasing function of the queue length. The queue length evolves as a birth-and-death process with constant arrival rate λ = 1 and with state-dependent service rates μn that can be chosen from a fixed subset A of [0, ∞). Finally, there is a nondecreasing cost-of-effort function c(·) on A, and service costs are incurred at rate c(μn) when the queue length is n. The objective is to minimize average cost per time unit over an infinite planning horizon. The standard optimality equation of average-cost dynamic programming allows one to write out the optimal service rates in terms of the minimum achievable average cost ζ*. Here we present a method for computing ζ* that is so fast and so transparent it may be reasonably described as an explicit solution for the problem of service rate control. The optimal service rates are nondecreasing as a function of queue length and are bounded if the holding cost function is bounded. From a managerial standpoint it is natural to compare ζ*, the minimum average cost achievable with state-dependent service rates, against the minimum average cost achievable with a single fixed service rate. The difference between those two minima represents the economic value of a responsive service mechanism, and numerical examples are presented that show it can be substantial.
Input Distribution Selection for Simulation Experiments: Accounting for Input Uncertainty
Authors: Chick Stephen E.
Published: December 2003

A number of authors have identified problematic issues with techniques used in current simulation practice for selecting probability distributions and their parameters for input to stochastic simulations. A major goal of this paper is to address some of those issues by presenting a self-consistent evaluation of the uncertainty about the mean value of the simulation output, when there is uncertainty in both the parameters and functional form of input distributions (structural uncertainty), and uncertainty due to the stochastic nature of simulation output (stochastic uncertainty), as is common in simulation practice. The analysis leads to an algorithm for randomly sampling input distributions and parameters before each simulation replication, using a Bayesian posterior distribution for input distributions and parameters, given historical data. Mechanisms for addressing issues of importance to the discrete-event simulation community are illustrated by example, such as the specification of prior distributions, and analysis for shifted distributions.
Effective Sequencing Rules for Closed Manufacturing Networks
Authors: Gilland Wendell G.
Published: December 2003

This paper develops a method for determining sequencing policies to effectively control a multistation closed queueing network. We assume that several job classes, with different service time distributions, share each server and should be sequenced to maximize the long-run throughput rate of the system. A Brownian control problem that approximates the original queueing network is formulated and used to develop a dynamic sequencing policy that seeks to prevent idleness, unless the system is at a face of the workload imbalance polytope that arises in the Brownian formulation. Several examples are used to demonstrate the benefit of this policy over the static prioritization proposed by Chevalier and Wein (1993), which has previously been shown to dominate traditional scheduling policies in a closed network setting.
High-Performance Computing for Asset-Liability Management
Authors: Gondzio Jacek , Kouwenberg Roy
Published: December 2003

Financial institutions require sophisticated tools for risk management. For companywide risk management, both sides of the balance sheet should be considered, resulting in an integrated asset-liability management approach. Stochastic programming models suit these needs well and have already been applied in the field of asset-liability management to improve financial operations and risk management. The dynamic aspect of the financial planning problems inevitably leads to multiple decision stages (trading dates) in the stochastic program and results in an explosion of dimensionality. In this paper we show that dedicated model generation, specialized solution techniques based on decomposition and high-performance computing, are the essential elements to tackle these large-scale financial planning problems. It turns out that memory management is a major bottleneck when solving very large problems, given an efficient solution approach and a parallel computing facility. We report on the solution of an asset-liability management model for an actual Dutch pension fund with 4,826,809 scenarios; 12,469,250 constraints; and 24,938,502 variables; which is the largest stochastic linear program ever solved. A closer look at the optimal decisions reveals that the initial asset mix is more stable for larger models, demonstrating the potential benefits of the high-performance computing approach for ALM.
Simple Procedures for Selecting the Best Simulated System When the Number of Alternatives is Large
Authors: Nelson Barry L. , Swann Julie , Goldsman David , Song Wheyming
Published: December 2003

In this paper, we address the problem of finding the simulated system with the best (maximum or minimum) expected performance when the number of alternatives is finite, but large enough that ranking-and-selection (R&S) procedures may require too much computation to be practical. Our approach is to use the data provided by the first stage of sampling in an R&S procedure to screen out alternatives that are not competitive, and thereby avoid the (typically much larger) second-stage sample for these systems. Our procedures represent a compromise between standard R&S procedures—which are easy to implement, but can be computationally inefficient—and fully sequential procedures—which can be statistically efficient, but are more difficult to implement and depend on more restrictive assumptions. We present a general theory for constructing combined screening and indifference-zone selection procedures, several specific procedures and a portion of an extensive empirical evaluation.
Navy Operations Research
Authors: Hughes Wayne P.
Published: December 2003

This paper emphasizes OR's utility to the U.S. Navy, as seen by its customers. Like many naval officers who subspecialized in operations research, the author was both producer and consumer of analysis toward improving fleet operations, Pentagon planning, and training effectiveness. Many of OR's unnoticed heroes are officers and Navy civilians who, then and now, could put operations analysis to best practical use. The paper reaches three conclusions, which (briefly) are: (1) The U.S. Navy could shift much analytical talent to improve fleet readiness and scarcely notice a loss of quality in Washington, (2) the benefit of Navy OR in the Pentagon was not so much in formal decision making as it was in educating a stream of future leaders about the state of the Navy and cost-constrained possible future states, and (3) the distinguishing contribution of all OR has been and still is in helping executives make better, timely decisions by applying our special art of quantitative analysis, and only incidentally in the fidelity or complexity of the models and other tools we employ.
Philip M. Morse and the Beginnings
Authors: Little John D. C.
Published: December 2003

Morse was the many-sided founding father of operations research in the United States. Following his pioneering wartime effort, he vigorously promoted the nonmilitary development of the field. A glimpse into his activities and accomplishments helps explain the vitality and high intellectual standards of the field.
Efficient Portfolios, Sparse Matrices, and Entities: A Retrospective
Authors: Markowitz Harry M.
Published: December 2003

In 1989 I was pleased and honored to be awarded the ORSA/TIMS (now INFORMS) John von Neumann Theory Prize for my work in portfolio theory, sparse matrices, and SIMSCRIPT. The following is a retrospective on my work in these fields.
The First Linear-Programming Shoppe
Authors: Gass Saul I.
Published: December 2003

We review the early history of linear programming with respect to the solution of linear equations, computer developments, and its origins within the federal government.
Scheduling Solutions for the Paper Industry
Authors: Keskinocak Pinar , Wu Frederick , Goodwin Richard , Murthy Sesh , Akkiraju Rama , Kumaran Santhosh , Derebail Annap
Published: December 2003

This paper describes a decision support system for paper production scheduling. This is the first system to provide an integrated solution to paper production scheduling and to consider interactions between different stages of the manufacturing and distribution process. Using a multicriteria optimization approach, the system generates multiple enterprisewide schedules to reveal tradeoffs between the multiple, often competing, objectives. The large portfolio of algorithms used by the system is embedded in an agent-based decision support framework, called Asynchronous Team (A-Team). Successful implementations of the system in several paper mills in North America have resulted in significant savings and improved customer satisfaction.
Order Allocation for Stock Cutting in the Paper Industry
Authors: Menon Syam , Schrage Linus
Published: December 2003

A common problem encountered in paper-production facilities is that of allocating customer orders to machines so as to minimize the total cost of production. It can be formulated as a dual-angular integer program, with identical machines inducing symmetry. While the potential advantages of decomposing large mathematical programs into smaller subproblems have long been recognized, the solution of decomposable integer programs remains extremely difficult. Symmetry intensifies the difficulty. This paper develops an approach, based on the construction of tight subproblem bounds, to solve decomposable dual-angular integer programs and successfully applies it to solve the problem from the paper industry. This method is of particular interest as it significantly reduces the impact of symmetry.
Design of Capacitated Multicommodity Networks with Multiple Facilities
Authors: Agarwal Yogesh K.
Published: December 2003

This paper addresses the problem of designing a multicommodity network using several facilities with different costs and capacities. The problem is addressed in a special context of designing private telecommunications networks using Fractional-T1 services. The algorithm starts from any given solution of the problem and gradually improves it by solving a series of subproblems, arriving at a local minimum. The subproblem is defined over a subset of links, called the subnetwork, by using one of the links as the base link. It is shown that the subproblem can be formulated as a multiple choice knapsack problem that is solved by dynamic programming. Computational results and lower bounds are reported on problems of up to 20 nodes and up to 3 facilities. On most problems, the algorithm produces solutions within about 5% of lower bound on the average. Although it was not possible to compute lower bounds for larger problems, heuristic solutions and running times are reported for problems of up to 99 nodes and four facilities.
An Integer L-Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands
Authors: Laporte Gilbert , Louveaux François V. , van Hamme Luc
Published: December 2003

The classical Vehicle Routing Problem consists ofdetermining optimal routes for m identical vehicles, starting and leaving at the depot, such that every customer is visited exactly once. In the capacitated version (CVRP) the total demand collected along a route cannot exceed the vehicle capacity. This article considers the situation where some ofthe demands are stochastic. This implies that the level of demand at each customer is not known before arriving at the customer. In some cases, the vehicle may thus be unable to load the customer's demand, even ifthe expected demand along the route does not exceed the vehicle capacity. Such a situation is referred to as a failure. The capacitated vehicle routing problem with stochastic demands (SVRP) then consists ofminimizing the total cost ofthe planned routes and of expected failures. Here, penalties for failures correspond to return trips to the depot. The vehicle first returns to the depot to unload, then resumes its trip as originally planned. This article studies an implementation of the Integer L-shaped method for the exact solution of the SVRP. It develops new lower bounds on the expected penalty for failures. In addition, it provides variants of the optimality cuts for the SVRP that also hold at fractional solutions. Numerical experiments indicate that some instances involving up to 100 customers and few vehicles can be solved to optimality within a relatively short computing time.
Optimal Lot Sizes with Geometric Production Yield and Rigid Demand
Authors: Anily Shoshana , Beja Avraham , Mendel Amit
Published: December 2003

A job shop has to deliver a given number of custom-order items. Production is performed in “lots” that require costly setup, and output quality is stochastic. The size of each lot must be set before output quality is observed. We study production processes whose yield is distributed according to a generalized truncated geometric distribution: Production can randomly go “out of control,” in which case all subsequent output of that lot is defective. The “generalization” allows both hazard rates and marginal production costs to vary as production progresses. Our results characterize the optimal lot sizes. In particular, we show that for small demands the optimal lot size equals the outstanding demand, and for larger demands it is less than the outstanding demand, with all lot sizes being uniformly bounded. For sufficiently large demands, we identify conditions under which the optimal lots are precisely those that minimize the ratio of production cost to the expected number of good items. A tighter characterization is given for the standard case, where hazard rates and marginal costs are constant.
Large-Scale Integer Programs in Image Analysis
Authors: Dahl Geir , Storvik Geir , Fadnes Alice
Published: December 2003

An important problem in image analysis is to segment an image into regions with different class labels. This is relevant in applications in medicine and cartography. In a proper statistical framework this problem may be viewed as a discrete optimization problem. We present two integer linear programming formulations of the problem and study some properties of these models and associated polytopes. Different algorithms for solving these problems are suggested and compared on some realistic data. In particular, a Lagrangian algorithm is shown to have a very promising performance. The algorithm is based on the technique of cost splitting and uses the fact that certain relaxed problems may be solved as shortest path problems.
Production and Inventory Model Using Net Present Value
Authors: Sun Daning , Queyranne Maurice
Published: December 2003

Using the net present value is the standard methodology in theoretical analysis, and the most frequently used method for making financial decisions. However, net present value is rarely used in production and inventory decisions. The main reasons appear to be the complexity of the formulae and the robustness of the EOQ model. We investigate the general multiproduct, multistage production and inventory model using the net present value of its total cost as the objective function. A power-of-two heuristic gives us a near optimal solution to this problem. If the base period is fixed (or varied), the solution based on the best power-of-two heuristic will be within 6.2% (or 2.1% ) of the optimal. This result is surprisingly similar to models using the long-term average cost. The average cost does not reflect the time value of money. Does this mean that decisions based on average cost are significantly inferior to those based on net present value? The answer is quite surprising. If we include discounted production cost in the holding cost, it turns out that the decision based on average cost is only 9.6% (in terms of the net present value of the total cost) worse than the decision based on the net present value. However, the reorder interval based on the average cost could be much longer than that derived using net present value. This result shows that average cost is a good approximation to the net present value when the demands are deterministic.
On the Tail of the Waiting Time in a Markov-Modulated M/G/1 Queue
Authors: Asmussen Søren , O'cinneide Colm
Published: December 2003

We show that the “exponential decay parameter” of the waiting time in a Markov-modulated M/G/1 queue is no larger than that of the corresponding M/G/1 queue with “averaged” parameters, and we give a necessary and sufficient condition for equality. We also explore the effect of speeding up the modulation process. A key tool is a Markov-modulated fluid model.
Dynamic Airline Revenue Management with Multiple Semi-Markov Demand
Authors: Brumelle Shelby , Walczak Darius
Published: December 2003

When a customer requests a discount fare, the airline must decide whether to sell the seat at the requested discount or to hold the seat in hope that a customer will arrive later who will pay more. We model this situation for a single-leg flight with multiple fare classes and customers who arrive according to a semi-Markov process (possibly nonhomogeneous). These customers can request multiple seats (batch requests) and can be overbooked. Under certain conditions, we show that the value function decreases as departure approaches. If each customer only requests a single seat or if the requests can be partially satisfied, then we show that there are optimal booking curves which decrease as departure approaches. We also provide counterexamples to show that this structural property of the optimal policy need not hold for more general arrival processes if the requests can be for more than one seat and must be accepted or rejected as a whole.
Optimal Exercise Policies and Simulation-Based Valuation for American-Asian Options
Authors: Wu Rongwen , Fu Michael C.
Published: December 2003

American-Asian options are average-price options that allow early exercise. In this paper, we derive structural properties for the optimal exercise policy, which are then used to develop an efficient numerical algorithm for pricing such options. In particular, we show that the optimal policy is a threshold policy: The option should be exercised as soon as the average asset price reaches a characterized threshold, which can be written as a function of the asset price at that time. By exploiting this and other structural properties, we are able to parameterize the exercise boundary, and derive gradient estimators for the option payoff with respect to the parameters of the model. These estimators are then incorporated into a simulation-based algorithm to price American-Asian options. Computational experiments carried out indicate that the algorithm is very competitive with other recently proposed numerical algorithms.
A Time-Series Framework for Supply-Chain Inventory Management
Authors: Aviv Yossi
Published: December 2003

We consider a supply chain in which the underlying demand process can be described in a linear state space form. Inventory is managed at various points of the chain (members), based on local information that each member observes and continuously updates. The key feature of our model is that it takes into account the ability of the members to observe subsets of the underlying state vector, and adopt their forecasting and replenishment policies accordingly. This enables us to model situations in which the members are privy to certain explanatory variables of the demand, with the latter possibly evolving according to a vector autoregressive time series. For each member, we identify an associated demand evolution model, for which we propose an adaptive inventory replenishment policy that utilizes the Kalman filter technique. We then provide a simple methodology for assessing the benefits of various types of information-sharing agreements between members of the supply chain. We also discuss inventory positioning and cost performance assessment in the supply chain. Our performance metrics and inventory target levels are usually presented in matrix forms, allowing them to accommodate a relatively large spectrum of linear demand models, and making them simple to implement. Several illustrations for possible applications of our models are provided.
An Oil Pipeline Design Problem
Authors: Brimberg Jack , Hansen Pierre , Lin Keh-Wei , Mladenović Nenad , Breton MichÈle
Published: December 2003

We consider a given set of offshore platforms and onshore wells producing known (or estimated) amounts of oil to be connected to a port. Connections may take place directly between platforms, well sites, and the port, or may go through connection points at given locations. The configuration of the network and sizes of pipes used must be chosen to minimize construction costs. This problem is expressed as a mixed-integer program, and solved both heuristically by Tabu Search and Variable Neighborhood Search methods and exactly by a branch-and-bound method. Two new types of valid inequalities are introduced. Tests are made with data from the South Gabon oil field and randomly generated problems.
Record Matching in Data Warehouses: A Decision Model for Data Consolidation
Authors: Dey Debabrata
Published: December 2003

The notion of a data warehouse for integrating operational data into a single repository is rapidly becoming popular in modern organizations. An important issue in the integration process is how to deal with the identifier mismatch problem when combining similar data from disparate sources. A real-world entity may be represented using different identifiers in different operational data sources, and matching them may often be difficult using simple database operations expressed, say, as an SQL query. A record-by-record manual matching is also not practical because the databases may be large. A decision model is presented that combines probability-based automated matching with manual matching in a cost minimization formulation. A heuristic approach is proposed for solving the decision model. Both the model and the heuristic solution approach have been tested on real data. The results from the testing indicate that the model can be effectively used in real-world situations.