In This Issue

Analytical Long-Term Care Capacity Planning

The rapidly aging population has resulted in an urgent need for long-term care programs and facilities to develop capacity expansion plans to meet this need. Current practice has been to use a fixed ratio of beds per person over age 75 for planning. This approach lacks rigor or empirical basis and is insensitive to regional demographic differences. It has resulted in long wait times for admission to care or to excess capacity. In “A Simulation Optimization Approach to Long-Term Care Capacity Planning,” Y. Zhang, M. L. Puterman, M. Nelson, and D. Atkins present a methodology for setting long-term care capacity levels over a multiyear planning horizon to achieve target wait time service levels. Their approach integrates demographic and survival analysis, discrete event simulation, and optimization. They illustrate this approach and derive policy recommendations through two case studies: one for a regional health authority in British Columbia, Canada, and the other for an individual long-term care facility.

Should I Buy Now or Wait for a Cheaper or Better Version?

As consumers, we all struggle with technology adoption decisions. Should I buy a new cell phone (or a new computer, new television, new car, and so on) now or wait for the next generation of the product, which might be better or cheaper? Firms face similar difficulties: Should I install a new power plant (or new piece of equipment, new manufacturing process, and so on) now or wait for a future generation of the technology, which might be better or cheaper? In “Technology Adoption with Uncertain Future Costs and Quality,” J. E. Smith and C. Ulu study these kinds of technology adoption decisions, with uncertainty about future costs and quality. They compare three models of the adoption decision: (i) a simple NPV model where the consumer adopts any technology whose NPV of benefits exceeds the cost of adoption; (ii) a stochastic dynamic programming model where the consumer can wait to adopt; and (iii) a more sophisticated (and more realistic) dynamic programming model where the consumer can wait to adopt and may also repeatedly adopt, by upgrading over time. Although the first two models have many intuitive structural properties (e.g., improving the technology makes consumers better off and encourages adoption), the more realistic third model has much more complicated policies, and some of these intuitive properties need not hold. For example, improving the technology may make the consumer better off and discourage adoption. In short, the technology adoption decisions that we consumers find difficult to make can also be quite difficult to study.

An Efficient Method for Solving the Economic Dispatch Problem

Economic dispatch is the problem of determining the most efficient, low-cost, and reliable operation of a power system by dispatching the available electricity generation resources to the load on the system. The primary objective of economic dispatch is to minimize the total cost of generation while satisfying the physical constraints and operational limits. This problem is formulated as a nonconvex nonlinear programming problem, which is, in general, difficult to solve. In “Lagrangian Duality and Branch-and-Bound Algorithms for Optimal Power Flow,” D. T. Phan proposes an efficient method to solve the problem to optimality.

An Alternate Approach to Inventory Models with Fixed Costs

Stochastic dynamic inventory problems with fixed costs are technically challenging because the objective function is neither concave nor convex. The problems have traditionally been analyzed by showing that the objective function is K-concave or non-K-increasing. In “On the Quasiconcavity of Lost-Sales Inventory Models with Fixed Costs,” Q. Li and P. Yu identify a set of conditions under which both the objective function and the maximal value function are quasiconcave. Not only is the quasiconcavity useful in computation, it leads to sharper and more intuitively appealing characterization of the optimal policies.

Sensor Placement Optimization for Threat Detection

This work presents a stochastic optimization approach to placement of passive acoustic sensors for underwater threat detection in a surveillance zone with complex environmental noise. In “Stochastic Optimization of Sensor Placement for Diver Detection,” A. Molyboha and M. Zabarankin suggest an approach that is efficient in numerical experiments with real data and can be used in underwater security systems. They also propose decision-aid software for detecting a hostile swimmer or diver in an urban harbor or estuary.

Estimating Lost Demand in the Presence of Substitution Effects

Two important problems in retail demand forecasting are estimating turned away demand when items are sold out and properly accounting for substitution effects among related items. For simplicity, most retail demand forecasts rely on time-series models of observed sales data, which treat each stock keeping unit (SKU) as receiving an independent stream of requests. However, if the demand lost when a customer's first choice is unavailable (referred to as “spilled” demand) is ignored, the resulting demand forecasts may be negatively biased; this underestimation can be severe if products are unavailable for long periods of time. Concurrently, stockout-based substitution will increase sales in substitute products that are available (referred to as “recaptured” demand); ignoring recapture in demand forecasting leads to an overestimation bias among the set of available SKUs. Correcting for both spill and recapture effects is important to establishing a good estimate of the true underlying demand for products. In “Estimating Primary Demand for Substitutable Products from Sales Transaction Data,” G. Vulcano, G. van Ryzin, and R. Ratliff propose a method for estimating substitute and lost demand when only sales and product availability data are observable, not all products are displayed in all periods (e.g., due to stock-outs or availability controls), and the seller knows its aggregate market share. The model combines a multinomial logit (MNL) choice model with a nonhomogeneous Poisson model of arrivals over multiple periods and uses the expectation-maximization (EM) method to compensate for incomplete observations of primary demand; that is, the demand that would have been observed if all products had been available in all periods. The procedure is shown to be effective on both simulated and real-world data sets.

