Approximation Algorithms for Choice Model-Based Inventory Management

Abstract

Incorporating consumer choice behavior into inventory management is essential for accurately capturing demand dynamics and optimizing inventory decisions. In this thesis, we consider two inventory control problems, and focus on the general choice models instead of traditional independent demand models.

There are three chapters in this thesis. In the first chapter, we provide an introduction and review the relevant literature. In Chapter 2, we propose a constant-factor approximation framework for the joint assortment planning and inventory management problem, where customers substitute to less preferred in-stock products if more preferred products are out of stock. This customer behavior is governed by a discrete choice model with dynamic inventory availability. Our decision involves determining the initial inventory vector, subject to a capacity constraint. Our algorithm begins with a new fluid approximation to identify at most two candidates of the most profitable assortments. For each assortment, we construct a static-allocation-based lower bound on the expected total revenue for an inventory vector that stocks only the products in the assortment. The final inventory decision is the vector that maximizes the better of these two lower bounds. We derive a state-of-the-art approximation ratio of 0.25−𝜖 for the multinomial logit (MNL) choice model and the first constant-factor approximation ratio of 0.0625 − 𝜖 for the Markov chain choice model. Both bounds can be improved to 0.333 − 𝜖 when the capacity constraint is relatively loose.

In Chapter 3, we study a periodic-review inventory control problem for a perishable product with fixed lifetime over a finite planning horizon. In each period, the retailer determines an order quantity, after which a random number of customers arrive. Each customer may have different preferences regarding product freshness, convenience, and price, leading to stochastic inventory issuance sequences that often deviate from traditional inventory issuance sequences such as first-in-first-out (FIFO) or last-in-last-out (LIFO). This diversity in customer preferences is not adequately captured by conventional issuance rules, motivating the need for a more flexible and accurate modeling approach. To address this, we adopt the Markov chain choice model to represent customer purchasing behavior. This framework generalizes and subsumes existing deterministic and probabilistic models of inventory issuance, enabling us to accurately capture the stochastic nature of the issuance sequence induced by customer choices. After fulfilling demand, inventory reaching the end of its lifetime is discarded, and the remaining inventory is carried over to the next period. Our objective is to minimize the total expected cost including ordering, holding, lost-sales penalty, and outdating costs over the planning horizon. Within this framework, we show that common issuance policies such as FIFO, LIFO, and threshold rules are special cases of the Markov chain choice model, thus unifying and extending previous analyses. We propose a modified constant-order policy, which typically orders the same quantity in each period as determined by the optimal nested assortment structure. Under certain structural assumptions on the choice model, we establish the asymptotic optimality of this policy as the customer population grows large. For general Markov chain choice models, we provide explicit suboptimality guarantees, which improve when the product’s lifetime and holding cost are small and when the lost-sales penalty is large relative to ordering costs. Numerical experiments highlight the importance of age management in perishable inventory systems and offer practical managerial insights.

Date of Award	6 Oct 2025
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Yanzhi David LI (Supervisor)