Operations Research

最新文章

• Error Propagation in Asymptotic Analysis of the Data-Driven (s, S) Inventory Policy AI翻译
  作者：Zhang, Xun; Ye, Zhi-Sheng; Haskell, William B.
  作者单位：Southern University of Science & Technology; National University of Singapore; Purdue University System; Purdue University
  摘要：We study periodic review stochastic inventory control in the data-driven setting where the retailer makes ordering decisions based only on historical demand observations without any knowledge of the probability distribution of the demand. Because an (s, S)policy is optimal when the demand distribution is known, we investigate the statistical properties of the data-driven (s, S)-policy obtained by recursively computing the empirical cost-to-go functions. This policy is inherently challenging to...
• Deepest Cuts for Benders Decomposition AI翻译
  作者：Hosseini, Mojtaba; Turner, John
  作者单位：University of Iowa; University of California System; University of California Irvine
  摘要：Since its inception, Benders decomposition (BD) has been successfully applied to a wide range of large-scale mixed-integer (linear) problems. The key element of BD is the derivation of Benders cuts, which are often not unique. In this paper, we introduce a novel unifying Benders cut selection technique based on a geometric interpretation of cut depth, produce deepest Benders cuts based on & ell;p-norms, and study their properties. Specifically, we show that deepest cuts resolve infeasibility t...
• Ordinary and Prophet Planning Under Uncertainty in Bernoulli Congestion Games AI翻译
  作者：Cominetti, Roberto; Scarsini, Marco; Schroder, Marc; Stier-Mosesd, Nicolas E.
  作者单位：Universidad Adolfo Ibanez; Luiss Guido Carli University; Maastricht University
  摘要：We consider an atomic congestion game in which each player i participates in the game with an exogenous and known probability p(i) is an element of (0, 1], independently of everybody else, or stays out and incurs no cost. We compute the parameterized price of anarchy to characterize the impact of demand uncertainty on the efficiency of selfish behavior, considering two different notions of a social planner. A prophet planner knows the realization of the random participation in the game; the or...
• Asymptotically Tight Bounds on the Optimal Pricing Strategy with Patient Customers AI翻译
  作者：Qian, Shuaijie; Su, Xizhi; Zhou, Chao
  作者单位：Hong Kong University of Science & Technology; National University of Singapore; National University of Singapore
  摘要：This work considers a monopolist seller facing both patient and impatient customers. Given the current price, the impatient customers will either purchase or leave immediately, depending on the relative magnitude between this price and their valuation of the product. In comparison, the patient customers will wait for some periods to see if the price will drop to their valuation, and if that occurs, they will purchase immediately. The monopolist designs the pricing strategy to maximize the long...
• Search in the Dark: The Case with Recall and Gaussian Learning AI翻译
  作者：Baucells, Manel; Zorc, Sasa
  作者单位：University of Virginia
  摘要：The classic sequential search problem rewards the decision maker with the highest sampled value minus a cost per sample. If the sampling distribution is unknown, then a Bayesian decision maker faces a complex balance between exploration and exploitation. We solve the stopping problem of sampling from a normal distribution with unknown mean and variance and a conjugate prior, a longstanding open problem. The optimal stopping region may be empty (it may be optimal to continue the search regardle...
• Dynamic Control of Service Systems with Returns: Application to Design of Postdischarge Hospital Readmission Prevention Programs AI翻译
  作者：Chan, Timothy C. Y.; Huang, Simon Y.; Sarhangian, Vahid
  作者单位：University of Toronto
  摘要：We study a control problem for queueing systems in which customers may return for additional episodes of service after their initial service completion. At each service completion epoch, the decision maker can choose to reduce the probability of return for the departing customer but at a cost that is convex increasing in the amount of reduction in the return probability. Other costs are incurred as customers wait in the queue and every time they return for service. Our primary motivation comes...
• Strong Optimal Classification Trees AI翻译
  作者：Aghaei, Sina; Gomez, Andres; Vayanos, Phebe
  作者单位：University of Southern California; University of Southern California
  摘要：Decision trees are among the most popular machine learning models and are used routinely in applications ranging from revenue management and medicine to bioinformatics. In this paper, we consider the problem of learning optimal binary classification trees with univariate splits. Literature on the topic has burgeoned in recent years, motivated both by the empirical suboptimality of heuristic approaches and the tremendous improvements in mixed-integer optimization (MIO) technology. Yet, existing...
• Nonadaptive Stochastic Score Classification and Explainable Half-Space Evaluation AI翻译
  作者：Ghuge, Rohan; Gupta, Anupam; Nagarajan, Viswanath
  作者单位：University System of Georgia; Georgia Institute of Technology; New York University; University of Michigan System; University of Michigan
  摘要：Sequential testing problems involve a complex system with several components, each of which is working with some independent probability. The outcome of each component can be determined by performing a test, which incurs some cost. The overall system status is given by a function f of the outcomes of its components. The goal is to evaluate this function f by performing tests at the minimum expected cost. Although there has been extensive prior work on this topic, provable approximation bounds ...
• Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations AI翻译
  作者：Bray, Robert L.
  作者单位：Northwestern University
  摘要：I use empirical processes to study how the shadow prices of a linear program that allocates an endowment of nf3 is an element of Rm resources to n customers behave as n -> infinity. I show the shadow prices (i) adhere to a concentration of measure, (ii) converge to a multivariate normal under central-limit-theorem scaling, and (iii) have a variance that decreases like Theta(1/n). I use these results to prove that the expected regret in an online linear program is Theta(log n), both when the cu...
• Hardness of Pricing Routes for Two-Stage Stochastic Vehicle Routing Problems with Scenarios AI翻译
  作者：Ota, Matheus J.; Fukasawa, Ricardo
  作者单位：University of Waterloo
  摘要：The vehicle routing problem with stochastic demands (VRPSD) generalizes the classic vehicle routing problem by considering customer demands as random variables. Similar to other vehicle routing variants, state-of-the-art algorithms for the VRPSD are often based on set-partitioning formulations, which require efficient routines for the associated pricing problems. However, all of these set partitioning-based approaches have strong assumptions on the correlation between the demands of random var...