Operations Research

最新文章

• Optimal Regularized Online Allocation by Adaptive Re-Solving AI翻译
  作者：Ma, Wanteng; Cao, Ying; Tsang, Danny H. K.; Xia, Dong
  作者单位：Hong Kong University of Science & Technology; Hong Kong University of Science & Technology
  摘要：This paper introduces a dual -based algorithm framework for solving the regularized online resource allocation problems, which have potentially nonconcave cumulative rewards, hard resource constraints, and a nonseparable regularizer. Under a strategy of adaptively updating the resource constraints, the proposed framework only requests approximate solutions to the empirical dual problems up to a certain accuracy and yet delivers an optimal logarithmic regret under a locally second -order growth...
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback AI翻译
  作者：Jordan, Michael; Lin, Tianyi; Zhou, Zhengyuan
  作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; Columbia University; New York University
  摘要：Online gradient descent (OGD) is well-known to be doubly optimal under strong convexity or monotonicity assumptions: (1) in the single -agent setting, it achieves an optimal regret of O ( log T ) for strongly convex cost functions, and (2) in the multiagent setting of strongly monotone games with each agent employing OGD, we obtain lastiterate convergence of the joint action to a unique Nash equilibrium at an optimal rate of O 1 ( ). . Whereas these finite -time guarantees highlight its merits...
• On the Robustness of Second-Price Auctions in Prior-Independent Mechanism Design AI翻译
  作者：Anunrojwong, Jerry; Balseiro, Santiago R.; Besbes, Omar
  作者单位：Columbia University
  摘要：Classical Bayesian mechanism design relies on the common prior assumption, but the common prior is often not available in practice. We study the design of prior-independent mechanisms that relax this assumption: The seller is selling an indivisible item to n buyers such that the buyers' valuations are drawn from a joint distribution that is unknown to both the buyers and the seller, buyers do not need to form beliefs about competitors, and the seller assumes the distribution is adversarially c...
• Column-Randomized Linear Programs: Performance Guarantees and Applications AI翻译
  作者：Akchen, Yi-Chun; Misic, Velibor V.
  作者单位：University of London; University College London; University of California System; University of California Los Angeles
  摘要：We propose a randomized method for solving linear programs with a large number of columns but a relatively small number of constraints. Because enumerating all the columns is usually unrealistic, such linear programs are commonly solved by column generation, which is often still computationally challenging because of the intractability of the subproblem in many applications. Instead of iteratively introducing one column at a time as in column generation, our proposed method involves sampling a...
• Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality Loss, and Algorithms AI翻译
  作者：Scroccaro, Pedro Zattoni; Atasoy, Bilge; Esfahani, Peyman Mohajerin
  作者单位：Delft University of Technology; Delft University of Technology
  摘要：In inverse optimization (IO), an expert agent solves an optimization problem parametric in an exogenous signal. From a learning perspective, the goal is to learn the expert's cost function given a data set of signals and corresponding optimal actions. Motivated by the geometry of the IO set of consistent cost vectors, we introduce the incenter concept, a new notion akin to the recently proposed circumcenter concept. Discussing the geometric and robustness interpretation of the incenter cost ve...
• Process Flexibility: A Distribution-Free Approach to Long Chain Resilience AI翻译
  作者：Chen, Li; Chou, Mabel; Sun, Qinghe
  作者单位：University of Sydney; National University of Singapore; National University of Singapore; National University of Singapore; Hong Kong Polytechnic University
  摘要：Process flexibility has been a well-established supply chain strategy in both theory and practice for managing demand uncertainty. This study extends its application to mitigating supply disruptions by analyzing a long chain system. Specifically, we investigate the effectiveness of long chains in the face of random supply disruptions and demand uncertainty. We derive a closed-form, tight bound on the expected sales ratio of a long chain relative to full flexibility under random disruptions, th...
• Joint Capacity Allocation and Job Assignment Under Uncertainty AI翻译
  作者：Wang, Peng; Lim, Yun Fong; Loke, Gar Goei
  作者单位：Singapore University of Social Sciences (SUSS); Singapore Management University; Durham University
  摘要：In this paper, we consider the multiperiod joint capacity allocation and job assignment problem. The goal of the planner is to simultaneously decide on allocating resources across the J different supply nodes and assigning jobs of I different demand origins to these J nodes, so as to maximize the reward for matching or minimize the cost of failure to match. We furthermore consider three features: (i) supply is replenishable after random time, (ii) demand is random, and (iii) demand can wait an...
• Dynamic Pricing with Fairness Constraints AI翻译
  作者：Cohen, Maxime C.; Miao, Sentao; Wang, Yining
  作者单位：McGill University; University of Colorado System; University of Colorado Boulder; University of Texas System; University of Texas Dallas
  摘要：Following the increasing popularity of personalized pricing, there is a growing concern from customers and policymakers regarding fairness considerations. This paper studies the problem of dynamic pricing with unknown demand under two types of fairness constraints: price fairness and demand fairness. For price fairness, the retailer is required to (i) set similar prices for different customer groups (called group fairness) and (ii) ensure that the prices over time for each customer group are r...
• On the Sparsity of Optimal Linear Decision Rules for a Class of Robust Optimization Problems with Box Uncertainty Sets AI翻译
  作者：Lu, Haihao; Sturt, Bradley
  作者单位：Massachusetts Institute of Technology (MIT); University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
  摘要：We consider a class of production-inventory problems with box uncertainty sets from the seminal work of Ben-Tal et al. [Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math. Programming 99(2):351-376] on linear decision rules in robust optimization. We prove that there always exists an optimal linear decision rule for this class of problems in which the number of nonzero parameters in the linear decision rule grows linearly in ...
• Technical Note-A Data-Driven Approach to Beating SAA Out of Sample AI翻译
  作者：Gotoh, Jun-ya; Kim, Michael Jong; Lim, Andrew E. B.
  作者单位：Chuo University; University of British Columbia; National University of Singapore; National University of Singapore
  摘要：Whereas solutions of distributionally robust optimization (DRO) problems can sometimes have a higher out-of-sample expected reward than the sample average approximation (SAA), there is no guarantee. In this paper, we introduce a class of distributionally optimistic optimization (DOO) models and show that it is always possible to beat SAA out-of-sample if we consider not just worst case (DRO) models but also best case (DOO) ones. We also show, however, that this comes at a cost: optimistic solu...