检索结果-内蒙古大学图书馆

Technical Note-Near-Optimal Bayesian Online Assortment of Reusable Resources

OPERATIONS RESEARCH 2024年第5期72卷 iii-vii, 1751-2261, C2-C3页

作者： Feng, Yiding Niazadeh, Rad Saberi, Amin Univ Chicago Booth Sch Business Chicago IL 60637 USA Stanford Univ Management Sci & Engn Stanford CA 94305 USA

Motivated by the applications of rental services in e-commerce, we consider revenue maximization in online assortment of reusable resources for a stream of arriving consumers with different types. We design competitive online algorithms with respect to the optimum online policy in the Bayesian setting in which types are drawn independently from known heterogeneous distributions over time. In the regime where the minimum of initial inventories cmin is large, our main result is a near-optimal 1. min 12, root log(c(min))=c(min). p. competitive algorithm for the general case of reusable resources. Our algorithm relies on an expected LP benchmark for the problem, solves this LP, and simulates the solution through an independent randomized rounding. The main challenge is obtaining point-wise inventory feasibility in a computationally efficient fashion from these simulation-based algorithms. To this end, we use several technical ingredients to design discarding policies-one for each resource. These policies handle the trade-off between the inventory feasibility under reusability and the revenue loss of each of the resources. However, discarding a unit of a resource changes the future consumption of other resources. To handle this new challenge, we also introduce postprocessing assortment procedures that help with designing and analyzing our discarding policies as they run in parallel, which might be of independent interest. As a side result, by leveraging techniques from the literature on prophet inequality, we further show an improved near-optimal 1. 1= root c(min) + 3v competitive algorithm for the special case of nonreusable resources. We finally evaluate the performance of our algorithms using the numerical simulations on the synthetic data.

关键词： analysis of algorithms suboptimal algorithms inventory/production approximations/heuristics

来源：评论

学校读者我要写书评

暂无评论

Batching and Optimal Multistage Bipartite Allocations

引用

MANAGEMENT SCIENCE 2025年第5期71卷 iv-vi, 3641-4531页

作者： Feng, Yiding Niazadeh, Rad Univ Chicago Booth Sch Business Chicago IL 60637 USA

In several applications of real-time matching of demand to supply in online marketplaces, the platform allows for some latency to batch the demand and improve the efficiency of the resulting matching. Motivated by these applications, we study the optimal trade-off between batching and inefficiency in the context of designing robust online allocations. As our base model, we consider K-stage variants of the classic vertexweighted bipartite b-matching in the adversarial setting, where online vertices arrive stagewise and in K batches-in contrast to online arrival. Our main result for this problem is an optimal (1 - (1- 1/K)K)-competitive (fractional) matching algorithm, improving the classic (1 -1/e)-competitive ratio bound known for its online variant [Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Ad words and generalized online matching. J. ACM 54(5):22-es;Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex weighted bipartite matching and single-bid budgeted allocations. Proc. 22nd Annual ACM-SIAM Sympos. Discrete algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1253-1264]. We also extend this result to the general problem of multistage configuration allocation with free disposals [Devanur NR, Huang Z, Korula N, Mirrokni VS, Yan Q (2016) Whole page optimization and submodular welfare maximization with online bidders. ACM Trans. Econom. Comput. 4(3):1-20], which is motivated by the display advertising application in the context of video streaming platforms. Our main technique at a high level is developing algorithmic tools to vary the trade-off between "greediness" and "hedging" of the matching algorithm across stages. We rely on a particular family of convex programming-based matchings that distribute the demand in a specifically balanced way among supply in different stages while carefully modifying the balancedness of the resulting matching across stages. More precisely, we identify a sequence of polynomials with decreasing degr

关键词： computers computer science analysis of algorithms suboptimal algorithms online algorithms competitive analysis matching and batching

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Bounds on the k-Traveling Salesman Problem and the Traveling Repairman Problem

引用

MATHEMATICS OF OPERATIONS RESEARCH 2024年第2期49卷 1169-1191页

作者： Blanchard, Moise Jacquillat, Alexandre Jaillet, Patrick MIT Cambridge MA 02139 USA

