In This Issue
Nonlinear Pricing: A Key to Success for Fashion Retailers
Nonlinear pricing is frequently used by fast-fashion retailers (e.g., Zara). Discounts of the form “Buy 2, get 20% off” or “Buy 3 and save 30%” are becoming common. by Gallego, Li, and Liu in “Dynamic Nonlinear Pricing of Inventories over Finite Sales Horizons,” nonlinear dynamic pricing can significantly improve a company’s revenue, by as much as 30%–90%, especially when inventories are high and the relative value of the marginal unit is neither too low nor too high, a situation that is common in fast-fashion retailing. They find that a single quantity discount threshold can capture most of the benefits of nonlinear pricing. The simplicity of this policy validates observed practice and concentrates managerial efforts to dynamically selecting the threshold and the depth of the discount.
Benefit of Planning Replenishment Trips in Stochastic Vehicle Routing
In “Technical Note—Worst-Case Benefit of Restocking for the Vehicle Routing Problem with Stochastic Demands,” Bertazzi and Secomandi shed new light on an old yet timely problem in transportation. They analyze the benefit of planning replenishment trips in the vehicle routing problem with stochastic demands, taking as a benchmark their execution only upon stock-outs. Their worst-case investigation provides a theoretical explanation of a phenomenon that has been observed in prior numerical studies.
Dynamic Pricing for Revenue Management with Reusable Resources
In “Real-Time Dynamic Pricing for Revenue Management with Reusable Resources, Advance Reservation, and Deterministic Service Time Requirements,” Lei and Jasin consider a fundamental dynamic pricing problem when resources are reusable. In this problem, demand arrives according to a price-sensitive nonstationary rate, requesting a service that uses a combination of different types of resources for a deterministic duration of time. The resources are reusable in the sense that they can be immediately used to serve a new customer on the completion of the previous service. Moreover, different customers may have different service time requirements and may book the service in advance. The objective is to construct a dynamic pricing control that maximizes expected total revenues. They develop real-time heuristic controls based on the solution of the deterministic relaxation of the original stochastic problem and show that the proposed controls are near optimal in the regime of large demand and large resource capacity.
Container Terminal Operations: Models and Design
The design of container terminal operations is complex because multiple factors affect operational performance. These factors include numerous choices for handling technology, terminal topology, and design parameters and stochastic interactions between the quayside, stackside, and vehicle transport processes. In “Modeling and Design of Container Terminal Operations,” Roy, De Koster, and Bekker propose new integrated queuing network models for rapid design evaluation of container terminals with automated lift vehicles and automated guided vehicles. These models offer the flexibility to analyze alternate design variations and develop insights. For instance, the effect of different vehicle dwell point policies and efficient terminal layouts are analyzed. The authors show the relation among the dwell point–dependent waiting times and also show their asymptotic equivalence at heavy traffic conditions. These models form the building blocks for design and analysis of large-scale terminal operations. The authors test the model efficacy using detailed simulation experiments and real-terminal validation.
Vehicle Routing Under Uncertainty
In the paper, “The Distributionally Robust Chance-Constrained Vehicle Routing Problem,” Ghosal and Wiesemann examine when the popular two-index vehicle flow formulation can be used to solve a distributionally robust variant of the capacitated vehicle routing problem when only certain moments of the probability distribution governing the uncertain customer demands are available. In contrast to much of the existing literature, their framework does not require knowledge of the precise probability distribution underlying the customer demands, and it does not require the customer demands to be independent either. They also develop efficient cut generation schemes for several popular classes of moment ambiguity sets that allow the distributionally robust vehicle routing problem to be solved in times that are comparable to the deterministic formulation.
Options Portfolio Selection
Options markets offer countless opportunities for investment and hedging, but leave investors with the high-dimensional puzzle of combining nonlinear payoffs in several assets as to maximize the risk-return tradeoff, a problem that is ill-suited to standard approaches because of the extreme correlation among options' payoffs. In “Technical Note—Options Portfolio Selection,” Guasoni and Mayerhofer develop a method to optimize portfolios of European call and put options with different exercise prices and on several correlated assets. Even if all options carry a positive risk premium, it may be optimal to take negative positions in some of them, as the resulting expected losses are more than offset by their hedging benefits, which enable larger positions in more profitable options. In particular, options with zero risk premium, while unattractive in isolation, are ideal hedging tools to improve the risk-return tradeoff of options portfolios.
Extending the Toolkit of Choice Models for Assortment Optimization
When retailers decide which assortment of products to offer, they can make use of a choice model that describes how customers choose and substitute among the products. The key is to use a choice model that faithfully captures the choice process of customers, while making sure that the corresponding problem of finding the revenue-maximizing assortment remains tractable. In “Assortment Optimization Under the Paired Combinatorial Logit Model,” Zhang, Rusmevichientong, and Topaloglu consider the paired combinatorial logit model to capture the choice process of customers. This choice model uses a utility maximization framework to capture the customer choices, and the utilities of the products can have a rather general correlation structure. The authors demonstrate that one can construct algorithms with performance guarantees to solve the assortment optimization problem under this choice model.
A New Approach to the CMS Hospital Star Ratings
For many years, stakeholders have been complaining about how hospital scores are computed in the Centers for Medicare and Medicaid Services (CMS) hospital star ratings. In “An Efficient Frontier Approach to Scoring and Ranking Hospital Performance,” Adelman shows how the current system can lower the scores even of hospitals that improve along every quality measure. He proposes a new approach, based on an optimization framework, that he proves does not exhibit this behavior, and thus creates better incentives for hospitals to improve. The approach scores hospitals as closely as possible to the best scoring hospital on the efficient frontier of hospital performance, under the same measure weights. It is flexible enough to incorporate constraints that represent stakeholder interests, such as giving higher weight to measures that impact more people. Using this new approach, he computes new scores for nearly every hospital in the United States and shows that there are significant differences with the current CMS hospital star ratings.
Can Adopting Multiple Revenue Streams Secure Long-Term Sustainability of HIEs?
Healthcare information exchanges (HIEs) facilitate information sharing among participating healthcare practices. Despite HIEs’ pivotal role in improving healthcare delivery, many struggle to be financially sustainable in the long run. As a practical and implementable solution for this issue, in “Sustainability Planning for Healthcare Information Exchanges with Supplier Rebate Program,” Rajapakshe, Kumar, Sen, and Sriskandarajah propose a multiperiod two-service model that improves the profitability of HIEs while retaining a sizable member pool. This study provides the guidelines for HIEs in adopting a two-service model. It also sheds light on how policymakers could intervene successfully to improve participation of healthcare providers and operations of the HIEs to guarantee long-term survival.
Optimal Pricing in Networks
How should a firm make pricing decisions in social networks when the customers hold in private their local network information? In “Optimal Nonlinear Pricing in Social Networks Under Asymmetric Network Information,” Zhang and Chen develop a solution approach based on calculus of variations and positive neighbor affiliation to tackle this problem. They show that the optimal pricing compromises the capitalization of the susceptibility to neighbor consumption with the motivation of one’s own consumption, which gives rise to a menu of quantity premium or quantity discount. In the Erdös and Rényi graph (a special case of the social network model in this paper), they find that the pricing scheme does not screen network positions; consequently, the firm can offer a simple uniform price. The authors also find that, in the context of two-way connections, the firm-optimal consumption becomes linear in customer degree in the scale-free network.
Near-Optimal Solutions for High-Dimensional Capacity Control and Pricing
Many revenue management problems require making capacity control and pricing decisions for multiple products. The decisions for the different products interact because either the products use a common pool of resources or the customers choose and substitute among the products. When pricing airline tickets, for example, different itinerary products use the capacities on common flight legs, and the customers choose and substitute among different itinerary products that serve the same origin-destination pair. Finding the optimal capacity control and pricing decisions in such problems can be challenging because one needs to simultaneously consider the capacities available to serve a large pool of products. In “An Approximation Algorithm for Network Revenue Management Under Nonstationary Arrivals,” Ma, Rusmevichientong, Sumida, and Topaloglu develop efficient methods to make decisions with performance guarantees in high-dimensional capacity control and pricing problems.
Adaptive Algorithms for Submodular Covering
Many applications of stochastic optimization involve making sequential decisions until some stopping criterion is satisfied. For example, in medical diagnosis, a doctor needs to perform an adaptive sequence of tests on a patient in order to diagnose a disease. Being adaptive allows the doctor to choose the next test based on the outcomes of prior tests. Given an a priori probability distribution over diseases, the goal is to minimize the expected cost of tests. In “Adaptive Submodular Ranking and Routing,” Navidi, Kambadur, and Nagarajan formulate a general stochastic optimization problem in which the stopping criterion corresponds to covering a submodular function. Such problems arise in many applications, including active learning, robotics, and disaster management. The authors obtain efficient algorithms with best possible performance guarantees. These results also extend to a vehicle-routing setting, in which one needs to plan an adaptive route based on information observed at nodes in the network. The authors also present experimental results on a data set arising in the identification of toxic chemicals, thereby demonstrating the practical applicability of their algorithm.
New Decomposition Method for General MILPs
Many methods that have been proposed to solve large-scale mixed integer linear programing (MILP) problems rely on the use of decomposition strategies. These methods exploit either the primal or dual structures of the problems by applying the Benders decomposition or Lagrangian dual decomposition strategy, respectively. In “The Benders Dual Decomposition Method,” Rahmaniani, Ahmed, Crainic, Gendreau, and Rei propose a new and high-performance approach that combines the complementary advantages of both strategies. The authors show that this method (i) generates stronger feasibility and optimality cuts compared with the classical Benders method, (ii) can converge to the optimal integer solution at the root node of the Benders master problem, and (iii) is capable of generating high-quality incumbent solutions at the early iterations of the algorithm. The developed algorithm obtains encouraging computational results when used to solve various benchmark MILP problems.
Content Distribution and End-to-End Monitoring with Set Cover by Pairs
Digital content is housed at data centers located on nodes of a data network. Consumers of this content are also located on network nodes. Content flows from a data center to a consumer on a path defined by a routing protocol, such as open shortest path first. A pair of data centers is said to feasibly serve content to a consumer if there are disjoint paths from each data center to the consumer. In “Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs,” Johnson, Breslau, Diakonikolas, Duffield, Gu, Hajiaghayi, Karloff, Resende, and Sen study this problem when the goal is to minimize the number of required data centers to serve a set of consumers. They also study another facility location problem that arises in network traffic monitoring. Both problems are modeled as a set cover-by-pairs problem. The authors provide complexity results, a new lower-bounding integer programming formulation, and several heuristics. The lower bounds are easily computed with a commercial MIP solver and validate the claim of near-optimality of their heuristics.
When (and When Not) to Leave a Short Deadline with Your Offer
In “Deadlines, Timing, and the Search for Alternatives,” Zorc and Tsetlin consider decentralized matching markets like the job market for MBAs. They show that exploding offers (ones with a very short deadline) are often optimal. The benefit of those offers is to prevent the other party’s search for alternatives. However, the main argument in favor of longer deadlines is that people who already hold an offer become more selective when deciding whether to accept other alternatives (the acceptance deterrence effect). Thus, the goal of curtailing search can also be accomplished through increasing the other party’s selectivity instead of preventing them from searching altogether. A practical prescription for offer makers is to use exploding offers when acceptance deterrence is weak (e.g., when the other party’s alternatives will not change) and longer deadlines when it is strong (e.g., when you are able to react to the other party’s other offers).
A New Perspective on the Bootstrap Method
The bootstrap method is one of the major developments in statistics in the 20th century for computing confidence intervals directly from data. However, the bootstrap method is traditionally approximated with a randomized algorithm, which can sometimes produce inaccurate confidence intervals. In “Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms,” Bertsimas and Sturt present a new perspective of the bootstrap method through the lens of counting integer points in a polyhedron. Through this perspective, the authors develop the first computational complexity results and efficient deterministic approximation algorithm (fully polynomial time approximation scheme) for bootstrap confidence intervals, which unlike traditional methods, has guaranteed bounds on its error. In experiments on real and synthetic data sets from clinical trials, the proposed deterministic algorithms quickly produce reliable confidence intervals, which are significantly more accurate than those from randomization.
