In This Issue
Improving Gleaning Operations to Help Alleviate Food Waste and Food Insecurity
Although edible and healthy food was left unharvested in farm fields, 14% of U.S. households in 2014 were food insecure. The practice of gleaning combines the dual paradoxical problems of food waste and food insecurity to create an elegant solution for both. Gleaning dates back to ancient times when landowners allowed the poor to gather crops left on the fields after the harvest. Modern-day gleaning organizations coordinate volunteer gleaners to harvest crops donated by farmers to hunger-relief charities. Although the gleaning solution to food waste and food insecurity is conceptually elegant and appealing, the operationalization of the solution poses distinct challenges. Gleaning relies on two uncertain sources of input: the food and labor supplies. In “Dynamic Volunteer Staffing in Multicrop Gleaning Operations,” Ata, Lee, and Sönmez develop an intuitive method for scheduling gleaning trips that takes into account the uncertainties in the operation, thereby increasing the amount of fresh food rescued. A numerical study shows that the dynamic staffing policy we propose can recover approximately 10% of the volume lost compared with a static policy. To achieve this improvement, no capital or major process changes would be required—only some small changes to the staffing level requests.
Ellipsoidal Methods for Adaptive Choice-Based Conjoint Analysis
In “Ellipsoidal Methods for Adaptive Choice-Based Conjoint Analysis,” Sauré and Vielma study adaptive questionnaire design for choice-based conjoint analysis, a popular survey-based preference elicitation method used in market research. The authors adopt a Bayesian approach to model consumer preferences, based on their characterization via partworth vectors, and formulate the problem of finding the optimal adaptive questionnaire (thus allowing the next question asked to a respondent to depend on the respondent’s answers to previous questions). Because said formulation is intractable for practical instances of the problem, the authors develop an integer-programming-based adaptive questionnaire that minimizes the D-error (a measurement of the accuracy of the partworth vector estimate) while approximating the posterior distribution of the partworth vector with a moment-matching multivariate normal distribution. Through numerical experiments, the authors are able to quantify the relationship between D-error minimization and heuristic guidelines promoted in extant work and to illustrate the superiority of their method.
Learning and Competition in Dynamic Contests
Firms and institutions increasingly employ contests as a way to innovate. Participants learn from one another’s successes and failures while competing for the contest’s awards. In “Designing Dynamic Contests,” Bimpikis, Ehsani, and Mostagir provide a number of design guidelines that focus on the contest’s information-disclosure policy. Critically, their analysis highlights that when agents compete and learn from one another dynamically, the success of the contest largely relies on when and what information the designer chooses to disclose about their relative progress toward the end goal.
How Consumers Screen Products
Consumers generally do not know about, much less evaluate, the hundreds or thousands of product variations available to them in a category. In many situations, including online shopping, they use product features to sequentially screen the set of available alternatives. In “Randomized Algorithms for Lexicographic Inference,” R. Kohli, Boughanmi, and V. Kohli describe a method for inferring lexicographic rules from ranking, choice, or paired comparison data. They show that the inference problem is computationally hard (it generalizes the linear ordering problem) and propose a randomized algorithm that explicitly uses statistical distributions, the parameters of which are obtained by maximizing a likelihood function. The expected value of the solution obtained by the randomized algorithm is a function of the likelihood value and has a nontrivial lower bound. In an empirical test, the algorithm found screening rules that predicted consumer preferences substantially better than several competing methods.
Scheduling Pedestrian Flows during the Great Islamic Pilgrimage to Mecca
By Islam’s principle, each adult Muslim who is physically and financially capable is obligated to perform Hajj—Pilgrimage to Mecca—once in his lifetime. With millions of faithful pilgrims, the Hajj is one the largest annual pedestrian events in the world. It is also a stress test to the authority’s ability to protect pilgrims' safety throughout the multiday rituals. In “A Pilgrim Scheduling Approach to Increase Safety during the Hajj,” Haase, Kasper, Koch, and Müller describe the combined optimization and simulation approach used in the years 2007–2014 and 2016–2017 to plan safe pilgrim flows between the ritual sites and pilgrim camps.
Grid Design for Markov Chain Approximation in Option Pricing and Hedging
Markov chain approximation is a general method for option pricing and hedging in Markovian models with continuous-state spaces. A key issue for its efficiency is how to design the grid for the Markov chain. In “Analysis of Markov Chain Approximation for Option Pricing and Hedging: Grid Design and Convergence Behavior,” Zhang and Li investigate how grid design affects the convergence behavior of barrier and European options in general diffusion models. They obtain sharp estimates for the convergence rate of option price, delta, and gamma and develop two principles that are sufficient and necessary for designing nonuniform grids that can achieve second-order convergence. They further propose a novel class of nonuniform grids that ensure that convergence is not only second order but also smooth. This allows extrapolation to be applied to achieve even higher convergence rate. Their grids enable the continuous time Markov chain approximation method to price and hedge a large number of options with different strikes fast and accurately.
How Measures of Model Risk Affect Conservative Risk Management
Any quantitative model (e.g., in financial risk management) must rely on modeling assumptions and is thus prone to model risk. In “Technical Note—The Joint Impact of F Divergences and Reference Models on the Contents of Uncertainty Sets,” Kruse, Schneider, and Schweizer reassess the “robustness” approach to model risk. In this approach, model risk is defined in a nonparametric way. Calculations under a reference model are contrasted against worst-case scenarios over all alternative models within a maximal “divergence” from the reference model. The choices of the reference model and the divergence measure jointly shape the uncertainty set—and thus, the perceived severity of model risk. The authors argue that there is no single divergence measure that is suitable for all reference models. Instead, when choosing a divergence measure, properties of the reference model should be taken into account. This concerns in particular assumptions on tail risk made under the reference model.
Assortment Planning with Product Fixed Costs
In “Tractable Approximations for Assortment Planning with Product Costs,” Kunnumkal and Martínez-de-Albéniz study the assortment planning problem under the multinomial logit demand model when there are product-specific fixed costs. The objective of the assortment planning problem is to determine the set of products to offer to maximize the expected profit obtained from a customer. Although the presence of product-specific fixed costs makes the assortment planning problem NP-hard, the authors propose a relaxation that provides an upper bound on the optimal expected profit. They show that their upper bound can be computed efficiently and that it has attractive theoretical guarantees, especially when products are homogeneous in terms of preference weights. The authors also show numerically that their method has good practical performance and yields bounds that are competitive with respect to other approaches in the literature.
Ration Gaming in a Chinese Supermarket
Lee et al. (1997) theorized that stores game the means by which inventory is rationed, jockeying for stock in times of scarcity. Furthermore, they theorized that this ration gaming exacerbates the bullwhip effect. In “Ration Gaming and the Bullwhip Effect,” Bray, Yao, Duan, and Huo confirm both hypotheses with a supply chain sample from one distribution center (DC) and 72 grocery stores. The authors show that the stores strategically avoid upstream stock outs, ordering 31% more often when the DC’s inventory level is in the bottom decile. Also, they report that this ration gaming accounts for approximately 11% of the bullwhip effect. The authors estimate the causal effect of ration gaming on the bullwhip effect with a dynamic discrete choice model of the supply chain.
On the Interface of Operations and Finance: Dynamic Inventory Management with Trade Credit
How does a firm manage inventory when it receives trade credit from its upstream supplier and offers trade credit to its downstream customer? To maximize its end-of-horizon working capital, the firm needs to trade off standard inventory costs and cash-related costs, such as deficit penalty and interest gain. The problem is challenged by the curse of dimensionality when trade credit length grows longer relative to the replenishment period. In “Technical Note—Managing Inventory for Firms with Trade Credit and Deficit Penalty,” Luo and Shang consider a simplified model in which a myopic policy is optimal under nondecreasing demand. The heuristic policies the authors develop generalize the classic base-stock policy and resemble practical working capital management. The policy parameters have closed-form expressions, which show the impact of demand and cost parameters on the inventory decision. Our study assesses the value of considering financial flows when a firm makes the inventory decision and reveals insights consistent with empirical findings.
A Facility Location Model Involving Rational Customers
In an optimization process, firms or institutions frequently overlook the impact of their decisions on a population of users, thus leading to a poor performance of the system. This flaw can be corrected by explicitly embedding the rational reaction of the users into the mathematical framework. However, the resulting complexity yields formulations that cannot be solved by commercial software, hence the need for mathematical tools adapted to this situation. In “Competitive Facility Location with Selfish Users and Queues” by Dan and Marcotte, a step in that direction is achieved for a facility location problem where users individually maximize their utility, taking into account travel time, queueing delays, and the probability of accessing the service provided at one of the facilities. The techniques that the authors developed are not specific to this model (i.e., they can be adapted to other applications sharing similar properties).
Travel Time Estimation in the Age of Big Data
The need to understand complex city traffic patterns has led to an increase in the amount and the diversity of traffic data being collected. For instance, taxi companies in an increasing number of major cities have started recording metadata for every individual car ride, such as its origin, destination, and travel time. In “Travel Time Estimation in the Age of Big Data,” Bertsimas, Delarue, Jaillet, and Martin, by leveraging network optimization insights, extract accurate travel time estimations from such origin-destination data. For example, the authors reconstruct traffic patterns at the scale of Manhattan using only origin-destination information for a few hundred thousand taxi trips, without any information about vehicles’ individual paths.
Trade-off Between Demand Fulfillment and Manufacturing Cost
Process flexibility, as an important manufacturing strategy to hedge against demand uncertainty, has been widely adopted by many manufacturing industries, such as automobile, textile, electronics, and semiconductor. In “Optimal Design of Process Flexibility for General Production Systems,” Chen, Ma, Zhang, and Zhou propose a new algorithm for constructing flexibility structures. Whereas most existing literature studies balanced and symmetrical systems in which the number of plants equals the number of products and demands are i.i.d., this work relaxes these assumptions and is applicable to a very general class of production systems. The proposed construction introduces a simple yet effective thresholding scheme to the natural weighted probabilistic construction and is proven to be asymptotically optimal. Roughly speaking, for a general production system with highly heterogeneous demands, even with very limited flexibility/cost, the authors' design performs almost as well as fully flexible structures.
On the Minimum Chordal Completion Polytope
A graph is chordal if every cycle of length at least four contains a chord—that is, an edge connecting two nonconsecutive vertices of the cycle. Several classical applications in sparse linear systems, database management, computer vision, and semidefinite programming can be cast as finding the minimum number of edges to add to a graph so that it becomes chordal, known as the minimum chordal completion problem. In “On the Minimum Chordal Completion Polytope,” Bergman, Cardonha, Cire, and Raghunathan propose a novel integer programming formulation for the problem and investigate its polyhedral structure. The authors introduce several families of facet-defining inequalities and identify conditions in which they are facet defining. Numerical studies combining heuristic separation methods indicate that the new approach substantially outperforms existing methods for the problem, solving many instances for the first time.
How Good Are Uniform Copayments in Increasing Market Consumption?
Consider a central planner with a limited budget charging taxes and allocating copayment subsidies to competing producers of a commodity, with the goal of maximizing its aggregate consumption (e.g., the Global Fund trying to increase the consumption of artemisinin combination therapy antimalarials in Africa). The policy most frequently implemented allocates uniform copayments (i.e., every firm gets the same copayment), even if some firms are more efficient than others. The central question in “Near-Optimality of Uniform Copayments for Subsidies and Taxes Allocation Problems” is to evaluate the worst possible efficiency loss induced by uniform copayments. Levi, Perakis and Romero show that uniform copayments are guaranteed to induce a large fraction of the market consumption induced by the optimal policy. This is important, because they also show that the optimal policy is hard to implement. In summary, the authors' results provide theoretical support to continue the use of the simple uniform copayments policy in practice.
Comparisons-based Inference on the Optimal Solution Under Input Model Risk
In “Input–Output Uncertainty Comparisons for Discrete Optimization via Simulation,” Song and Nelson discuss how selecting the optimal policy using simulation is subject to input model risk when input models that mimic real-world randomness in the simulation have estimation error due to finite sample sizes. Instead of trying to find the optimal solution under unknown real-world input distributions by taking a conservative stance or with low statistical guarantee, the input–output uncertainty comparisons (IOU-C) procedure finds a set of solutions that cannot be separated from the best given the resolution decided by the finite sample sizes. The common-input-data (CID) effects measure how differently solutions are affected by the common estimated input models. When CID effects of two systems are positively correlated, the comparison becomes easier than estimating the performance measures of two systems precisely under input model risk; the IOU-C procedure takes advantage of the CID effects to develop a sharp comparison and thereby provides a small subset even in the presence of input model risk.
Analyzing Heuristic Policies in Complex Dynamic Programs
In the analysis of complex stochastic dynamic programs, we often seek strong theoretical guarantees on the suboptimality of heuristic policies. A common technique for obtaining performance bounds in the approximation algorithms literature is “hindsight” (or “offline”) analysis, which considers a decision maker who has perfect information about the outcomes of all uncertainties in advance. In many problems, however, this information is quite valuable and leads to weak bounds. In “Approximations to Stochastic Dynamic Programs via Information Relaxation Duality,” Balseiro and Brown study information relaxation duality, which involves incorporating a penalty for perfect information. The primary application of information relaxation duality to this point has been as a computational method for evaluating heuristic policies. The authors show how to use this approach to derive theoretical guarantees on the performance of heuristic policies in complex dynamic programs. The paper introduces a general recipe involving an approximate value function that generates both a heuristic policy and a penalty for the perfect information analysis. The authors apply the approach to three challenging problems: (1) stochastic knapsack problems, (2) stochastic scheduling on parallel machines, and (3) sequential search problems with recall. In each problem, the method leads to analytical bounds on the suboptimality of the corresponding heuristic policy, which, in turn, implies asymptotic optimality of the policy in specific regimes of interest.