This article may be used only for the purposes of research, teaching, and/or private study. Commercial use or systematic downloading (by robots or other automatic processes) is prohibited without explicit Publisher approval, unless otherwise noted. For more information, contact permissions@***. The Publisher does not warrant or guarantee the article's accuracy, completeness, merchantability, fitness for a particular purpose, or non-infringement. Descriptions of, or references to, products or publications, or inclusion of an advertisement in this article, neither constitutes nor implies a guarantee, endorsement, or support of claims made of that product, publication, or service.

关键词： traveling salesman stochastic model applications suboptimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Assortment Optimization Under the Multinomial Logit Model with Utility-Based Rank Cutoffs

引用

OPERATIONS RESEARCH 2024年第4期72卷 1453-1474页

作者： Bai, Yicheng Feldman, Jacob Topaloglu, Huseyin Wagner, Laura Cornell Tech Sch Operat Res & Informat Engn New York NY 10044 USA Washington Univ Olin Business Sch St Louis MO 63130 USA Univ Navarra IESE Business Sch Barcelona 08034 Spain

We study assortment optimization problems under a natural variant of the multinomial logit model where the customers are willing to focus only on a certain number of products that provide the largest utilities. In particular, each customer has a rank cutoff, characterizing the number of products that she will focus on during the course of her choice process. Given that we offer a certain assortment of products, the choice process of a customer with rank cutoff k proceeds as follows. The customer associates random utilities with all of the products as well as the no-purchase option. The customer ignores all alternatives whose utilities are not within the k largest utilities. Among the remaining alternatives, the customer chooses the available alternative that provides the largest utility. Under the assumption that the utilities follow Gumbel distributions with the same scale parameter, we provide a recursion to compute the choice probabilities. Considering the assortment optimization problem to find the revenue-maximizing assortment of products to offer, we show that the problem is NP-hard and give a polynomial time approximation scheme. Because the customers ignore the products below their rank cutoffs in our variant of the multinomial logit model, intuitively speaking, our variant captures choosier choice behavior than the standard multinomial logit model. Accordingly, we show that the revenue-maximizing assortment under our variant includes the revenue-maximizing assortment under the standard multinomial logit model, so choosier behavior leads to larger assortments offered to maximize the expected revenue. We conduct computational experiments on both synthetic and real data sets to demonstrate that incorporating rank cutoffs can yield better predictions of customer choices and yield more profitable assortment recommendations.

关键词： analysis of algorithms suboptimal algorithms marketing choice models statistics data analysis

来源：评论

学校读者我要写书评

暂无评论

Dynamic Pricing (and Assortment) Under a Static Calendar

引用

MANAGEMENT SCIENCE 2021年第4期67卷 2292-2313页

作者： Ma, Will Simchi-Levi, David Zhao, Jinglong Columbia Univ Grad Sch Business New York NY 10027 USA MIT Inst Data Syst & Soc 77 Massachusetts Ave Cambridge MA 02139 USA MIT Dept Civil & Environm Engn 77 Massachusetts Ave Cambridge MA 02139 USA MIT Operat Res Ctr 77 Massachusetts Ave Cambridge MA 02139 USA

This work is motivated by our collaboration with a large consumer packaged goods (CPG) company. We have found that whereas the company appreciates the advantages of dynamic pricing, they deem it operationally much easier to plan out a static price calendar in advance. We investigate the efficacy of static control policies for revenue management problems whose optimal solution is inherently dynamic. In these problems, a firm has limited inventory to sell over a finite time horizon, over which heterogeneous customers stochastically arrive. We consider both pricing and assortment controls, and derive simple static policies in the form of a price calendar or a planned sequence of assortments, respectively. In the assortment planning problem, we also differentiate between the static vs. dynamic substitution models of customer demand. We show that our policies are within 1-1/e (approximately 0.63) of the optimum under stationary demand, and 1/2 of the optimum under nonstationary demand, with both guarantees approaching 1 if the starting inventories are large. We adapt the technique of prophet inequalities from optimal stopping theory to pricing and assortment problems, and our results are relative to the linear programming relaxation. Under the special case of stationary demand single-item pricing, our results improve the understanding of irregular and discrete demand curves, by showing that a static calendar can be (1-1/e)-approximate if the prices are sorted high-to-low. Finally, we demonstrate on both data from the CPG company and synthetic data from the literature that our simple price and assortment calendars are effective.

关键词： analysis of algorithms suboptimal algorithms inventory-production policies pricing empirical pricing

来源：评论

学校读者我要写书评

暂无评论