Benefits of Competition in Imperfect Markets

As government intervention in the marketplace suffers increasing criticism in recent years, the authors analyze the impact of antitrust laws on the welfare of society. Although it is well known that in a perfectly competitive market, free competition is optimal for society, in practice many markets are oligopolies: they are controlled by only a few price-setting firms. In such an environment, free competition does not necessarily lead to an optimal social outcome. In “Generalized Quantity Competition for Multiple Products and Loss of Efficiency,” J. Kluberg and G. Perakis evaluate the impact of competition on both social welfare and firms' profit. For a market in which firms compete for market share, they compute the social benefit and the cost for the firms of enforcing competition as a function of market characteristics such as the number of competing firms and the intensity of competition.

Balancing Contractual and Spot Market Revenue Streams in Cargo Revenue Management

Cargo carriers face the same fundamental trade-off as passenger carriers. Given a request for a certain amount of capacity at a certain price, should the carrier accept this request to generate revenue or keep the capacity for a more profitable request that may arrive in the future? Although the fundamental trade-off is the same, management of cargo capacity brings unique challenges when compared with management of passenger capacity. To begin with, cargo capacity is measured in multiple dimensions such as weight, volume, and location of the cargo in the body of the aircraft. Furthermore, the amount of capacity that will eventually be used by an accepted cargo request is usually not known until the departure time of the aircraft, resulting in an additional source of uncertainty. Finally, carriers do business through periodically signed contracts that can generate a steady stream of cargo from large customers and through the spot market that can be somewhat unpredictable. In “Cargo Capacity Management with Allotments and Spot Market Demand,” Y. Levin, M. Nediak, and H. Topaloglu develop a model that allows a carrier to decide which portion of the capacity to sell through contracts and which portion of the capacity to reserve for the spot market. The model has both tactical and operational implications, as it can be used not only to make relatively infrequent contract decisions, but also to manage the cargo capacity reserved for the spot market on a day-to-day basis.

Proposing a Novel Solution Method for Integrated Supply Chain Design Problems

Integrated supply chain design problems are normally modeled as complex integer or mixed-integer nonlinear optimization problems. In the past decade, column generation and Lagrangian relaxation methods have been the solution methods of choice for different versions of these problems. However, these algorithms are problem-specific and time consuming to design and implement. In “A Conic Integer Approach to Stochastic Joint Location-Inventory Problems,” A. Atamtürk, G. Berenguer, and Z.-J. Shen suggest conic programming as an alternative approach for solving these problems. Conic optimization has been employed in a wide arrange of areas, including basic uncapacitated facility location problems, but this paper is the first to apply conic integer programming formulations to various supply chain design problems. The advantage of the new approach is that it not only provides a more general modeling framework but also leads to fast solution times in general.

Clustering Customers for Inventory Routing

Tactical planning for inventory routing consists of grouping customers that are geographically close and can be serviced by a same vehicle in a periodic schedule. The objective is to minimize both the distances between customers and the number of vehicles required. The actual routes taken by vehicles on each day of the planning can be seen as an operational issue. In “A Column-Generation Based Tactical Planning Method for Inventory Routing,” S. Michel and F. Vanderbeck propose a truncated branch-and-price-and-cut algorithm combined with rounding and local search heuristics that yields solutions with a provably small optimality gap for real-live instances. Technically, the approach reveals an original treatment of the symmetry in the time period indexing: first define a solution for an average time period, which is then discretized over the time horizon. Practically, the solutions achieve a 10 percent improvement over the industrial practice both in terms of number of vehicles and travel distances, while being easier to implement given the regional clustering.

Representing a Semiclosed Polyhedron with Applications

Polyhedron theory, in particular the representation of a polyhedron, defined as the intersection of finitely many closed half spaces, as the convex hull of a finite set of points and directions, has applications in many areas of mathematics, including linear programs. It has been shown that the solution set of a linear multicriteria program is the union of finitely many polyhedra. This solution characterization has formed the base for the well-known multicriteria simplex method. A semiclosed polyhedron is defined as the intersection of finitely many closed half-spaces and/or open half-spaces. In “Piecewise Linear Multicriteria Programs: The Continuous Case and Its Discontinuous Generalization,” Y. P. Fang, K. Meng, and X. Q. Yang obtain a representation of a semiclosed polyhedron as a generalized convex hull of a finite set of points and directions, where coefficients of some points and directions are required to be positive, and they apply a semiclosed polyhedron to the study of the solution structure of piecewise linear multicriteria programs and the solution procedure of a bicriteria portfolio selection problem with an l_∞ risk measure and transaction costs.

Solving Network Flow Problems Fast Using the Belief Propagation Algorithm

