In This Issue

Red States Versus Blue States

In “Blotto Politics,” A. Washburn takes a quantitative look at everyone's favorite topic—political campaign spending. How should two political parties partition their budgets over the states, given that the states differ significantly in the number of electoral votes? Washburn takes a game theoretic approach and finds that the answer depends strongly on budgets, of course, but also on the information that each party has about the spending plans and history of the other.

How Hospital Size and Occupancy Affect Ambulance Diversion

In “The Impact of Size and Occupancy of Hospital on the Extent of Ambulance Diversion: Theory and Evidence,” G. Allon, S. Deo, and W. Lin show how key operational characteristics of hospitals, such as the number of beds in the emergency and inpatient departments and the use of inpatient beds, affect ambulance diversion. The authors use a combination of analytical models (queuing) and empirical (sample selection) methods on cross-sectional data from California hospitals. They find that a model based on unpredictable variability (uncertainty in arrivals and services) better explains the variation in the extent of diversion than one based on predictable variability (intraday patterns). The results also suggest that hospitals can be characterized by whether the emergency or the inpatient department is the main driver of ambulance diversion. Finally, the authors find evidence of a network effect, wherein ambulances are diverted more frequently in neighborhoods with more emergency departments.

Modifying Instance Generators to Better Support Research Conclusions

Experimental studies of algorithm performance rely on a collection of instances to support their conclusions. If we are to compare algorithms, these instances should have real-world applicability and elicit discriminating algorithm performance without bias. Instance generators do not necessarily produce instances with these properties without modification. In “Generating Applicable Synthetic Instances for Branch Problems,” L. Lopes and K. Smith-Miles propose a method for modifying instance generators to produce instances that support an experimental study's claims, and they propose a metric to establish the suitability of a set of instances to support such claims. They demonstrate the methodology using the curriculum timetabling problem. They show that experimental conclusions depend on the chosen instances, and their methodology lets them identify and correct instance bias. The algorithms demonstrated in the article are available as a COIN-OR project.

A Stochastic Programming Approach to Short-Term Power Systems Scheduling

The large-scale integration of renewable energy in power systems has triggered a re-evaluation of the existing practices for committing reserves to protect power systems from forecast errors and component failures. In “Multiarea Stochastic Unit Commitment for High Wind Penetration in a Transmission Constrained Network,” A. Papavasiliou and S. S. Oren present a stochastic programming model for day-ahead unit commitment that accounts for transmission constraints, generator and transmission line failures, and multiarea renewable supply uncertainty. The authors present a scenario selection algorithm inspired by importance sampling in order to formulate the model, and a parallel Lagrangian relaxation algorithm for solving the problem, which is implemented in a high-performance computing cluster. The approach is shown to outperform current operating practice and serves as a promising model for optimizing the level of reserves in day-ahead operations and analyzing the economic impacts of large-scale renewable energy integration.

Provably Good Inventory Policies with Dynamic Forecasts

The 2012 Annual State of Logistics Report reveals that total U.S. business logistics costs in 2011 rose to $1.28 trillion, a 6.6% increase from the previous year and accounting for 8.5% of the U.S. gross domestic product. Inventory costs in the United States have increased consistently over the last decade. Thus, finding efficient inventory control policies has become a primary challenge to many large organizations. Demand forecasts often serve as an essential managerial tool to address uncertainties about future demands. In “Approximation Algorithms for the Stochastic Lot-Sizing Problem with Order Lead Times,” R. Levi and C. Shi develop a new class of efficient policies for these rather complex optimization models. The new policies can be applied under almost any forecast mechanism, and their performance is nearly optimal. The authors establish the quality of the new policies through theoretical analysis and computational experiments.

Managing Hybrid Manufacturing/Remanufacturing Systems with Finite Production Capacity

The remanufacturing industry has seen enormous growth in recent years. At the individual company level, however, most remanufacturing companies are still small or medium in size; thus their ability to satisfy market demands is highly constrained by their production capacity. In “Optimal Control Policy for Capacitated Inventory Systems with Remanufacturing,” X. Gong and X. Chao study the optimal control policy for hybrid manufacturing/remanufacturing systems with finite capacities in manufacturing, remanufacturing, and/or total manufacturing/remanufacturing operations. In addition to characterizing the structure of the optimal policy for different capacitated systems, they show that the optimal production policy gives priority to remanufacturing for systems with a remanufacturing capacity and/or a total manufacturing/remanufacturing capacity. However, this priority rule does not hold for systems with a manufacturing capacity.