Inventory Balancing with Online Learning

引用

MANAGEMENT SCIENCE 2022年第3期68卷 1776-1807页

作者： Cheung, Wang Chi Ma, Will Simchi-Levi, David Wang, Xinshang Natl Univ Singapore Dept Ind Syst Engn & Management Singapore 117576 Singapore Columbia Univ Grad Sch Business New York NY 10027 USA MIT Inst Data Syst & Soc Dept Civil & Environm Engn 77 Massachusetts Ave Cambridge MA 02139 USA MIT Operat Res Ctr 77 Massachusetts Ave Cambridge MA 02139 USA Alibaba Grp US San Mateo CA 94402 USA Shanghai Jiao Tong Univ Antai Coll Econ & Management Shanghai 200240 Peoples R China

We study a general problem of allocating limited resources to heterogeneous customers over time under model uncertainty. Each type of customer can be serviced using different actions, each of which stochastically consumes some combination of resources and returns different rewards for the resources consumed. We consider a general model in which the resource consumption distribution associated with each customer type-action combination is not known but is consistent and can be learned over time. In addition, the sequence of customer types to arrive over time is arbitrary and completely unknown. We overcome both the challenges of model uncertainty and customer heterogeneity by judiciously synthesizing two algorithmic frameworks from the literature: inventory balancing, which "reserves" a portion of each resource for high-reward customer types that could later arrive based on competitive ratio analysis, and online learning, which "explores" the resource consumption distributions for each customer type under different actions based on regret analysis. We define an auxiliary problem, which allows for existing competitive ratio and regret bounds to be seamlessly integrated. Furthermore, we propose a new variant of upper confidence bound (UCB), dubbed lazyUCB, which conducts less exploration in a bid to focus on "exploitation" in view of the resource scarcity. Finally, we construct an information-theoretic family of counterexamples to show that our integrated framework achieves the best possible performance guarantee. We demonstrate the efficacy of our algorithms on both synthetic instances generated for the online matching with stochastic rewards problem under unknown probabilities and a publicly available hotel data set. Our framework is highly practical in that it requires no historical data (no fitted customer choice models or forecasting of customer arrival patterns) and can be used to initialize allocation strategies in fast-changing environments.

关键词： decision analysis sequential analysis of algorithms suboptimal algorithms inventory production

来源：评论

学校读者我要写书评

暂无评论

A unifying look at sequence submodularity

引用

ARTIFICIAL INTELLIGENCE 2021年 297卷 103486-103486页

作者： Bernardini, Sara Fagnani, Fabio Piacentini, Chiara Royal Holloway Univ London Dept Comp Sci Egham TW20 0EX Surrey England Politecn Torino Dept Math Sci I-10129 Turin Italy Augmenta Inc Toronto ON M5A 1E1 Canada

Several real-world problems in engineering and applied science require the selection of sequences that maximize a given reward function. Optimizing over sequences as opposed to sets requires exploring an exponentially larger search space and can become prohibitive in most cases of practical interest. However, if the objective function is submodular (intuitively, it exhibits a diminishing return property), the optimization problem becomes more manageable. Recently, there has been increasing interest in sequence submodularity in connection with applications such as recommender systems and online ad allocation. However, mostly ad hoc models and solutions have emerged within these applicative contexts. In consequence, the field appears fragmented and lacks coherence. In this paper, we offer a unified view of sequence submodularity and provide a generalized greedy algorithm that enjoys strong theoretical guarantees. We show how our approach naturally captures several application domains, and our algorithm encompasses existing methods, improving over them. (C) 2021 The Authors. Published by Elsevier B.V.

关键词： Submodularity Sequence submodularity Greedy algorithms suboptimal algorithms Detection problems Search-and-tracking Environmental monitoring Scheduling Recommender systems

来源：评论

学校读者我要写书评

暂无评论

Capacity Constraints Across Nests in Assortment Optimization Under the Nested Logit Model

引用

OPERATIONS RESEARCH 2015年第4期63卷 812-822页

作者： Feldman, Jacob B. Topaloglu, Huseyin Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA

