Search

The paper studies generalization of the secretary problem, where decisions do not have to be made immediately upon applicants' arrivals. After arriving, each applicant stays in the system for some (random) amount of time and then leaves, whereupon the algorithm has to decide irrevocably whether to select this applicant or not. The arrival and waiting times are drawn from known distributions, and the decision maker's goal is to maximize the probability of selecting the best applicant overall. The paper characterizes the optimal policy for this setting, showing that when deciding whether to select an applicant, it suffices to know only the time and the number of applicants that have arrived so far. Furthermore, the policy is monotone nondecreasing in the number of applicants seen so far, and, under certain natural conditions, monotone nonincreasing in time. Furthermore, when the number of applicants is large, a single threshold policy is almost optimal. We study a generalization of the secretary problem, where decisions do not have to be made immediately upon applicants' arrivals. After arriving, each applicant stays in the system for some (random) amount of time and then leaves, whereupon the algorithm has to decide irrevocably whether to select this applicant or not. The arrival and waiting times are drawn from known distributions, and the decision maker's goal is to maximize the probability of selecting the best applicant overall. Our first main result is a characterization of the optimal policy for this setting. We show that when deciding whether to select an applicant, it suffices to know only the time and the number of applicants that have arrived so far. Furthermore, the policy is monotone nondecreasing in the number of applicants seen so far, and, under certain natural conditions, monotone nonincreasing in time. Our second main result is that when the number of applicants is large, a single threshold policy is almost optimal. Funding: A. Psomas is supported in part by the National Science Foundation [Grant CCF-2144208], a Google Research Scholar Award, and by the Algorand Centres of Excellence program managed by Algorand Foundation. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2476. [ABSTRACT FROM AUTHOR]

This paper presents the first comprehensive study of a data-driven formulation of the distributionally robust second order stochastic dominance constrained problem (DRSSDCP) that hinges on using a type-1 Wasserstein ambiguity set. It is, furthermore, for the first time shown to be axiomatically motivated in an environment with distribution ambiguity. We formulate the DRSSDCP as a multistage robust optimization problem and further propose a tractable conservative approximation that exploits finite adaptability and a scenario-based lower bounding problem. We then propose the first exact optimization algorithm for this DRSSDCP. We illustrate how the data-driven DRSSDCP can be applied in practice on resource-allocation problems with both synthetic and real data. Our empirical results show that, with a proper adjustment of the size of the Wasserstein ball, DRSSDCP can reach acceptable out-of-sample feasibility yet still generating strictly better performance than what is achieved by the reference strategy. Optimization with stochastic dominance constraints has recently received an increasing amount of attention in the quantitative risk management literature. Instead of requiring that the probabilistic description of the uncertain parameters be exactly known, this paper presents a comprehensive study of a data-driven formulation of the distributionally robust second order stochastic dominance constrained problem (DRSSDCP) that hinges on using a type-1 Wasserstein ambiguity set. This formulation allows us to identify solutions with finite sample guarantees and solutions that are asymptotically consistent when observations are independent and identically distributed. It is, furthermore, shown to be axiomatically motivated in an environment with distribution ambiguity. Leveraging recent results in the field of robust optimization, we further formulate the DRSSDCP as a multistage robust optimization problem and further propose a tractable conservative approximation that exploits finite adaptability and a scenario-based lower bounding problem, both of which can reduce to linear programs under mild conditions. We then propose, to the best of our knowledge, the first exact optimization algorithm for this DRSSDCP, the efficiency of which is confirmed by our numerical results. Finally, we illustrate how the data-driven DRSSDCP can be applied in practice on resource-allocation problems with both synthetic and real data. Our empirical results show that, with a proper adjustment of the size of the Wasserstein ball, DRSSDCP can reach "acceptable" out-of-sample feasibility yet still generating strictly better performance than what is achieved by the reference strategy. Funding: This research was partially supported by the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2016-05208], the Canada Research Chair program [Grant 950-230057], and Groupe d'études et de recherche en analyse des décisions, and it was enabled in part by support provided by Calcul Quebec (https://www.calculquebec.ca/en/) and the Digital Research Alliance of Canada (https://www.alliancecan.ca/). Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.2387. [ABSTRACT FROM AUTHOR]

