Assortment optimization problems under new choice models and business contexts

Assortment optimization is one of the key problems in the field of revenue management. We study several assortment optimization problems under new choice models and business contexts. In the first chapter, we study an assortment optimization problem under a multi-purchase choice model in which customers choose a bundle of up to one product from each of two product categories. Different bundles have different utilities and the bundle price is the summation of the prices of products in it. For the uncapacitated setting where any set of products can be offered, we prove that this problem is strongly NP-hard. We show that an adjusted-revenue-ordered assortment provides a $\frac{1}{2}$-approximation. Furthermore, we develop an approximation framework based on a linear programming relaxation of the problem and obtain a 0.74-approximation algorithm. This approximation ratio almost matches the integrality gap of the linear program, which is proven to be at most 0.75. For the capacitated setting, we prove that there does not exist a constant-factor approximation algorithm assuming the Exponential Time Hypothesis. The same hardness result holds for settings with general bundle prices or more than two categories. Finally, we conduct numerical experiments on randomly generated problem instances. The average approximation ratios of our algorithms are over 99\%.We study an assortment optimization problem under a multi-purchase choice model in which customers choose a bundle of up to one product from each of two product categories. Different bundles have different utilities and the bundle price is the summation of the prices of products in it. For the uncapacitated setting where any set of products can be offered, we prove that this problem is strongly NP-hard. We show that an adjusted-revenue-ordered assortment provides a $\frac{1}{2}$-approximation. Furthermore, we develop an approximation framework based on a linear programming relaxation of the problem and obtain a 0.74-approximation algorithm. This approximation ratio almost matches the integrality gap of the linear program, which is proven to be at most 0.75. For the capacitated setting, we prove that there does not exist a constant-factor approximation algorithm assuming the Exponential Time Hypothesis. The same hardness result holds for settings with general bundle prices or more than two categories. Finally, we conduct numerical experiments on randomly generated problem instances. The average approximation ratios of our algorithms are over 99\%. In the second chapter, we explore assortment optimization in scenarios where retailers lack certainty regarding product availability. Such situations may arise due to the adoption of new business models, such as grocery delivery services provided by brick-and-mortar stores, or the retailers' limited capacity to monitor inventory levels for all stock-keeping units (SKUs). We formulate the assortment optimization problem that aims to maximize the retailer's expected revenue while maintaining a satisfactory service level, defined as the probability that a product ordered by a customer is indeed available. The assortment optimization problem is NP-hard. We propose a fully polynomial-time approximation scheme (FPTAS) to efficiently solve it. We also analyze the structure of the optimal solution to the joint pricing and assortment optimization problem. To validate our problem formulation and assortment optimization algorithm, we conduct extensive numerical studies using both synthetic data and transaction data from Walmart groceries. Our results demonstrate that our approach enhances both the revenue and service level of the retailer compared to benchmark methods.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Business Administration

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Zhao, Tiancheng

Contributors dc:contributor

• Mukherjee, Ujjal
• Subramanyam, Ramanath
• Seshadri, Sridhar
• Chen, Xin

• Assortment Optimization
• Pricing
• Approximation Algorithms

Statement dc:rights

• Copyright 2023 Tiancheng Zhao

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121224

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121224