In This Issue
The Benefits of a Simple Procurement Mechanism
It is ubiquitous in procurement practice by private industries or government agencies that buyers are concerned about not only the costs, but also such noncost attributes as completion time or quality. In “Procurement with Cost and Noncost Attributes: Cost-Sharing Mechanisms,” Gupta, Wang, Dawande, and Janakiraman formulate such procurement problems as a two-dimensional mechanism design problem and recognize the possibility that contractors may “manipulate” the noncost attributes of the procurement. They examine the family of cost-sharing mechanisms, under which the winning contractor is selected via a second-price auction and is asked to reimburse a prespecified fraction of the buyer’s disutility cost inflicted by the delivered noncost attribute. The authors show that the optimal cost-sharing mechanism can serve as a nonmanipulable, easy-to-implement, and near-optimal solution to the buyer’s procurement problem.
The Effect of Social Preferences on Sales and Operations Planning
Sales and operations planning processes are used to align production quantities and customer demand. Two key activities of these processes are demand planning and production planning, which are often assigned to individuals in different departments. In “The Effect of Social Preferences on Sales and Operations Planning,” Papier and Thonemann analyze the role of social preferences (altruism, inequality aversion, and competitive pressure) and monetary incentives in motivating demand planners to invest effort in forecasting that benefits the production planners. Their results indicate that social preferences can be used to incentivize demand planners to invest effort and that this effect is anticipated by production planners. The resulting more accurate demand forecasts and adapted production quantities result in higher company profit. They also provide an optimization model for optimally allocating investments to financial incentives and social preference building.
A New Approach for Structural Analysis of Operations Models with Substitutability Structures
In many operations models with substitutability structures, one often ends up with parametric optimization models that maximize submodular objective functions, and it is desirable to derive structural properties including monotone comparative statics of the optimal solutions or preservation of submodularity under the optimization operations. Yet, this task is challenging because the classical and commonly used results in lattice programming, applicable to optimization models with supermodular objective function maximization, do not apply. Using a key concept in discrete convex analysis, in “M♮-convexity and Its Applications in Operations,” Chen and Li establish conditions under which the optimal solutions are nonincreasing in the parameters and the preservation property holds for parametric maximization models with submodular objectives, together with the development of several new fundamental properties of M♮-convexity. Their approach is powerful as demonstrated by applications in a classical multiproduct stochastic inventory model and a portfolio contract model.
Revenue Management for Online Advertising: A Holistic Approach
Publishers of online advertising sell ad resources in both up-front market and spot market. In the up-front market, advertisers enter contracts with publishers for a guaranteed amount of exposures. Besides ensuring the fulfillment of contracts, publishers also have the incentive to improve the effectiveness of advertising for building long-term relationship with advertisers. When it comes to ad delivery, publishers therefore often give priority to guaranteed contracts and then sell the leftover in the spot market. Such an approach risks significant loss of revenue due to the lack of coordination between the two selling channels. In “Integrated Ad Delivery Planning for Targeted Display Advertising,” Shen, Li, Chen, and Pan present an integrated approach for ad resource allocation. The approach models the problem as a distributionally robust chance-constrained program. They propose effective approximation and transformation for the model and design efficient algorithms to solve the problem. Experiments with real data show that their approach generates more revenue while fulfilling the guaranteed contracts and ensuring advertising effectiveness.
Curse of a Favorable Opportunity: Strategic Choice of Investment Size and Timing with Bayesian Learning
Motivated by challenges faced by firms entering an unknown market, “Competitive Investment with Bayesian Learning: Choice of Business Size and Timing,” by Sunar, Yu, and Kulkarni studies a strategic investment problem in a leader-follower setting where the favorableness of the market is unknown to firms. A leader invests first by choosing its investment size. Then, in a continuous-time Bayesian setting, a competitive follower dynamically learns about the favorableness of the market by observing the leader’s earnings and chooses its investment size and timing. A distinctive feature of the considered model is that firms choose their investment sizes, and thus the follower’s observations about the favorableness of the market can be censored due to the leader’s investment size choice. It is generally accepted that if there is an increase in the likelihood of a favorable market, then the firm’s expected discounted profit and its investment size increase. The article shows that, contrary to this common understanding, the leader’s equilibrium expected discounted profit and equilibrium investment size can strictly decrease when there is an increase in the likelihood of a favorable market.
Selling Ads via First-Look Contracts
Billions of dollars’ worth of online advertising is sold via auctions and via contracts. A key challenge in this market is how to structure these contracts and coordinate the ad sales via different channels. In “Deals or No Deals: Contract Design for Online Advertising,” Kim, Mirrokni, and Nazerzadeh present a formal study of first-look and preferred deals, which generalize traditional reservation contracts and are suitable for advertisers with advanced targeting capabilities. Under these deals, one or more advertisers gain priority access to an inventory of impressions before others and can choose to purchase in real time. They propose algorithms that guarantee constant fractions of the revenue that can be obtained from combinations of deals and auctions. In numerical simulation using data from Google's ad exchange platform, these algorithms obtain 85%–96% of the optimal achievable revenue.
Using Machine Learning and Integer Optimization to Help Improve Employment Outcomes of Resettled Refugees
Every year, tens of thousands of refugees are resettled to dozens of host countries. Although there is growing evidence that the initial placement of refugee families profoundly affects their lifetime outcomes, there have been few attempts to optimize resettlement decisions of refugee agencies. In “Placement Optimization in Refugee Resettlement,” Ahani, Andersson, Martinello, Teytelboym, and Trapp use machine learning to estimate the likelihood of employment, a key indicator of integration for refugees, and combine these estimates with integer optimization to develop refugee family-to-community placement recommendations for a refugee resettlement agency in the United States. They embed these technologies in a decision support tool known as Annie™ MOORE, the world's first software for optimizing refugee resettlement decisions. Annie™ enables resettlement staff to visually interact with the solutions to fine tune the developed recommendations, thereby achieving superior outcomes for refugees.
Operations Research Journal 1952-2019
In “Operations Research: Topics, Impact and Trends from 1952–2019,” Calma, Ho, Shao, and Li retrospectively look at 68 years of publication of the Operations Research journal. Using 5,440 journal articles, they highlight the top contributing countries and authors and top research methods and problems investigated. Mathematical programming is the most common research method, whereas inventory is the most investigated problem. Investigations related to pricing are growing significantly. The United States, Canada, and the United Kingdom publish the most papers, with the United States and Canada having similar publication profiles per capita. Inventory is the most popular research problem studied by North American, Asian, and Middle Eastern countries, whereas European countries focus on scheduling problems. Network visualizations of the journal’s last 10 years show dynamic programming as the most used method and pricing as the most studied problem. Coauthor networks on collaborations on both dynamic programming and pricing are also shown.
Sequential Recommendation Under the Multinomial Logit Model with Impatient Customers
In many applications, customers incrementally view a subset of offered products and make purchasing decisions before observing all the offered products. In this case, the decision faced by a firm is not only what assortment of products to offer, but also in what sequence to offer the products. In “Assortment Optimization and Pricing Under the Multinomial Logit Model with Impatient Customers: Sequential Recommendation and Selection,” Gao, Ma, Chen, Gallego, Li, Rusmevichientong, and Topaloglu propose a choice model where each customer incrementally view the assortment of products in multiple stages, and their patience level determines the maximum number of stages. Under this choice model, the authors develop a polynomial-time algorithm that finds a revenue-maximizing sequence of assortments. If the sequence of assortments is fixed, the problem of finding revenue-maximizing prices can be transformed to a convex program. They combine these results to develop an effective approximation algorithm when both the sequence of assortments and prices are decision variables.
Finite-Time Behavior of Nested Partitions Method for Global Optimization
In the previous article “Nested Partitions Method for Global Optimization,” Shi and Ólafsson propose the nested partitions (NP) method for global optimization. The NP method takes a global perspective and provides a setting for an efficient combination of global and local search. The motivation behind this method is that some parts of the feasible region may be most likely to contain the global optimal solution. Hence, this method considers them promising regions and concentrates the computational effort in these promising ones. Two of their main results are the properties of the global convergence of the NP method stated in Theorems 3 and 4, respectively. In particular Theorem 3 provides a hitting-probability-based formula to represent the bound of the expected number of convergence iterations, and Theorem 4 evaluates its expected numeric bound of convergence iterations under a particular case. In “Technical Note—On Nested Partitions Method for Global Optimization,” Wu proves that both theorems are fundamentally incorrect and rectify them in this study.
Impact of Redundancy in the Performance of Computing Systems
The main motivation to investigate redundancy models comes from empirical evidence suggesting that redundancy can help improve the performance of real-world applications. Although there are several variants of a redundancy-based system, the general notion of redundancy is to create multiple copies of the same job that will be sent to a subset of servers. By allowing for redundant copies, the aim is to minimize the system latency by exploiting the variability in the queue lengths and the capacity of the different servers. In ”On the Stability of Redundancy Models,” by Anton, Ayesta, Jonckheere, and Verloop the stability condition of redundancy multiserver systems is investigated. Several popular scheduling disciplines are considered, such as first-come-first-serve (FCFS), processor sharing (PS), and random order of service (ROS) and show that whereas with ROS the performance is not reduced, with both PS and FCFS the performance can severely degrade.
Approximating Nonstationary Stochastic Systems with Rapidly Fluctuating Arrivals
In many operations management settings, the arrival process to the system exhibits clear nonstationarities. These nonstationarities may arise as a consequence of time-of-day effects, day-of-week effects, seasonalities, or stochastic fluctuations in the arrival rate. Tools that are developed for performance prediction and decision making when systems are stationary may not be valid in the nonstationary environment. In ”Technical Note--Approximating Systems Fed by Poisson Processes with Rapidly Changing Arrival Rates,” by Zheng, Honnappa, and Glynn, the authors provide a generic, closed-form, and simple approximation tool for when the nonstationarities are caused by rapid fluctuations in the arrival processes.
A Framework for Private Sequential Learning
Can we learn privately and efficiently through sequential interactions? In “Private Sequential Learning,” by Tsitsiklis, K. Xu, and Z. Xu a private learning model is formulated to study an intrinsic tradeoff between privacy and query complexity in sequential learning. The formulation involves a learner who aims to learn a scalar value by sequentially querying an external database and receiving binary responses. In the meantime, an adversary observes the learner’s queries, although not the responses, and tries to infer from them the scalar value of interest. The objective of the learner is to obtain an accurate estimate of the scalar value using only a small number of queries while simultaneously protecting his or her privacy by making the scalar value provably difficult to learn for the adversary. The main results provide tight upper and lower bounds on the learner’s query complexity as a function of desired levels of privacy and estimation accuracy. The authors also construct explicit query strategies whose complexity is optimal up to an additive constant.
Transforming Dynamic Optimization Problems for Enhanced Computational Efficiency
Dynamic programming is one of the core algorithms for solving optimization problems in operations research, economics, finance, computer science, and numerous other fields. Although the theory itself is relatively straightforward, implementation can be computationally expensive, inhibiting application to interesting and realistic problems. In “Dynamic Programming Deconstructed: Transformations of the Bellman Equation and Computational Efficiency,” by Ma and Stachurski the research considers a variety of transformations that can be applied to optimization problems and the key equations associated with the dynamic programming algorithm. It investigates the range of possible transformations, clarifies their links with optimality, and applies specific transformations to generate large speed gains in high-dimensional problems. Several economic applications are considered.
Sensitivities for Stochastic Optimization
In optimization, sensitivities of optimal values with respect to the data of the problem are of practical as well as theoretical interest. In the paper “Envelope Theorems for Multistage Linear Stochastic Optimization,” Terça and Wozabal propose a framework to compute derivatives of optimal values for a certain class of stochastic optimization problems. The results make use of classical envelope theorems and almost sure smoothness properties for optimal values of linear optimization problems, which are derived using tools from real algebraic topology. The authors show that derivatives can be sampled based on solutions obtained from stochastic dual dynamic programming and discuss two numerical case studies, demonstrating that the approach is superior, both in terms of accuracy as well as computationally, to naïve methods of computing derivatives that are based on difference quotients.
Out-of-Sample Properties of Solutions of Distributionally Robust Optimization Problems
In “Calibration of Distributionally Robust Empirical Optimization Models,” Gotoh, Kim, and Lim study the statistical properties of -divergence distributionally robust optimization with concave rewards. They show that worst-case sensitivity of the expected reward to deviations from the nominal is equal to the in-sample variance and that significant out-of-sample variance (sensitivity) reduction is possible with little impact on the mean if the robustness parameter is properly chosen. The authors also explain theoretically why the out-of-sample expected reward of robust solutions can sometimes “beat” that of sample average optimization, a phenomenon that has been observed empirically, and that the difference is typically small. This paper highlights that robust solutions are not “too conservative” if both mean and variance (sensitivity) are considered when selecting the size of the uncertainty set (e.g., via the bootstrap).