This paper builds a bridge between two area in optimization and machine learning by establishing a general connection between Wasserstein distributional robustness and variation regularization. It helps to demystify the empirical success of Wasserstein distributionally robust optimization and devise new regularization schemes for machine learning. Wasserstein distributionally robust optimization (DRO) is an approach to optimization under uncertainty in which the decision maker hedges against a set of probability distributions, specified by a Wasserstein ball, for the uncertain parameters. This approach facilitates robust machine learning, resulting in models that sustain good performance when the data are to some extent different from the training data. This robustness is related to the well-studied effect of regularization. The connection between Wasserstein DRO and regularization has been established in several settings. However, existing results often require restrictive assumptions, such as smoothness or convexity, that are not satisfied by many important problems. In this paper, we develop a general theory for the variation regularization effect of the Wasserstein DRO—a new form of regularization that generalizes total-variation regularization, Lipschitz regularization, and gradient regularization. Our results cover possibly nonconvex and nonsmooth losses and losses on non-Euclidean spaces and highlight the bias-variation tradeoff intrinsic in the Wasserstein DRO, which balances between the empirical mean of the loss and the variation of the loss. Example applications include multi-item newsvendor, linear prediction, neural networks, manifold learning, and intensity estimation for Poisson processes. We also use our theory of variation regularization to derive new generalization guarantees for adversarial robust learning. Funding: X. Chen is supported by the National Science Foundation [Grant IIS-1845444]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2383. [ABSTRACT FROM AUTHOR]

In recent years, there has been an increasing need to understand the complex interdependencies between critical infrastructure systems, for example, electric power, natural gas, and potable water. Whereas open-source and commercial tools for the independent simulation of these systems are well established, frameworks for cosimulation with other systems are nascent and tools for co-optimization are scarce—the major challenge being the hidden combinatorics that arise when connecting multiple-infrastructure system models. Building toward a comprehensive solution for modeling interdependent infrastructure systems, this work presents InfrastructureModels, an extensible, open-source mathematical programming framework for co-optimizing multiple interdependent infrastructures. This work provides new insights into methods and programming abstractions that make state-of-the-art independent infrastructure models composable with minimal additional effort. To that end, this paper presents the design of the InfrastructureModels framework, documents key components of the software's implementation, and demonstrates its effectiveness with three case studies on canonical co-optimization tasks arising in interdependent infrastructure systems. History: Accepted by Ted Ralphs, Area Editor for Software Tools. Funding: The work was funded by Los Alamos National Laboratory's Directed Research and Development project "The Optimization of Machine Learning: Imposing Requirements on Artificial Intelligence" and the U.S. Department of Energy's Office of Electricity Advanced Grid Modeling projects "Joint Power System and Natural Gas Pipeline Optimal Expansion Planning" and "Coordinated Planning and Operation of Water and Power Infrastructures for Increased Resilience and Reliability." This work was carried out under the U.S. DOE contract no. [DE-AC52-06NA25396]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0118) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0118). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