Simple Dynamic Pricing Algorithms with Volatile Demand

In “Simple Policies for Dynamic Pricing with Imperfect Forecasts,” Y. Chen and V. F. Farias revisit a simple revenue management problem—dynamic pricing for a single product over a finite horizon—and consider the scenario in which demand is highly volatile but difficult to forecast. The authors show that this problem's structure mitigates the need for a careful forecast in a broad array of circumstances. In particular, they propose a class of “balanced” pricing policies that compensate for forecast imperfections by frequent reoptimization and reestimation of the “instantaneous” market size. In many cases, these pricing policies offer strong performance guarantees.

Solving Optimal Stopping Problems by Eigenfunction Expansions

Many problems in financial engineering can be formulated as an optimal stopping problem. Examples include pricing financial options with early exercise features, evaluating real options in physical investment projects, and timing decisions in trading strategies. In “Optimal Stopping and Early Exercise: An Eigenfunction Expansion Approach,” L. Li and V. Linetsky develop an approach based on eigenfunction expansions to solve finite-horizon optimal stopping problems for a wide class of Markov processes. They find the value function of the discrete time optimal stopping problem analytically using eigenfunction expansions, with the continuous time value function approximated by the discrete time solutions via extrapolation. As an illustration for applications, the authors use the method to evaluate both financial and real options with early exercise features under a commodity model with mean-reverting jumps. Numerical results indicate the method is fast and accurate.

How to Explore Optimally

An oil company approaching a new oil or gas field must develop a strategy for exploring the field: Where should we drill first? What to do next? Clearly the choices for later targets may depend on what we observe at earlier wells. For example, positive results in one region may lead us to explore other nearby targets. Conversely, negative results may lead us to explore other regions or quit altogether. Researchers considering R&D projects face similar problems. These sequential exploration problems resemble the classic multiarmed bandit problem, but correlation among the “arms” plays an important role. In “Optimal Sequential Exploration: Bandits, Clairvoyants, and Wildcats,” D. B. Brown and J. E. Smith develop methods for studying such problems, including heuristics and “clairvoyant” performance bounds that build on new results for bandit superprocesses. The authors apply these methods to a real oil and gas exploration problem and find that they perform well.

Comparing the Performance of Similar but Not Identical Firms

Data envelopment analysis measures the relative efficiency of similar firms called decision-making units (DMUs). Traditionally this assumes DMUs are homogeneous with the same set of inputs used to produce the same set of outputs. Often, comparisons are needed of similar DMUs where this homogeneity assumption is not strictly met e.g., a group of manufacturers in the same industry producing a range of related products, but where all manufacturers do not produce all products. This heterogeneity is usually ignored, leading to potentially unfair evaluations, or DMUs are divided into subsamples with identical product ranges, defeating the original objective of comparing all DMUs. In “Data Envelopment Analysis with Nonhomogeneous DMUs,” W. D. Cook, J. Harrison, R. Imanirad, P. Rouse, and J. Zhu develop DEA models that relax the homogeneity assumption. They apply these models to a group of steel fabrication plants to show how they provide fairer evaluations of performance.

Can We Truly Afford to Consider Uncertainty in Customer Demands?

In “The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty,” C. E. Gounaris, W. Wiesemann, and C. A. Floudas study the capacitated vehicle routing problem (CVRP) with uncertain customer demands supported on generic polyhedra. The authors derive robust optimization counterparts and show they provide solutions that are no more conservative than what is absolutely necessary to insure against all admissible demand realizations. The derivation of robust rounded capacity inequalities, coupled with efficient techniques for their separation, further enables the development of a branch-and-cut framework, which is used to solve standard literature benchmark instances with up to 100 customers. The authors demonstrate that incorporating demand uncertainty in the CVRP does not have to come at the expense of solution quality or at a prohibitive computational burden. Its implications extend beyond the confines of the CVRP and open new avenues for exploration in the broader area of vehicle routing under uncertainty.

Patrol Against Potential Attacks