The paper establishes the largest known class of optimization problems solvable by the belief propagation (BP) algorithm—the minimum cost network flow problem (MCNF). It is shown that, while a general linear programming problem is not solvable by the BP algorithm, the BP does solve MCNF problem in pseudo-polynomial time. BP is a popular heuristic introduced in the literature on statistical inference and used in many applications. Whereas excellent practical performance of the algorithm is well known, understanding the theoretical power of the algorithm is a very active area of current research. The paper “Belief Propagation for Min-Cost Network Flow: Convergence and Correctness,” by D. Gamarnik, D. Shah, and Y. Wei is a step forward in this direction.

Inventory Models When Information Is Given by an Oracle

The literature on inventory models typically assumes that either all cost functions are given to the vendor explicitly or that additional structure about the revenue, salvage, and order cost functions is known. But this is not always a realistic assumption. For example, in some cases, the supplier does not reveal the order cost function to the vendor, and instead provides quotes for every query submitted by the vendor. This scenario applies, for example, when the vendor purchases in the spot market, as well as situations where orders are placed over the Internet. The same is true for demand forecast. Indeed, firms typically maintain a database that includes historical customer demand information and update it with daily or weekly point of sale (POS) data. In such an environment, there may not be a function representing the demand distribution. Rather, the database provides the probability that demand (or more precisely, sales) is smaller than a certain value, for any value inspected by the user. In “Approximating the Nonlinear Newsvendor and Single-Item Stochastic Lot-Sizing Problems When Data Is Given by an Oracle,” N. Halman, J. B. Orlin, and D. Simchi-Levi show that unlike traditional newsvendor inventory models, when information about various functions (cost, forecast) is given by an oracle, the problems become intractable. Moreover, these problems cannot be approximated to within any given constant. Fortunately, however, the authors develop fully polynomial time approximation schemes by focusing on two dimensions when maximizing business performance: expected profit and profit-to-cost ratio. Specifically, given a requirement on the profit-to-cost ratio, the approximation schemes generate efficient solutions that satisfy the requirement and are arbitrary close to the optimal profit.

Stochastic Derivative Estimators for Discontinuous Payoff Functions

For complex stochastic models requiring simulation, derivative estimates play an important role in both sensitivity analysis and gradient-based optimization. In the last three decades, derivative estimation has been studied extensively in the simulation literature. However, dealing with payoff functions with discontinuities is still a main challenge. In “A New Stochastic Derivative Estimator for Discontinuous Payoff Functions with Application to Financial Derivatives,” Y. Wang, M. C. Fu, and S. I. Marcus derive a new unbiased stochastic derivative estimator for a class of discontinuous payoff functions that arise in many options pricing settings from finance. Specifically, they circumvent the difficulty of differentiating discontinuous payoff functions by an appropriate change of random variables. The resulting estimator can be computed from a single sample path or simulation. They applied this technique to sensitivity analysis for European call options and American-style call options.

Refining Square-Root Staffing for Call Centers with Impatient Customers

In call centers it is crucial to staff the right number of agents so that the targeted service levels are met. These staffing problems typically lead to constraint satisfaction problems that are hard to solve. During the last decade, a beautiful many-server asymptotic theory has been developed to solve such problems for large call centers, and optimal staffing rules are known to obey the square-root staffing principle. In “Staffing Call Centers with Impatient Customers: Refinements to Many-Server Asymptotics,” B. Zhang, J. S. H. van Leeuwaarden, and B. Zwart develop refinements to many-server asymptotics and this staffing principle for a Markovian queueing model with impatient customers.

Skill-Based Routing at Call Centers or Organ Transplants: Who Will Serve You?

Current service systems care for customers of various requirements and are operated by servers of various skills, and some overlap of server skills is used to achieve needs tailored service as well efficient resource pooling. Many such systems, including call centers on the one hand and the matching of kidney transplant patients to donors on the other, operate under FCFS regime, where whenever a server is available he will engage the longest waiting customer compatible with his skills. Crucial for the design of such systems is the question, what is the fraction of type i customers that will be served by a type j server? In “Exact FCFS Matching Rates for Two Infinite Multitype Sequences,” I. Adan and G. Weiss derive these i–j matching rates from a new probability model.

Slowdown and Diffusion Approximations

Slowdown is the ratio between the sojourn time and the service time experienced by a typical customer in a queueing network. Because sojourn time is the sum of the queueing delay and the service time, slowdown takes values between 1 and ∞. Most diffusion approximation results in the heavy traffic literature are concerned with situations in which the slowdown is either very close to 1 or very large. This corresponds to the delay being negligible with respect to the service time, or vice versa. Exceptions are the treatments by Mandelbaum, Gurvich, and Shaikhet, and independently, Whitt, of the M/M/N queue in a heavy traffic diffusion regime where the slowdown is nondegenerate (i.e., does not converge to 1 or ∞). In applications, this regime is important because delay and service time are often observed to be of the same order of magnitude. In “A Diffusion Regime with Nondegenerate Slowdown,” R. Atar analyzes a queue with multiple heterogenous servers in the regime alluded to above and identifies a new limit law for the joint distribution of delay and service time and, as a result, for the sojourn time process.