When and where was the study conducted: This work was done in 2018, 2019 and 2020 when Palma London was a PhD student at Caltech and Shai Vardi was a postdoc at Caltech. This work was also done in part while Palma London was visiting Purdue University, and while Reza Eghbali was a postdoctoral fellow the Simons Institute for the Theory of Computing. Adam Wierman is a professor at Caltech. Article Summary and Talking Points: Please describe the primary purpose/findings of your article in 3 sentences or less. This paper presents a framework for accelerating (speeding up) existing convex program solvers. Across engineering disciplines, a fundamental bottleneck is the availability of fast, efficient, accurate solvers. We present an acceleration method that speeds up linear programing solvers such as Gurobi and convex program solvers such as the Splitting Conic Solver by two orders of magnitude. Please include 3-5 short bullet points of "Need to Know" items regarding this research and your findings. - Optimizations problems arise in many engineering and science disciplines, and developing efficient optimization solvers is key to future innovation. - We speed up linear programing solver Gurobi by two orders of magnitude. - This work applies to optimization problems with monotone objective functions and packing constraints, which is a common problem formulation across many disciplines. Please identify 2 pull quotes from your article that best capture the novelty and impact of your research. "We propose a framework for accelerating exact and approximate convex programming solvers for packing linear programming problems and a family of convex programming problems with linear constraints. Analytically, we provide worst-case guarantees on the run time and the quality of the solution produced. Numerically, we demonstrate that our framework speeds up Gurobi and the Splitting Conic Solver by two orders of magnitude, while maintaining a near-optimal solution." "Our focus in this paper is on a class of packing problems for which data is either very costly or hard to obtain. In these situations, the number of data points available is much smaller than the number of variables. In a machine-learning setting, this regime is increasingly prevalent because it is often advantageous to consider larger and larger feature spaces, while not necessarily obtaining proportionally more data." Article Implications - Please describe in 5 sentences or less the innovative takeaway(s) of your research.This framework applies to optimization problems with monotone objective functions and packing constraints, which is a common problem formulation across many disciplines, including machine learning, inference, and resource allocation. Providing fast solvers for these problems is crucial. We exploit characteristics of the problem structure and leverage statistical properties of the problem constraints to allow us to speed up optimization solvers. We present worst-case guarantees on run-time, and empirically demonstrate speedups of two orders of magnitude. - Please describe in 5 sentences or less why your findings would be of interest to the general public.Many problems in engineering, science, math, and machine learning involve solving an optimization problem. Fast, efficient optimization solvers are key to future innovation in science and engineering. This work presents a tool to accelerate existing convex solvers, and thus can also be applied to future solvers. As the size of datasets grow it is even more crucial to have fast solvers. - Who would be the most impacted by your research (i.e. by industry, job title, consumer category).Our work impacts machine-learning researchers and optimization researchers, in industry or academia. This paper presents a black-box framework for accelerating packing optimization solvers. Our method applies to packing linear programming problems and a family of convex programming problems with linear constraints. The framework is designed for high-dimensional problems, for which the number of variables n is much larger than the number of measurements m. Given an (m × n) problem, we construct a smaller (m × ϵ n) problem, whose solution we use to find an approximation to the optimal solution. Our framework can accelerate both exact and approximate solvers. If the solver being accelerated produces an α-approximation, then we produce a (1 − ϵ) / α 2 -approximation of the optimal solution to the original problem. We present worst-case guarantees on run time and empirically demonstrate speedups of two orders of magnitude. Funding: Financial support from the National Science Foundation [Grants AitF-1637598, CNS-151894, and CPS-154471] and the Linde Institute is gratefully acknowledged. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the Special Issue on Machine Learning Methods and Applications in Large-Scale Route Planning Problems, which draws its inspiration from the academic community's positive reception of the 2021 Amazon Last Mile Routing Research Challenge. We provide a structured overview of the papers featured in this special issue, and briefly discuss other noteworthy contributions to the research challenge. Further, we point the reader to a number of peer-reviewed publications outside of this special issue that directly or indirectly emerged from the research challenge. We conclude by highlighting a number of important priorities for future research into applications of machine learning to real-world route planning problems. [ABSTRACT FROM AUTHOR]

Utility Preference Robust Optimization with Moment-Type Information Structure In some decision-making problems, information on the true utility function of the decision maker may be incomplete, which may bring potential modeling risk. In "Utility Preference Robust Optimization with Moment-Type Information Structure," Guo, Xu, and Zhang propose a maximin utility preference robust optimization model where information about the DM's preference is constructed by moment-type conditions. The authors propose a piecewise linear approximation approach to tackle the maximin problem, reformulate the approximate problem as a single mixed integer linear program, and derive error bounds for the approximate ambiguity set, the optimal value, and the optimal solutions. To examine the performance of the model and the computational schemes, they carry out extensive numerical tests and demonstrate the effectiveness of the model and efficiency of the computational methods. Utility preference robust optimization (PRO) models have recently been proposed to deal with decision-making problems where the decision-maker's true utility function is unknown and the optimal decision is based on the worst-case utility function in an ambiguity set of utility functions. In this paper, we consider the case where the ambiguity set is constructed using some moment-type conditions. We propose piecewise linear approximation of the utility functions in the ambiguity set. The approximate maximin problem can be solved directly by derivative-free methods when the utility functions are nonconcave. Alternatively, we can reformulate the approximate problem as a single mixed integer linear program (MILP) and solve the MILP by existing solvers such as Gurobi. To justify the approximation scheme, we derive error bounds for the approximate ambiguity set, the optimal value and optimal solutions of the approximate maximin problem. To address the data perturbation/contamination issues arising from the construction of the ambiguity set, we derive some stability results which quantify the variation of the ambiguity set against perturbations in the elicitation data and its propagation to the optimal value and optimal solutions of the PRO model. Moreover, we extend the PRO models to allow some inconsistencies in the process of eliciting the decision-maker's preferences. Finally, we carry out numerical tests to evaluate the performances of the proposed numerical schemes and show that the computational schemes work fairly efficiently, the PRO model is resilient against small perturbations in data (with respect to both exogenous uncertainty data and preference elicitation data), and there is a potential to improve the efficiency of the preference elicitation by incorporating an optimal selection strategy. Funding: This project is supported by Hong Kong RGC [Grant 14500620] and The Chinese University of Hong Kong start-up grant. The research of S. Guo is supported by the National Key R&D Program of China [Grant 2022YFA1004000] and the Natural Science Foundation of China [Grant 12271077]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2023.2464. [ABSTRACT FROM AUTHOR]

