Knowledge that Transforms

Performance of a queueing system with scheduled arrivals A scheduled arrival sequence is one in which customers are scheduled to arrive at constant interarrival times, but each customer’s actual arrival time is perturbed from her scheduled arrival time by a random perturbation. In “Stability of a Queue Fed by Scheduled Traffic at Critical Loading”, V.F. Araman and P.W. Glynn consider a single server queue with deterministic service times in which customers arrive following a scheduled arrival process. Unlike a queue fed by renewal traffic, this queue is shown to be stable even when the utilization is equal to one. It is also shown that for finite mean perturbations, a necessary and sufficient condition for stability is when the positive part of the perturbation has bounded support, with no requirement on the negative part of the perturbation. Perhaps surprisingly, this criterion is not reversible, in the sense that such a queue can be stable for a scheduled traffic process in forward time, but unstable for the time-reversal of the same traffic process.

Advancing Risk Assessment: New Ways To Compute Quantile Aggregation This issue features a pivotal study on quantile aggregation amid dependence uncertainty, an area critical to finance, risk management, and statistics. The authors introduce “convolution bounds,” derived from a recent inf-convolution formula of quantiles and related risk measures. The obtained analytical tools unify existing results and enhance the understanding of quantile methods by providing general, sharp, and computationally efficient solutions. The results offer insights into the extremal dependence structures, with several implications in risk management and economic analysis applications. For more detailed insights, read the full paper, “Convolution Bounds on Quantile Aggregation” (reference: [insert reference]).

On the Difficulty of Pricing Routes for Stochastic Vehicle Routing Problems Many approaches exist for dealing with the uncertainty in the vehicle routing problem with stochastic demands (VRPSD), but the most popular approach models the VRPSD as a two-stage stochastic program where a recourse policy prescribes actions that handle when the realized demands exceed the vehicle capacity. Similarly to other VRP variants, some state-of-the-art algorithms for the VRPSD use set-partitioning formulations that generate variables (routes) via a pricing problem. All of these algorithms, however, have strong assumptions on the probability distribution of customer demands, a simplification that might not be realistic in some applications. In “Hardness of Pricing Routes for Two-Stage Stochastic Vehicle Routing Problems with Scenarios,” Ota and Fukasawa examine the challenges associated with solving the pricing problem of the VRPSD when the customer demands are given by scenarios. They demonstrate that the VRPSD pricing problem is strongly NP-hard for a wide variety of recourse policies and route relaxations. This highlights the difficulty of developing efficient pricing algorithms for the VRPSD with scenario-based demand models.

Handling Heterogeneous Machines in Malleable Scheduling Parallelization is an important and widespread technique to speed up the completion of time-critical tasks, not only in high-speed computing, but also in operations planning in production and logistics. A fundamental model in this context is that of malleable jobs, each of which can be assigned to a subset of machine for parallel processing. In “Assigning and Scheduling Generalized Malleable Jobs Under Submodular or Subadditive Processing Speeds,” Fotakis, Matuschke, and Papadigenopoulos go beyond the by now well-understood identical-machine setting in malleable scheduling and develop algorithmic approaches for scheduling malleable jobs under various discrete concavity assumptions on the joint processing speeds of the assigned (possibly very heterogeneous) machines. They show that under these assumptions, the task of finding a schedule of small makespan can be reduced to that of finding an assignment with small maximum machine load. For this latter problem, numerous efficient approximation algorithms are derived and their practical performance explored in a computational experiments. These results indicate that the computational challenges posed by parallelization in heterogeneous environments can indeed be overcome, enabling the optimization of heavily parallelized schedules in the aforementioned applications.

In the paper, “The Analytics of Robust Satisficing: Predict, Optimize, Satisfice, Then Fortify,” published in Operations Research, authors Sim, Tang, Zhou, and Zhu introduce a novel approach to decision making under uncertainty. Their method, termed “estimation-fortified robust satisficing,” leverages advanced predictive and prescriptive analytics to optimize decisions where traditional models falter due to risk ambiguity and estimation uncertainties. This approach not only enhances the resilience of decisions against unforeseen variations but also consistently outperforms conventional predictive methods in scenarios characterized by sparse data. This significant advancement promises to fortify decision-making processes in critical sectors such as finance and operations management, offering a new paradigm in handling the inherent uncertainties of real-world systems.

