Operations Research

最新文章

• Sparse PCA with Multiple Components AI翻译
  作者：Cory-Wright, Ryan; Pauphilet, Jean
  作者单位：University of London; London Business School
  摘要：Sparse principal component analysis (PCA) is a fundamental technique for obtaining interpretable combinations of features, or principal components (PCs), that explain the variance of high-dimensional data sets. This involves solving a sparsity- and orthogonality-constrained convex maximization problem, which is extremely computationally challenging. Most existing work addresses sparse PCA via methods-such as iteratively computing one sparse PC and deflating the covariance matrix-that do not gu...
• Invariant Distributions in Nonlinear Markov Chains with Aggregators: Theory, Computation, and Applications AI翻译
  作者：Light, Bar
  作者单位：National University of Singapore; National University of Singapore
  摘要：We study the properties of a subclass of stochastic processes called discrete-time nonlinear Markov chains with an aggregator, which naturally appear in various topics such as strategic queueing systems, inventory dynamics, opinion dynamics, and wealth dynamics. In these chains, the next period's distribution depends on both the current state and a real-valued function of the current distribution. For these chains, we provide conditions for the uniqueness of an invariant distribution that do n...
• The Pandora's Box Problem with Sequential Inspections AI翻译
  作者：Aouad, Ali; Ji, Jingwei; Shaposhnik, Yaron
  作者单位：Massachusetts Institute of Technology (MIT); Stanford University; University of Rochester
  摘要：The Pandora's box problem is a core model in economic theory that captures an agent's (Pandora's) search for the best alternative (box). We study an important generalization of the problem in which the agent can either fully open boxes for a certain fee to reveal their exact values or partially open them at a reduced cost. This introduces a new trade-off between information acquisition and cost efficiency. We establish a hardness result and employ an array of techniques in stochastic optimizat...
• A Note on Piecewise Affine Decision Rules for Robust, Stochastic, and Data-Driven Optimization AI翻译
  作者：Thomae, Simon; Schiffer, Maximilian; Wiesemann, Wolfram
  作者单位：RWTH Aachen University; Technical University of Munich; Technical University of Munich; Imperial College London
  摘要：Multistage decision making under uncertainty, where decisions are taken under sequentially revealing uncertain problem parameters, is often essential to faithfully model managerial problems. Given the significant computational challenges involved, these problems are typically solved approximately. This short note introduces an algorithmic framework that revisits a popular approximation scheme for multistage stochastic programs and improves on it to deliver superior policies in the stochastic s...
• On Sinkhorn's Algorithm and Choice Modeling AI翻译
  作者：Qu, Zhaonan; Galichon, Alfred; Gao, Wenzhi; Ugander, Johan
  作者单位：New Jersey Institute of Technology; Columbia University; New York University; New York University; Institut d'Etudes Politiques Paris (Sciences Po); Stanford University; Stanford University
  摘要：For a broad class of models widely used in practice for choice and ranking data based on the Luce choice axiom, including the Bradley-Terry-Luce and Plackett-Luce models, we show that the associated maximum likelihood estimation problems are equivalent to a classic matrix-balancing problem with target row and column sums. This perspective opens doors between two seemingly unrelated research areas and allows us to unify existing algorithms in the choice-modeling literature as special instances ...
• Hidden Convexity in a Class of Optimization Problems with Bilinear Terms AI翻译
  作者：Gorissen, Bram L.; den Hertog, Dick; Reusken, Meike
  作者单位：Harvard University; Harvard University Medical Affiliates; Massachusetts General Hospital; Harvard University; Harvard Medical School; Harvard University; Massachusetts Institute of Technology (MIT); Broad Institute; University of Amsterdam; Tilburg University; Wageningen University & Research
  摘要：In this paper we identify a new class of nonconvex optimization problems that can be equivalently reformulated to convex ones. These nonconvex problems can be characterized by convex functions with bilinear arguments. We describe several examples of important applications that have this structure. These include the problems with variable coefficients, the dual of robust nonlinear optimization problems that are convex in the optimization variables and concave in the uncertain parameters, and in...
• ORLM: A Customizable Framework in Training Large Models for Automated Optimization Modeling AI翻译
  作者：Huang, Chenyu; Tang, Zhengyang; Hu, Shixi; Jiang, Ruoqing; Zheng, Xin; Ge, Dongdong; Wang, Benyou; Wang, Zizhuo
  作者单位：Shanghai University of Finance & Economics; The Chinese University of Hong Kong, Shenzhen; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Columbia University; Tsinghua University; Duke University; Shanghai Jiao Tong University; The Chinese University of Hong Kong, Shenzhen
  摘要：Optimization modeling plays a critical role in the application of Operations Research (OR) tools to address real-world problems, yet they pose challenges and require extensive expertise from OR experts. With the advent of large language models (LLMs), new opportunities have emerged to streamline and automate such tasks. However, current research predominantly relies on closed-source LLMs, such as GPT-4, along with extensive prompt engineering techniques. This reliance stems from the scarcity o...
• Crosscutting Areas On Consistency of Signature Using Lasso AI翻译
  作者：Guo, Xin; Wang, Binnan; Zhang, Ruixun; Zhao, Chaoyi
  作者单位：University of California System; University of California Berkeley; Peking University; Peking University; Peking University; Peking University; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
  摘要：Signatures are iterated path integrals of continuous and discrete-time processes, and their universal nonlinearity linearizes the problem of feature selection in time series data analysis. This paper studies the consistency of signature using Lasso regression, both theoretically and numerically. We establish conditions under which the Lasso regression is consistent both asymptotically and in finite sample. Furthermore, we show that the Lasso regression is more consistent with the Ito signature...
• Random Graph Matching at Otter's Threshold via Counting Chandeliers AI翻译
  作者：Mao, Cheng; Wu, Yihong; Xu, Jiaming; Yu, Sophie H.
  作者单位：University System of Georgia; Georgia Institute of Technology; Yale University; Duke University; University of Pennsylvania
  摘要：We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two Erdos-Renyi graphs G(n,q) whose edges are correlated through a latent vertex correspondence, we show that this algorithm correctly matches all but a vanishing fraction of the vertices with high probability, provided that nq -> infinity and the edge correlation coefficient rho satisfies rho(2) > alpha approximate to 0:338, wh...
• Maximum Load Assortment Optimization: Approximation Algorithms and Adaptivity Gaps AI翻译
  作者：El Housni, Omar; Ibn Brahim, Marouane; Segev, Danny
  作者单位：Cornell University; Tel Aviv University; Tel Aviv University
  摘要：Motivated by modern-day applications such as attended home delivery and preference-based group scheduling, where decision makers wish to steer a large number of customers toward choosing the exact same alternative, we introduce a novel class of assortment optimization problems, referred to as maximum load assortment optimization. In such settings, given a universe of substitutable products, we are facing a stream of customers, each choosing between either selecting a product out of an offered ...