What is the relation between the notion of Nash equilibria and Pareto-optimal points? It is well known that Nash equilibria do not need to be Pareto optimal, and Pareto points do not need to be Nash equilibria. However, the paper "Characterizing and Computing the Set of Nash Equilibria via Vector Optimization" by Feinstein and Rudloff takes a deeper look at the relation. It is shown that it is possible to characterize the set of all Nash equilibria as the set of all Pareto-optimal solutions of a certain vector optimization problem. This is accomplished by carefully designing the objective function and the ordering cone of the vector optimization problem such that both notions coincide. This characterization holds for all noncooperative games (nonconvex, convex, linear). It opens up a new way of computing Nash equilibria, as one can now use techniques and algorithms from vector optimization to compute the set of all Nash equilibria, which is in contrast to the classical fixed-point iterations that find just a single Nash equilibrium. Nash equilibria and Pareto optimality are two distinct concepts when dealing with multiple criteria. It is well known that the two concepts do not coincide. However, in this work, we show that it is possible to characterize the set of all Nash equilibria for any noncooperative game as the Pareto-optimal solutions of a certain vector optimization problem. To accomplish this task, we increase the dimensionality of the objective function and formulate a nonconvex ordering cone under which Nash equilibria are Pareto efficient. We demonstrate these results, first, for shared-constraint games in which a joint constraint is applied to all players in a noncooperative game. In doing so, we directly relate our proposed Pareto-optimal solutions to the best response functions of each player. These results are then extended to generalized Nash games, where, in addition to providing an extension of the above characterization, we deduce two vector optimization problems providing necessary and sufficient conditions, respectively, for generalized Nash equilibria. Finally, we show that all prior results hold for vector-valued games as well. Multiple numerical examples are given and demonstrate that our proposed vector optimization formulation readily finds the set of all Nash equilibria. [ABSTRACT FROM AUTHOR]

Properly defining the center of a set has been a longstanding question in applied mathematics, with implications in numerical geometry, physics, and optimization algorithms. Minkowski centers are one such definition, whose theoretical benefits are numerous and well documented. In this paper, we revisit the advantages of Minkowski centers from a computational, rather than theoretical, perspective. First, we show that Minkowski centers are solutions to a robust optimization problem. Under this lens, we then provide computationally tractable reformulations or approximations for a series of sets, including polyhedra, polyhedral projections, and intersections of ellipsoids. Computationally, we illustrate that Minkowski centers are viable alternatives to other centers, such as Chebyshev or analytic centers, and can speed up the convergence of numerical algorithms like hit-and-run and cutting-plane methods. We hope our work sheds new and practical light on Minkowski centers and exposes their potential benefits as a computational tool. Centers of convex sets are geometric objects that have received extensive attention in the mathematical and optimization literature, both from a theoretical and practical standpoint. For instance, they serve as initialization points for many algorithms such as interior-point, hit-and-run, or cutting-planes methods. First, we observe that computing a Minkowski center of a convex set can be formulated as the solution of a robust optimization problem. As such, we can derive tractable formulations for computing Minkowski centers of polyhedra and convex hulls. Computationally, we illustrate that using Minkowski centers, instead of analytic or Chebyshev centers, improves the convergence of hit-and-run and cutting-plane algorithms. We also provide efficient numerical strategies for computing centers of the projection of polyhedra and of the intersection of two ellipsoids. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.2448. [ABSTRACT FROM AUTHOR]

