An official website of the United States government
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 assortment or opting to leave without making a selection. Assuming that these decisions are governed by the multinomial logit choice model, we define the random load of any underlying product as the total number of customers who select it. Our objective is to offer an assortment of products to each customer so that the expected maximum load across all products is maximized. We consider both static and dynamic formulations of the maximum load assortment optimization problem. In the static setting, a single offer set is carried throughout the entire process of customer arrivals, whereas in the dynamic setting, the decision maker offers a personalized assortment to each customer, based on the entire information available at that time. As can only be expected, both formulations present a wide range of computational challenges and analytical questions. The main contribution of this paper resides in proposing efficient algorithmic approaches for computing near-optimal static and dynamic assortment policies. In particular, we develop a polynomial time approximation scheme for the static problem formulation. Additionally, we demonstrate that an elegant policy utilizing weight-ordered assortments yields a 1/2 approximation. Concurrently, we prove that such policies are sufficiently strong to provide a 1/4 approximation with respect to the dynamic formulation, establishing a constant factor bound on its adaptivity gap. Finally, we design an adaptive policy whose expected maximum load is within factor 1-\epsilon of optimal, admitting a quasi-polynomial time implementation.
more »
« less
This content will become publicly available on February 10, 2026
Coordinated Inventory Stocking and Assortment Customization
Jointly Making Inventory Stocking and Assortment Offering Decisions Making the product assortment offer decisions for a customer requires keeping a balance between offering an assortment that will satisfy the current customer and reserving the products with scarce inventories for the customers who will arrive in the future. Therefore, whereas the assortment offer decisions should depend on the current inventories of the products, the stocking decisions should anticipate how the offered assortments will deplete the inventories, thereby creating a natural interaction between inventory stocking and assortment offer decisions. In “Coordinated Inventory Stocking and Assortment Customization,” Bai, El Housni, Rusmevichientong, and Topaloglu develop models that jointly make the assortment offer and inventory stocking decisions. Their models allocate the limited stocking capacity to the inventories for different products, while taking into consideration the assortment offer decisions that will be made for the customers arriving over a selling horizon.
more »
« less
- Award ID(s):
- 2226900
- PAR ID:
- 10592293
- Publisher / Repository:
- INFORMS (Institute for Operations Research and the Management Sciences)
- Date Published:
- Journal Name:
- Operations Research
- ISSN:
- 0030-364X
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider dynamic assortment problems with reusable products, in which each arriving customer chooses a product within an offered assortment, uses the product for a random duration of time, and returns the product back to the firm to be used by other customers. The goal is to find a policy for deciding on the assortment to offer to each customer so that the total expected revenue over a finite selling horizon is maximized. The dynamic-programming formulation of this problem requires a high-dimensional state variable that keeps track of the on-hand product inventories, as well as the products that are currently in use. We present a tractable approach to compute a policy that is guaranteed to obtain at least 50% of the optimal total expected revenue. This policy is based on constructing linear approximations to the optimal value functions. When the usage duration is infinite or follows a negative binomial distribution, we also show how to efficiently perform rollout on a simple static policy. Performing rollout corresponds to using separable and nonlinear value function approximations. The resulting policy is also guaranteed to obtain at least 50% of the optimal total expected revenue. The special case of our model with infinite usage durations captures the case where the customers purchase the products outright without returning them at all. Under infinite usage durations, we give a variant of our rollout approach whose total expected revenue differs from the optimal by a factor that approaches 1 with rate cubic-root of Cmin, where Cmin is the smallest inventory of a product. We provide computational experiments based on simulated data for dynamic assortment management, as well as real parking transaction data for the city of Seattle. Our computational experiments demonstrate that the practical performance of our policies is substantially better than their performance guarantees and that performing rollout yields noticeable improvements.more » « less
-
Assortment optimization finds many important applications in both brick-and-mortar and online retailing. Decision makers select a subset of products to offer to customers from a universe of substitutable products, based on the assumption that customers purchase according to a Markov chain choice model, which is a very general choice model encompassing many popular models. The existing literature predominantly assumes that the customer arrival process and the Markov chain choice model parameters are given as input to the stochastic optimization model. However, in practice, decision makers may not have this information and must learn them while maximizing the total expected revenue on the fly. In “Online Learning for Constrained Assortment Optimization under the Markov Chain Choice Model,” S. Li, Q. Luo, Z. Huang, and C. Shi developed a series of online learning algorithms for Markov chain choice-based assortment optimization problems with efficiency, as well as provable performance guarantees.more » « less
-
Problem definition: We consider network revenue management problems with flexible products. We have a network of resources with limited capacities. To each customer arriving into the system, we offer an assortment of products. The customer chooses a product within the offered assortment or decides to leave without a purchase. The products are flexible in the sense that there are multiple possible combinations of resources that we can use to serve a customer with a purchase for a particular product. We refer to each such combination of resources as a route. The service provider chooses the route to serve a customer with a purchase for a particular product. Such flexible products occur, for example, when customers book at-home cleaning services but leave the timing of service to the company that provides the service. Our goal is to find a policy to decide which assortment of products to offer to each customer to maximize the total expected revenue, making sure that there are always feasible route assignments for the customers with purchased products. Methodology/results: We start by considering the case in which we make the route assignments at the end of the selling horizon. The dynamic programming formulation of the problem is significantly different from its analogue without flexible products as the state variable keeps track of the number of purchases for each product rather than the remaining capacity of each resource. Letting L be the maximum number of resources in a route, we give a policy that obtains at least [Formula: see text] fraction of the optimal total expected revenue. We extend our policy to the case in which we make the route assignments periodically over the selling horizon. Managerial implications: To our knowledge, the policy that we develop is the first with a performance guarantee under flexible products. Thus, our work constructs policies that can be implemented in practice under flexible products, also providing performance guarantees. Funding: The work of H. Topaloglu was partly funded by the National Science Foundation [Grant CMMI-1825406]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2022.0583 .more » « less
-
We develop a variant of the multinomial logit model with impatient customers and study assortment optimization and pricing problems under this choice model. In our choice model, a customer incrementally views the assortment of available products in multiple stages. The patience level of a customer determines the maximum number of stages in which the customer is willing to view the assortments of products. In each stage, if the product with the largest utility provides larger utility than a minimum acceptable utility, which we refer to as the utility of the outside option, then the customer purchases that product right away. Otherwise, the customer views the assortment of products in the next stage as long as the customer’s patience level allows the customer to do so. Under the assumption that the utilities have the Gumbel distribution and are independent, we give a closed-form expression for the choice probabilities. For the assortment-optimization problem, we develop a polynomial-time algorithm to find the revenue-maximizing sequence of assortments to offer. For the pricing problem, we show that, if the sequence of offered assortments is fixed, then we can solve a convex program to find the revenue-maximizing prices, with which the decision variables are the probabilities that a customer reaches different stages. We build on this result to give a 0.878-approximation algorithm when both the sequence of assortments and the prices are decision variables. We consider the assortment-optimization problem when each product occupies some space and there is a constraint on the total space consumption of the offered products. We give a fully polynomial-time approximation scheme for this constrained problem. We use a data set from Expedia to demonstrate that incorporating patience levels, as in our model, can improve purchase predictions. We also check the practical performance of our approximation schemes in terms of both the quality of solutions and the computation times.more » « less
