Assortment optimization problems under new choice models and business contexts

Zhao, Tiancheng

Permalink

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

Description

Title

Assortment optimization problems under new choice models and business contexts

Author(s)

Zhao, Tiancheng

Issue Date

2023-07-10

Director of Research (if dissertation) or Advisor (if thesis)

• Seshadri, Sridhar
• Chen, Xin

Doctoral Committee Chair(s)

• Seshadri, Sridhar
• Chen, Xin

Committee Member(s)

• Mukherjee, Ujjal
• Subramanyam, Ramanath

Department of Study

Business Administration

Discipline

Business Administration

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Assortment optimization
• pricing
• approximation algorithms

Abstract

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.

Graduation Semester

2023-08

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Tiancheng Zhao

Owning Collections