A Comprehensive Set of Asymptotic Properties for a Meaningful Aggregation of Malmquist Indices The Malmquist productivity index (MPI) has become one of the most widely used tools for analyzing dynamic performance of decision-making units. Whereas accounting for economic weights of individual units in aggregations of indices is emphasized in the literature, statistical theory for constructing confidence intervals and performing hypothesis tests based on weighted aggregation of the MPI are still unavailable. In "Statistical Inference for Aggregation of Malmquist Productivity Indices," Pham, Simar, and Zelenyuk use a novel approach (based on the uniform delta method) to develop new asymptotic theory (including new central limit theorems) for aggregate MPIs as the basis for the statistical inference and test. They also verify the finite-sample performance of their approach via extensive Monte Carlo experiments and provide an illustration using real-world data. The Malmquist productivity index (MPI) has gained popularity among studies on the dynamic change of productivity of decision-making units (DMUs). In practice, this index is frequently reported at aggregate levels (e.g., public and private firms) in the form of simple, equally weighted arithmetic or geometric means of individual MPIs. A number of studies emphasize that it is necessary to account for the relative importance of individual DMUs in the aggregations of indices in general and of the MPI in particular. Whereas more suitable aggregations of MPIs have been introduced in the literature, their statistical properties have not been revealed yet, preventing applied researchers from making essential statistical inferences, such as confidence intervals and hypothesis testing. In this paper, we fill this gap by developing a full asymptotic theory for an appealing aggregation of MPIs. On the basis of this, meaningful statistical inferences are proposed, their finite-sample performances are verified via extensive Monte Carlo experiments, and the importance of the proposed theoretical developments is illustrated with an empirical application to real data. Funding: M. Pham acknowledges support from an Australian Government Research Training Program Scholarship. V. Zelenyuk acknowledges financial support from the University of Queensland and the Australian Research Council [Grant FT170100401]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2022.2424. [ABSTRACT FROM AUTHOR]

Can inefficiency be rational? Excess resources or slack may serve as a buffer against environmental shocks, help decouple organizations, ease planning and implementation, support innovation, and enable effective responses to competitors. Slack may however also be the result of inefficiency. In Bogetoft and Kerstens, Distinguishing useful and wasteful slack, we propose an approach to separate useful and wasteful slack. If an organization can maintain the same levels of output and slack at lower cost, there is wasteful or nonrationalizable spending. We develop ways to measure the extent to which total spending can be rationalized and show how to statistically estimate and test the usefulness of the available slack using bootstrapping. The literature on organization and strategic management suggests that slack in the form of excess resources may be useful. It may, for example, serve as a buffer against environmental shocks, help decouple organizations, ease planning and implementation, support innovation, and enable effective responses to competitors. In contrast, the economic literature tends to view slack as wasteful. When the same products and services can be produced with fewer resources and slack per se is not assigned any value, slack should be eliminated. The aim of this paper is to reconcile these two perspectives. We acknowledge that slack may be both useful and wasteful. The challenge is how to separate the two. Our approach relies on the simple Pareto idea. If an organization can maintain the same levels of output and slack at lower cost, there is wasteful or nonrationalizable spending. We develop ways to measure the extent to which total spending can be rationalized and show how to statistically estimate and test the usefulness of the available slack using bootstrapping. Funding: Financial support from Det Frie Forskningsråd [Grant 9038-00042A] is greatly appreciated. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2415. [ABSTRACT FROM AUTHOR]