Police officers patrol highways and cities; security guards patrol museums and shopping malls; soldiers patrol military bases and borders. To design an effective patrol strategy, one needs to take into account many factors. Some places may be more important, and some places may be more vulnerable. Furthermore, if the patrol is not planned carefully, the enemy may target the weakest link to maximize the chance of success. In “A Graph Patrol Problem with Random Attack Times,” K. Y. Lin, M. P. Atkinson, T. H. Chung, and K. D. Glazebrook formulate a mathematical model to study the optimal patrol strategy. They also develop algorithms that produce near-optimal patrol strategies with significantly less computational effort than is required to compute the optimal strategy.

Improving Appointment-Scheduling Efficiency

In many service delivery systems, the core operational activities are largely planned around the demand arrival times. The ability to regulate arrivals through a suitable appointment system is thus central to these systems' performance. In “Scheduling Arrivals to a Stochastic Service Delivery System Using Copositive Cones,” Q. Kong, C.-Y. Lee, C.-P. Teo, and Z. Zheng investigate an appointment-scheduling problem in an outpatient clinic with stochastic service durations. The authors assume that only the mean and covariance estimates of the service durations are known, and they plan for the worst-case distribution to balance patients' waiting time and doctor's overtime. Adopting such a distributionally robust model for the uncertainty transforms the problem into a convex conic optimization problem with a tractable semidefinite relaxation. They use this approach to develop a practical appointment schedule at an eye clinic that can significantly improve the efficiency of the clinic's appointment system.

Designing Equitable Vehicle Service Districts with Unknown Demand Distribution

The task of providing service to a territory with a fleet of vehicles (that is, vehicle routing) is a difficult and well-studied problem in the operations research community. One common strategy is to divide the territory into subregions and assign a vehicle to each. In “Robust Partitioning for Stochastic Multivehicle Routing,” J. G. Carlsson and E. Delage consider a data-driven vehicle routing problem in which the locations of demand points and their distribution are not known ahead of time. The authors propose designing these service subregions to minimize the worst-case workload when accounting for historical information regarding the demand locations. The authors derive a closed-form expression for the “worst-case a-posteriori distribution” of client locations with respect to a vehicle's workload, and they give algorithms that efficiently find these robust territory partitions. Experimentally, the proposed method exhibits excellent practical performance as more data is made available

Optimizing Portfolio Selection with Cardinality Constraints

Because of the presence of market friction, cardinality constrained investment situations naturally arise to select a small number of assets from an asset pool to optimize a portfolio objective. In “Optimal Cardinality Constrained Portfolio Selection,” J. Gao and D. Li focus on the cardinality constrained mean-variance portfolio selection problem and explore its structures and geometric properties. Unlike the existing literature of direct relaxations of the cardinality constraint, the authors consider modifying the objective function to some separable relaxations by the circumscribed box, the circumscribed ball, or the circumscribed axis-aligned ellipsoid, which are immune to the hard cardinality constraint and lead to analytical solutions. In addition, they derive efficient polynomial-time algorithms for the corresponding dual search problems. By integrating these lower bounding schemes and a heuristics in generating high-quality feasible solutions into a branch-and-bound algorithm, their scheme significantly outperforms CPLEX in identifying the exact optimal portfolio.

Computing Budget Allocation for Sample Average Approximation

The sample average approximation approach to solving stochastic programs induces a sampling error, caused by replacing an expectation by a sample, as well as an optimization error due to approximating the solution of the resulting sample average problem. In “Optimal Budget Allocation for Sample Average Approximation,” J. O. Royset and R. Szechtman obtain estimators of an optimal solution and the optimal value of the original stochastic program after executing a finite number of iterations of an optimization algorithm applied to the sample average problem. The authors examine the convergence rate of the estimators as the computing budget tends to infinity, and they characterize the allocation policies that maximize the convergence rate in the case of sublinear, linear, and superlinear convergence regimes for the optimization algorithm.

Optimal Sampling and Maintenance Policy

Stochastic control problems that arise in reliability and maintenance optimization typically assume that information used for decision making is obtained according to a predetermined sampling schedule. In many real applications, however, there is a high sampling cost associated with collecting such data. It is, therefore, equally important to determine when data should be collected through condition monitoring as it is to decide how this information should be utilized for maintenance decision making. In “Joint Optimization of Sampling and Control of Partially Observable Failing Systems,” M. J. Kim and V. Makis formulate and analyze the joint optimization of sampling and maintenance decision making in the partially observable Markov decision process framework. The paper establishes the optimality of a policy that is characterized by three critical thresholds, which have practical interpretation and give new insight into the value of condition-based maintenance programs used in life-cycle asset management.