Shape-Constrained Regression Using Algebraic Techniques How can one fit a multivariate polynomial to data points in such a way that this polynomial is guaranteed to have certain shape constraints, such as convexity or monotonicity in some of its variables? In “Shape-constrained regression using sum-of-squares polynomials,” M. Curmei and G. Hall propose a hierarchy of semidefinite programs to address this problem. They show that polynomial functions that are optimal to any fixed level of our hierarchy form a consistent estimator of the underlying shape-constrained function, which generates the data points. As a by-product of the proof, they establish that sum-of-squares-convex polynomials are dense in the set of polynomials that are convex over an arbitrary box. They further demonstrate the performance of the regressor for the problem of computing optimal transport maps in a color transfer task and that of estimating the optimal value function of a conic program. A real-time application of the latter problem to inventory management contract negotiation is presented.

Personalized prices can boost revenue, but they increasingly draw fire for hidden discrimination. A new study, “Dynamic Pricing with Fairness Constraints,” by Maxime C. Cohen, Sentao Miao, and Yining Wang, shows that firms can learn demand while staying fair at the same time. The authors embed two complementary notions of fairness into the classic learning-and-earning problem. The first, price fairness, limits price gaps across customer groups and over time, whereas the second, demand fairness, keeps realized demand shares balanced. To enforce price fairness, the authors design FaPU, an infrequently updated upper confidence bound algorithm that respects both group and temporal limits while securing near-optimal regret and matching lower bounds. For demand fairness, they propose FaPD, a primal-dual learner that meets aggregate demand quotas with high probability and the same near-optimal regret rate. Beyond providing tight theoretical analyses, the paper quantifies the “price of fairness” and outlines extensions to non-stationary markets, offering regulators and practitioners evidence that equity and profitability can coexist in algorithmic pricing.

The clearing of nonconvex markets poses unique challenges. The canonical market clearing, a Walrasian equilibrium, needs not exist when participants’ preferences display nonconvexities, for example, due to technical constraints. Then market clearing prices might not exist, and side payments may be required to compensate losses. Electricity markets are a prime example. Market operators in the United States use heuristic pricing rules to compute market prices; the magnitude of the side payments, potential lost opportunity costs, and the quality of network congestion signals in prices have all become a concern. In “Pricing Optimal Outcomes in Coupled and Non-Convex Markets: Theory and Applications to Electricity Markets,” Ahunbay, Bichler, and Knörr propose a multiobjective framework for pricing such markets. The design goals are shown to be inherently conflicting but may be balanced against each other through traditional methods in multiobjective optimization. Pricing rules used in practice are identified as prices for a suitably convexified market, which motivates a novel pricing method that drastically reduces side payments while maintaining congestion signals in realistic test cases.

A Review of Inverse Optimization In recent years, there has been an explosion of interest in the mathematics and applications of inverse optimization. Unlike traditional optimization, which seeks to compute optimal decisions given an objective and constraints, inverse optimization takes decisions as input and determines an objective and/or constraints that render these decisions approximately or exactly optimal. In “Inverse Optimization: Theory and Applications,” Chan, Rafid, and Zhu provide a comprehensive review of both the methodological and application-oriented literature. Specifically, the authors consolidate various model properties, reformulation techniques, and computational methods of different classes of inverse optimization problems. The authors also review a wide range of application areas that include, but are not limited to, transportation, logistics, healthcare, and energy systems. The paper concludes with several major directions for future research.

We propose a data-driven portfolio selection model that integrates side information, conditional estimation, and robustness using the framework of distributionally robust optimization. Conditioning on the observed side information, the portfolio manager solves an allocation problem that minimizes the worst-case conditional risk-return tradeoff, subject to all possible perturbations of the covariate-return probability distribution in an optimal transport ambiguity set. Despite the nonlinearity of the objective function in the probability measure, we show that the distributionally robust portfolio allocation with a side information problem can be reformulated as a finite-dimensional optimization problem. If portfolio decisions are made based on either the mean-variance or the mean-conditional value-at-risk criterion, the reformulation can be further simplified to second-order or semidefinite cone programs. Empirical studies in the U.S. equity market demonstrate the advantage of our integrative framework against other benchmarks. Funding: The material in this paper is based on work supported by the Air Force Office of Scientific Research [Award FA9550-20-1-0397]. Additional support is gratefully acknowledged from the National Science Foundation [Grants 1915967, 1820942, and 1838676], the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2016-05208], and the China Merchant Bank. V. A. Nguyen gratefully acknowledges the generous support from the Chinese University of Hong Kong [Improvement on Competitiveness in Hiring New Faculties Funding Scheme] and the Chinese University of Hong Kong [Direct Grant 4055191]. S. Wang is partially supported by the National Natural Science Foundation of China [Grant 72371022]. Finally, this research was enabled in part by support provided by Compute Canada. Supplemental Material: The computer code and data that support the findings of this study and the online appendix are available within this article’s supplemental material at https://doi.org/10.1287/opre.2021.0243 .