Problem definition: Multistage service is common in healthcare. One widely adopted approach to manage patient visits in multistage service is to provide patients with visit itineraries that specify personalized appointment time for each patient at each service stage. We study how to design such visit itineraries. Methodology/results: We develop the first optimization modeling framework to provide each patient with a personalized visit itinerary in a tandem (healthcare) service system. Due to interdependencies among stages, our model loses those elegant properties (e.g., L-convexity and submodularity) often utilized to solve the classic single-stage models. To address these challenges, we develop two original reformulations. One is directly amenable to off-the-shelf optimization software, and the other is a concave minimization problem over a polyhedron shown to have neat structural properties, based on which we develop efficient solution algorithms. In addition to these exact solution approaches, we propose an approximation approach with a provable optimality bound and numerically validated performance to serve as an easy-to-implement heuristic. A case study populated by data from the Dana-Farber Cancer Institute shows that our approach makes a remarkable 28% cost reduction over practice on average. Managerial implications: Common approaches used in practice are based on simple adjustments to schedules generated by single-stage models, often assuming deterministic service times. Whereas such approaches are intuitive and take advantage of existing knowledge of single-stage models, they can lead to significant loss of operational efficiency in managing multistage services. A well-designed patient visit itinerary that carefully addresses the interdependencies among stages can significantly improve patient experience and provider utilization. History: This paper was selected for Fast Track in the M&SOM Journal from the 2022 MSOM Healthcare SIG Conference. Funding: The work of the last two authors was supported in part by the National Natural Science Foundation of China [Grants 71931008 and 72001220]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2023.0134. [ABSTRACT FROM AUTHOR]

Markov Decision Process Tayloring for Approximation Design Optimal control problems are difficult to solve for problems on large state spaces, calling for the development of approximate solution methods. In "A Low-rank Approximation for MDPs via Moment Coupling," Zhang and Gurvich introduce a novel framework to approximate Markov decision processes (MDPs) that stands on two pillars: (i) state aggregation, as the algorithmic infrastructure, and (ii) central-limit-theorem-type approximations, as the mathematical underpinning. The theoretical guarantees are grounded in the approximation of the Bellman equation by a partial differential equation (PDE) where, in the spirit of the central limit theorem, the transition matrix of the controlled Markov chain is reduced to its local first and second moments. Instead of solving the PDE, the algorithm introduced in the paper constructs a "sister"' (controlled) Markov chain whose two local transition moments are approximately identical with those of the focal chain. Because of this moment matching, the original chain and its sister are coupled through the PDE, facilitating optimality guarantees. Embedded into standard soft aggregation, moment matching provides a disciplined mechanism to tune the aggregation and disaggregation probabilities. We introduce a framework to approximate Markov decision processes (MDPs) that stands on two pillars: (i) state aggregation, as the algorithmic infrastructure, and (ii) central-limit-theorem-type approximations, as the mathematical underpinning of optimality guarantees. The theory is grounded in recent work by Braverman et al. [Braverman A, Gurvich I, Huang J (2020) On the Taylor expansion of value functions. Oper. Res. 68(2):631–65] that relates the solution of the Bellman equation to that of a partial differential equation (PDE) where, in the spirit of the central limit theorem, the transition matrix is reduced to its local first and second moments. Solving the PDE is not required by our method. Instead, we construct a "sister" (controlled) Markov chain whose two local transition moments are approximately identical with those of the focal chain. Because of this moment matching, the original chain and its sister are coupled through the PDE, a coupling that facilitates optimality guarantees. Embedded into standard soft aggregation algorithms, moment matching provides a disciplined mechanism to tune the aggregation and disaggregation probabilities. Computational gains arise from the reduction of the effective state space from N to N 1 2 + ϵ is as one might intuitively expect from approximations grounded in the central limit theorem. Funding: This work was supported by the National Science Foundation [Grant CMMI-1662294]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2392. [ABSTRACT FROM AUTHOR]

