In This Issue
Stable Matching with Proportionality Constraints
School choice programs seek to give students the option to choose their school but also close an opportunity gap. To be fair in the assignment of students, it is usually argued that the assignment of students to schools should be stable. This second concern is usually expressed in terms of proportions. As an example, in 1989, the city of White Plains, New York, required each school to have the same proportions of Blacks, Hispanics, and “others,” a term that includes Whites and Asians. Satisfying both these concerns at the same time is difficult. Prior work replaces the proportions by numbers related to the capacity of school, but this assumes each school is operating at full capacity, which is often not the case. In “Stable Matching with Proportionality Constraints,” Nguyen and Vohra treat such proportionality constraints as soft but provide ex post guarantees on how well the constraints are satisfied while preserving stability.
Coming Soon: Dynamic Electricity Prices for Your Home's Smart Appliances
For the first time in the history of the power industry, because of smart meters, we now have the technology deployed to charge real-time prices for electricity to large populations of consumers. At the same time, homes are becoming smarter with appliances that can autonomously respond to their environment and optimize their performance. Imagining a world in which smart appliances anticipate future changes in electricity prices, in “Dynamic Electricity Pricing to Smart Homes,” Adelman and Uçkun develop an approach to evaluating market price–load equilibria when such smart appliances saturate a power utility's service region on a large scale. Their findings indicate substantial improvements in social welfare as compared with the current status quo of flat prices or popular peak-pricing policies.
Effects of Multiple Hospital Resources in Planning Surgical Procedures
Hospital care is one of the fundamental components in any healthcare delivery system. Within hospital care, surgical procedures account for the largest share of the revenue generated. Traditionally, the operating room (OR) capacity is viewed as a major constraint limiting a hospital's ability to increase the number of surgical procedures and the accompanying revenues. However, each procedure consumes not only the OR capacity but also the hospital bed capacity. In “Managing Portfolio of Elective Surgical Procedures: A Multidimensional Inverse Newsvendor Problem,” Bavafa, Leys, Örmeci, and Savin investigate the effects of the interaction between the two resources (i.e., OR and recovery beds) on the optimal number of elective surgical procedures to be performed daily. They evaluate the performance of the “front-end” approach, which considers only the OR capacity, in different settings. Moreover, they show how the variability of the resource utilization by surgical procedures affects the optimal elective portfolio.
A Data-Driven Functionally Robust Approach for Simultaneous Pricing and Order Quantity Decisions with Unknown Demand Function
In “A Data-Driven Functionally Robust Approach for Simultaneous Pricing and Order Quantity Decisions with Unknown Demand Function,” Hu, Li, and Mehrotra consider a retailer's problem of optimally pricing a product and making order quantity decisions without knowing the function specifying price–demand relationship. The authors assume that the price is set only once after collecting data, possibly from history or a market study, and that the price–demand relationship is a decreasing convex or concave function. Different from the classic approach that fits a function to the price–demand data, we propose and study a maximin framework introducing a novel concept of function robustness. This function robustness concept also provides an alternative mechanism for performing sensitivity analysis for decisions in the presence of data fitting errors. The overall profit maximization model is a non-convex optimization problem in a function space. A two-sided cutting surface algorithm is developed to solve the maximin model. An analytical approach to compute the rate of decrease of optimal profit is also given for the purposes of sensitivity analysis.
Novel Approach for Job-Shop Scheduling Problems in Traffic Management
Vehicle scheduling is a central problem in transportation. As railways and the airspace become increasingly congested, it is crucial to develop mathematical tools to better schedule trains and airplanes off-line (timetabling) and online (dispatching). These traffic-management problems can be modeled as job-shop scheduling problems, which, in turn, can be solved using mixed-integer linear programming (MILP). The two most successful and widespread formulations in the past decades are the big-M and the time-indexed methods, each with its strengths and weaknesses. However, there have been few advancements in either approach in recent years. In “A Noncompact Formulation for Job-Shop Scheduling Problems in Traffic Management,” Lamorgese and Mannino introduce an alternative formulation, obtained by strengthening and lifting the Benders' reformulation of a natural initial formulation. This new approach improves performances on our real-life test bed and opens up interesting research directions.
Joint Pricing and Inventory Management with Strategic Customers
In a vast number of industries, such as beverage, e-retail, furniture, and hair care, firms need to dynamically decide both products' prices on the demand side and inventory replenishment quantities on the supply side. Given that prices dynamically evolve over time, some customers are forward-looking who strategize their purchase times. Therefore, it is important to understand what joint pricing and inventory management policy a firm should adopt in the presence of strategic (forward-looking) customers. In “Joint Pricing and Inventory Management with Strategic Customers,” Chen and Shi show that a simple cyclic policy is optimal. In their analysis, they begin with using a mechanism design approach to establish an upper bound of the firm's optimal profit. They then exploit the structure of the upper bound profit to propose a joint pricing and inventory policy. They finally show that the upper bound profit is attained under this policy.
A Critical Review of Recent Stochastic Frontier Methods and Their Connections to Data Envelopment Analysis
In “Combining the Virtues of Stochastic Frontier and Data Envelopment Analysis,” Parmeter and Zelenyuk strive to provide the first critical review of the literature on semi- and nonparametric estimation and inference for the stochastic frontier model. This pellucid review demonstrates that these new, cutting edge methods enjoy nearly all of the modeling advantages inherent in the more traditional operations research (OR) method known as data envelopment analysis (DEA) while allowing for measurement error, a known bane to applied OR scientists. Parmeter and Zelenyuk focus on major recent developments in this important milieu, drawing myriad connections with the application of DEA across OR, discuss how useful synergies can be undertaken by practitioners, and offer practical implementation issues of these methods. They conclude with useful insights from what also appears to be the first comprehensive Monte Carlo study comparing the performance of the methods discussed.
A Generalized MIP Value Function and Its Applications
The classical definition of the integer programming value function parameterizes the optimal value of an integer program by its right-hand side. In “Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function,” Tavaslıglu, Prokopyev, and Schaefer extend the classical definition to a generalized mixed-integer program (MIP) value function of a mixed-integer program, which is simultaneously parameterized by its objective and right-hand side. The generalized MIP value function possesses superadditivity in its right-hand side and subadditivity in its objective. It also has mixed-integer complimentary slackness and a recursive optimal value structure, which lead to ecient algorithms for calculating value functions. Challenging stochastic mixed-integer programming and multi-follower bilevel mixed-integer programming problems are reformulated through generalized MIP value functions, and the value function calculation algorithms provide a computationally effective way to solve these challenging problems.
Performance of Load-Balancing Algorithms in Time-Varying Systems
The degree to which delays or queue lengths equalize under load-balancing algorithms gives a good indication of their performance. Some of the most well-known results in this context are concerned with the asymptotic behavior of the delay or queue length at the diffusion scale under a critical load condition, where arrival and service rates do not vary with time. For example, under the join the shortest queue policy, the queue length deviation process, defined as the difference between the greatest and smallest queue length as it varies over time, is at a smaller scale (subdiffusive) than that of queue lengths (diffusive). The goal of “Subdiffusive Load Balancing in Time-Varying Queueing Systems” is to argue that subdiffusivity of the deviation process (SDDP) is not limited to heavy traffic. To exhibit the breadth of this phenomenon, we establish SDDP in three load-balancing models: power of d choices, redundancy routing, and longest queue first. The results of Atar, Keslassy, and Mendelson accommodate server heterogeneity and time-varying arrival and service intensities.
Modeling Customers' Retrial Decisions in Queues
Long waits are common in many services. When queues are long, waiting is undesirable, and customers may often choose to come back (i.e., retry) later. However, such retrial attempts can be costly due to the cost of transportation or re-planning. Despite their ubiquity in practice, retrials have not been modeled as decisions in the research literature. In “A Model of Rational Retrials in Queues,” Cui, Su, and Veeraraghavan propose a modeling framework for retrial decisions over time periods. Within each period, customers make rational state-dependent decisions to join, balk, or retry in a future period. The customers choose their optimal strategies based on the queueing dynamics that are in turn determined by collective strategies of all customers. The authors characterize the equilibria in both stable and overloaded systems and find that utility-maximizing self-interested customers retry insufficiently (compared with the socially optimal retrial rates) when their retrial cost is low and too often when their retrial cost is high.
Easily Solving Markov Decision Processes with States and Actions That Are Continuous Vectors
Individuals, firms, and governments often face the challenge of making optimal decisions in a dynamic setting amid a changing and uncertain environment. Although Markov decision processes (MDPs) provide a powerful modeling framework for such problems, solving an MDP is generally difficult. In “Easy Affine Markov Decision Processes,” Ning and Sobel characterize decomposable affine MDPs, which can be solved easily. An MDP in this class has continuous multidimensional controlled states and actions, and Markov-modulated uncontrolled states. With affine immediate reward and transition dynamics and affine constraints on actions, these MDPs have a linear value function and a linear optimal policy. The linear coefficients can be computed easily and exactly by solving a small auxiliary MDP, which frees the solution of the original MDP from the curse of dimensionality and errors caused by discretizing the continuous state and action spaces. The applicability of decomposable affine MDPs is illustrated in fishery management, capacity portfolio management, and commodity procurement.
How to Staff Service Systems, Route Workload to Employees, and Decide on Payment
Three fundamental questions when operating a service system are (1) how many employees to staff, (2) how to route work to them, and (3) how to pay them. These questions have often been studied separately; that is, the queueing and network-design literature that considers staffing and workload routing generally ignores payment, and the literature on employee payment generally ignores issues surrounding staffing and routing. In “Staffing, Routing, and Payment to Trade off Speed and Quality in Large Service Systems,” Zhan and Ward study how the aforementioned three decisions jointly affect system throughput and the quality of the service delivered when the employers maximize their own payment. They find that the system manager should first solve a joint optimization problem to determine the staffing level, the routing policy, and the service speed, and second, design a payment contract under which the employees work at the desired service speed.
Sequential Decision-Making in a Nonstationary Environment
Most existing literature in stochastic optimization assumes that the underlying cost function does not change over time. However, in practice, cost functions may be nonstationary and change along the time horizon. In “Nonstationary Stochastic Optimization Under Lp,q-Variation Measures,” Chen, Y. Wang, and Y.-X. Wang study nonstationary sequential stochastic optimization problems and consider a general Lp,q-variation functional to quantify the nonstationarity of underlying cost functions. The Lp,q-variation functional generalizes a previously considered variation constraint and captures local temporal and spatial changes of cost functions. The matching regret upper and lower bounds are provided. The regret bound shows interesting phenomena under this general variation functional, such as the curse of dimensionality, which shares a similar spirit as in nonparametric statistics.
Approximating the Performance of a Time-Varying Single-Server Queue
The natural queueing models for many operations research applications have time-varying arrival rates. In addition, the natural models often are not Markov stochastic processes, so that they are not amenable to exact mathematical analysis. In “Time-Varying Robust Queueing,” Whitt and You propose a time-varying robust queueing algorithm to approximate the time-varying distribution of the workload (virtual waiting time) in a non-Markovian single-server queue with a time-varying arrival-rate function. They apply simulation and asymptotic methods to examine the performance of periodic robust queueing. They show that periodic robust queueing converges to a proper limit in appropriate long-cycle and heavy-traffic regimes and coincides with long-cycle fluid limits and heavy-traffic diffusion limits for long cycles. Simulation examples show that the mean and the full distribution (specified by the quantiles) of the periodic steady-state workload are remarkably well approximated.