We consider assortment optimization problems when customers choose according to the nested logit model and there is a capacity constraint limiting the total capacity consumption of all products offered in all nests. When each product consumes one unit of capacity, our capacity constraint limits the cardinality of the offered assortment. For the cardinality constrained case, we develop an efficient algorithm to compute the optimal assortment. When the capacity consumption of each product is arbitrary, we give an algorithm to obtain a 4-approximate solution. We show that we can compute an upper bound on the optimal expected revenue for an individual problem instance by solving a linear program. In our numerical experiments, we consider problem instances involving products with arbitrary capacity consumptions. Comparing the expected revenues from the assortments obtained by our 4-approximation algorithm with the upper bounds on the optimal expected revenues, our numerical results indicate that the 4-approximation algorithm performs quite well, yielding less than 2% optimality gap on average.

关键词： analysis of algorithms suboptimal algorithms marketing choice models

来源：评论

学校读者我要写书评

暂无评论

Semi-Autonomous Management of Multiple Ad-Hoc Teams of UAVs

Semi-Autonomous Management of Multiple Ad-Hoc Teams of UAVs

引用

IEEE Symposium on Computational Intelligence for Security and Defense Applications (CISDA)

作者： Loe, Richard Maracchion, Christopher Drozd, Andrew ANDRO Computat Solut LLC 7980 Turin RdBldg 1 Rome NY USA

ISBN: (纸本)9781467375573

A Distributed Battle Manager (DBM) system based on Concurrent MACro Partially Observable Markov Decision Processes (CMAC-POMDP) is proposed to manage multiple competing missions. Implementation details are presented for a semi-autonomous management of multiple ad-hoc teams of UAVs operating under extreme uncertainty in a contested environment. The proposed solution is semi-autonomous since command and control teams perform target confirmation, weapon selection, weapon release, and bomb damage assessment. Our proposed approach decomposes the resource management requirements into specialized mission timelines. There would be one adaptive mission timeline for each system objective, and each timeline would be represented by a POMDP. At any time, the DBM would be controlling multiple concurrent timelines that are competing for system resources. Each timeline is solved independently to obtain the optimal MDP solution parameters. These solution parameters are then combined using linear programming with constraints to obtain a suboptimal system solution. The resulting suboptimal solutions provide satisfactory real-time system performance. Under extreme uncertainty, it is preferable to maximize robustness utilizing an adequately performing solution as opposed to finding an optimal but brittle solution. Performance results of the core CMAC-POMDP algorithm are presented for a system implemented to manage multiple heterogeneous sensors addressing multiple simultaneous threats. This simpler resource management system utilizes the same timeline for all of the threats. Simulations demonstrate better than real-time performance even for large numbers of threats. Furthermore, computational requirements are shown to grow linearly with the number of threats. Extension to multiple simultaneous timelines for the DBM system is straightforward.

关键词： Partially Observable Markov Decision Processes management command and control concurrent MDPs suboptimal algorithms

来源：评论

学校读者我要写书评

暂无评论

The Assortment Packing Problem: Multiperiod Assortment Planning for Short-Lived Products

引用

MANAGEMENT SCIENCE 2014年第11期60卷 2701-2721页

作者： Caro, Felipe Martinez-de-Albeniz, Victor Rusmevichientong, Paat Univ Calif Los Angeles UCLA Anderson Sch Management Los Angeles CA 90095 USA Univ Navarra IESE Business Sch Barcelona 08034 Spain Univ So Calif USC Marshall Sch Business Los Angeles CA 90089 USA

Motivated by retailers' frequent introduction of new items to refresh product lines and maintain their market shares, we present the assortment packing problem in which a firm must decide, in advance, the release date of each product in a given collection over a selling season. Our formulation models the trade-offs among profit margins, preference weights, and limited life cycles. A key aspect of the problem is that each product is short-lived in the sense that, once introduced, its attractiveness lasts only a few periods and vanishes over time. The objective is to determine when to introduce each product to maximize the total profit over the selling season. Even for two periods, the corresponding optimization problem is shown to be NP-complete. As a result, we study a continuous relaxation of the problem that approximates the problem well, when the number of products is large. When margins are identical and product preferences decay exponentially, its solution can be characterized: it is optimal to introduce products with slower decays earlier. The structural properties of the relaxation also help us to develop several heuristics, for which we establish performance guarantees. We test our heuristics with data on sales and release dates of women's handbags from an accessories retailer. The numerical experiments show that the heuristics perform very well and can yield significant improvements in profitability.

关键词： analysis of algorithms suboptimal algorithms marketing product policy fractional programming attraction model assortment optimization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：