Erratum to "Competitive Two-Agent Scheduling and Its Applications" The paper "Competitive Two-Agent Scheduling and Its Applications" by Leung, Pinedo, and Wan appeared in Operations Research in 2010. Because competitive agent scheduling has become an active area of research, the paper has garnered its share of citations over the years. This particular direction of scheduling research has become so popular that the book Multiagent Scheduling: Models and Algorithms by Agnetis, Billaut, Gawiejnowicz, Pacciarelli, and Soukhal appeared in 2014. However, one of the results in the Leung et al. paper had a minor error in it. The paper considers a two-agent scheduling problem with a single machine, with each one of the two agents having their own set of jobs. The first agent has as the objective the minimization of the total tardiness of her set of jobs, and the second agent has to ensure that the total completion time of her set of jobs is less than or equal to Q. Leung et al. showed, through a dynamic programming formulation, that this problem can be solved in pseudopolynomial time and determined the time complexity of their algorithm. Their proof contains a minor error. The proper algorithm is still pseudopolynomial but of a slightly higher time complexity. Leung et al. (2010) [Leung JY-T, Pinedo M, Wan G (2010) Competitive two-agent scheduling and its applications. Oper. Res. 58:458–469] considered a two-agent nonpreemptive single-machine scheduling problem. Agent A is responsible for n1 jobs with due dates d 1 , ... , d n and has as the objective the minimization of the total tardiness of the n1 jobs. Agent B is responsible for n2 jobs and has as the objective the minimization of the total completion time of the n2 jobs. The problem is to find a schedule for the n 1 + n 2 jobs that minimizes the objective of agent A (with regard to his n1 jobs) while keeping the objective of agent B (with regard to his n2 jobs) below or at a fixed level Q. Leung et al. (2010) [Leung JY-T, Pinedo M, Wan G (2010) Competitive two-agent scheduling and its applications. Oper. Res. 58:458–469], in their theorem 3, showed that this problem can be solved through dynamic programming in pseudopolynomial time. However, in the proof of their theorem and in their dynamic programming formulation, there is an error that requires some changes in their proof. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel data-driven optimization approach for trajectory-based air traffic flow management (ATFM). A key aspect of the proposed approach is the inclusion of airspace users' trajectory preferences, which are computed from traffic data by combining clustering and classification techniques. Machine learning is also used to extract consistent trajectory options, whereas optimization is applied to resolve demand-capacity imbalances by means of a mathematical programming model that judiciously assigns a feasible four-dimensional trajectory and a possible ground delay to each flight. The methodology has been tested on instances extracted from the Eurocontrol data repository. With more than 32,000 flights considered, we solve the largest instances of the ATFM problem available in the literature in short computational times that are reasonable from the practical point of view. As a by-product, we highlight the trade-off between preferences and delays as well as the potential benefits. Indeed, computing efficient solutions to the problem facilitates a consensus between the network manager and airspace users. In view of the level of accuracy of the solutions and the excellent computational performance, we are optimistic that the proposed approach can make a significant contribution to the development of the next generation of air traffic flow management tools. [ABSTRACT FROM AUTHOR]

What would Dantzig do with a quantum computer? It is unlikely we will ever find out the answer to this question. However, we can try to understand if the simplex method can be implemented on a quantum computer, and this might have piqued Dantzig's interest. The paper "Fast Quantum Subroutines for the Simplex Method" gives a quantum implementation of an iteration of the simplex method, in which the basis inverse is never explicitly computed: the quantum computer takes as input the current basis and certifies optimality or outputs the next basis. Because computing the basis inverse is expensive, this can lead to an asymptotically faster algorithm in terms of the problem size: in the best case, the quantum algorithm can identify pivots in essentially linear time! This, however, comes at the cost of worse dependence on some numerical parameters: all these tradeoffs are discussed in the full article. We propose quantum subroutines for the simplex method that avoid classical computation of the basis inverse. We show how to quantize all steps of the simplex algorithm, including checking optimality, unboundedness, and identifying a pivot (i.e., pricing the columns and performing the ratio test) according to Dantzig's rule or the steepest edge rule. The quantized subroutines obtain a polynomial speedup in the dimension of the problem but have worse dependence on other numerical parameters. For example, for a problem with m constraints, n variables, at most dc nonzero elements per column of the costraint matrix, at most d nonzero elements per column or row of the basis, basis condition number κ, and optimality tolerance ϵ, pricing can be performed in O ˜ (ϵ − 1 κ d n (d c n + d m)) time, where the O ˜ notation hides polylogarithmic factors; classically, pricing requires O (d c 0.7 m 1.9 + m 2 + o (1) + d c n) time in the worst case using the fastest known algorithm for sparse matrix multiplication. For well-conditioned sparse problems, the quantum subroutines scale better in m and n and may therefore have an advantage for very large problems. The running time of the quantum subroutines can be improved if the constraint matrix admits an efficient algorithmic description or if quantum RAM is available. Funding: This work was supported by the Army Research Office [Grant W911NF-20-1-0014] and the Air Force Research Laboratory [Grant FA8750-C-18-0098]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2341. [ABSTRACT FROM AUTHOR]

Separation of mixtures of chemicals, ubiquitous in chemical and petrochemical industries, by distillation is energy intensive. Nearly 3% of the overall energy is used for distillation in the United States. Improving the distillation process is crucial for making chemical industries more sustainable. However, designing distillation sequences is challenging because the choice set is vast, and the equations governing the physical process are highly nonconvex. Traditional design practices rely on heuristics and often result in suboptimal solutions. Tumbalam Gooty et al. present the first approach that reliably identifies the distillation sequence that requires the least energy for a given separation. By embedding convex hulls of substructures and adapting the reformulation-linearization technique to fractions of polynomials, they demonstrated that their approach outperforms the state-of-the-art. Their work will help the chemical industry reduce greenhouse gas emissions associated with distillation. In this paper, we describe the first mixed-integer nonlinear programming (MINLP)-based solution approach that successfully identifies the most energy-efficient distillation configuration sequence for a given separation. Current sequence design strategies are largely heuristic. The rigorous approach presented here can help reduce the significant energy consumption and consequent greenhouse gas emissions by separation processes. First, we model discrete choices using a formulation that is provably tighter than previous formulations. Second, we highlight the use of partial fraction decomposition alongside reformulation-linearization technique (RLT). Third, we obtain convex hull results for various special structures. Fourth, we develop new ways to discretize the MINLP. Finally, we provide computational evidence to demonstrate that our approach significantly outperforms the state-of-the-art techniques. Funding: This work was supported by the U.S. Department of Energy [Grant DE-EE0005768], the Bilsland Dissertation Fellowship, and the National Science Foundation [Grant EEC-1647722]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2340. [ABSTRACT FROM AUTHOR]

An assumption that is pervasive in revenue management and economics is that buyers are perfect optimizers. However, in practice, buyers may be limited by their computational capabilities or lack of information and may not be able to perfectly optimize their response to a selling mechanism. This has motivated the introduction of approximate incentive compatibility as a solution concept for practical mechanisms. In "Mechanism Design under Approximate Incentive Compatibility," Balseiro, Besbes, and Castro study, for the first time, the problem of designing optimal selling mechanisms when buyers are imperfect optimizers. Their work characterizes structural properties of approximate incentive compatible mechanisms and establishes fundamental bounds on how much revenue can be garnered by moving from exact to approximate incentive constraints. Their work brings a new perspective to the theory of mechanism design by shedding light on a novel class of optimization problems, techniques, and challenges that emerge when relaxing incentive constraints. A fundamental assumption in classical mechanism design is that buyers are perfect optimizers. However, in practice, buyers may be limited by their computational capabilities or a lack of information and may not be able to perfectly optimize their response to a mechanism. This has motivated the introduction of approximate incentive compatibility (IC) as an appealing solution concept for practical mechanism design. Although most of the literature has focused on the analysis of particular approximate IC mechanisms, this paper is the first to study the design of optimal mechanisms in the space of approximate IC mechanisms and to explore how much revenue can be garnered by moving from exact to approximate incentive constraints. In particular, we study the problem of a seller facing one buyer with private values and analyze optimal selling mechanisms under ε-incentive compatibility. We establish that the gains that can be garnered depend on the local curvature of the seller's revenue function around the optimal posted price when the buyer is a perfect optimizer. If the revenue function behaves locally like an α-power for α ∈ (1 , ∞) , then no mechanism can garner gains higher than order ε α / (2 α − 1) . This improves on state-of-the-art results that imply maximum gains of ε 1 / 2 by providing the first parametric bounds that capture the impact of revenue function's curvature on revenue gains. Furthermore, we establish that an optimal mechanism needs to randomize as soon as ε > 0 and construct a randomized mechanism that is guaranteed to achieve order ε α / (2 α − 1) additional revenues, leading to a tight characterization of the revenue implications of approximate IC constraints. Our study sheds light on a novel class of optimization problems and the challenges that emerge when relaxing IC constraints. In particular, it brings forward the need to optimize not only over allocations and payments but also over best responses, and we develop a new framework to address this challenge. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2359. [ABSTRACT FROM AUTHOR]