A Re-Solving Heuristic for Dynamic Assortment Optimization With Knapsack Constraints

Abstract

In this article, we consider a multi-stage assortment optimization problem with multinomial logit (MNL) choice modeling under resource knapsack constraints. Given the current resource inventory levels, the retailer makes an assortment decision at each period, and the goal of the retailer is to maximize the total profit from purchases. With the exact optimal dynamic assortment solution being computationally intractable, a practical strategy is to adopt the re-solving technique that periodically re-optimizes deterministic linear programs (LPs) arising from fluid approximation. However, the fractional structure of MNL makes the fluid approximation in assortment optimization non-linear, which brings new technical challenges. To address this challenge, we propose a new epoch-based re-solving algorithm that effectively transforms the denominator of the objective into the constraint, so that the re-solving technique is applied to a linear program with additional slack variables amenable to practical computations and theoretical analysis. Theoretically, we prove that the regret (i.e., the gap between the re-solving policy and the optimal objective of the fluid approximation) scales logarithmically with the length of time horizon and resource capacities.

Keywords

Assortment Optimization Multinomial-Logit Choice Models Knapsack Constraints Re-Solving

1. Introduction

Assortment optimization is a core problem in revenue management, which has a wide range of applications in online retailing and advertising. For a given set of substitutable products, the assortment optimization problem refers to the selection of a subset of products (a.k.a., an assortment) offered to a customer. For example, the brand Fanta has 7 popular flavors.¹ For a Fanta vending machine with at most three slots, the assortment optimization aims at selecting at most three flavors to maximize a certain objective, such as purchasing probability or the expected revenue. One key in assortment optimization is the modeling of customer choice behavior when facing multiple products. In practice, the multi-nomial logit (MNL) model is arguably the most widely used choice model (see equation (1) for details), dating back to the foundational works of McFadden (1972); McFadden (1980); McFadden and Train (2000). Under the MNL, the single-stage assortment optimization problem is essentially a combinatorial optimization problem, which has been extensively studied in the literature (Gallego et al., 2004; Liu and van Ryzin, 2008; Mahajan and van Ryzin, 2001; Rusmevichientong et al., 2010; Talluri and van Ryzin, 2004; van Ryzin and Mahajan, 1999).

In this article, we study the multi-stage assortment optimization under resource inventory constraints. The resource inventory constraint, which is essentially a type of knapsack constraint, has been widely studied in network revenue management for multi-product pricing (Gallego and van Ryzin, 1997). Similar to the case of network revenue management, exact solutions to multi-period assortment optimization with resource constraints require an exponential number of states in a Markov decision process and is therefore computationally intractable. A fluid approximation is desirable, which replaces hard resource constraints with ones that only hold in expectation that greatly simplifies the computational burden of finding an (approximately) optimal solution. Heuristic methods such as probability sampling or resource tracking could then be proposed to match such fluid approximation solutions.

With the optimal solution to a fluid approximation formulation obtained, one effective approach to match such approximation in dynamic pricing is called “re-solving” (a.k.a., “re-optimization”) method, which periodically resolves the fluid approximation based on the left inventory level. For various dynamic pricing problems (e.g., single product vs. network revenue management, different demand models, the presence of reusable products), many re-solving techniques have been proposed and analyzed in the recent literature (see, e.g., Bumpensanti and Wang, 2020; Chen et al., 2015; Chen et al., 2019; Cooper, 2002; Jasin, 2014; Lei and Jasin, 2020; Lei et al., 2021; Maglaras and Meissner, 2006; Reiman and Wang, 2008; Secomandi, 2008; Vera et al., 2021; Wang and Wang, 2022). For network revenue management, the state-of-the-art results from Bumpensanti and Wang (2020); Wang and Wang (2022) establish constant regrets, which improve the classical $\log (T)$ regret bound (Jasin, 2014). The re-solving technique has also been applied to linear contextual bandits with knapsack constraints (Xu and anh Truong, 2021).

Despite the vast literature on re-solving for network revenue management, there is little research on re-solving for assortment optimization. One key challenge is due to the special structure of the MNL choice model (see equation (1) in Section 2). In particular, the objective arising from the MNL choice model, which is in the form of fractional programming, is non-linear, because the probability of choosing a particular product from an offered assortment is the product’s utility normalized (divided) by utility of all the other products in the offered assortment, where utilities are fixed parameters and in an MNL choice model they correspond to the exponentiated average of Gumbel valuations. In a similar vein, resource constraints involving the MNL choice model are also non-linear because they involve purchase probabilities of offered assortments that are expressed as fractions. In most existing research on re-solving, the linearity of objectives or constraints of fluid approximation plays an important role in both computation and analysis. To address the challenge brought by the non-linearity, we develop a new epoch-based re-solving algorithm. The technical novelty in our algorithm is two-fold:

Instead of re-solving the original fluid approximation, we propose a new linear programming (LP) formulation that moves the denominator of the fluid approximation into the constraint. This re-formulation not only has computational advantages, but also greatly facilitates regret analysis. By leveraging the envelop theorem (Milgrom and Segal, 2002; Terça and Wozabal, 2021), this re-formulation greatly helps the analysis of the stability of the re-solved problem.

To determine the right time for resolving, we adopt an epoch-based approach. In particular, our algorithm first resolves the original fluid approximation to estimate the number of epochs. For each epoch, we re-solve the LP and sample an assortment based on the LP solution. The sampled assortment will be offered repeatedly until no-purchase, which concludes this epoch. The idea of offering the same assortment until no-purchase is originated from Agrawal et al. (2019). However, the use of such an epoch-based strategy is for a different reason in our problem. Due to the non-linearity of the objective, if one samples an assortment at each time period, the probability of making a purchase based on the sampled assortment will not equal to the objective of the fluid approximation. On the other hand, the epoch-based sampling until no-purchase will guarantee the equality holds.

The optimal solution to the fluid approximation is in the form of a probability distribution. Converting such a distribution to actual assortment offerings is non-trivial, because hard resource capacity constraints must be satisfied. In this article, we use an efficient sampling algorithm based on the Birkhoff–von-Neumann decomposition to carry out the sampling efficiently while at the same time respecting hard capacity constraints.

With this epoch-based re-solving technique in place, the main theoretical contribution of the article is the development of the total regret, that is, the total gap of expected profit between fluid approximation solution and our policy. We proved that the total regret is logarithmic in the time horizon $T$ . Prior to this article, the works on computationally efficient methods for assortment optimization with knapsack constraints have regret on the order of $\tilde{O} (\sqrt{T})$ , by utilizing primal dual approaches (Jiang et al., 2025; Miao et al., 2025) or solving fluid approximation with $N T$ optimization variables (Lei et al., 2021), both of which are quite different from the techniques used in this article.

We also briefly mention that there is some recent literature on dynamic assortment optimization on inventory constraints (see, e.g., Chen et al., 2023; Fata et al., 2019; Golrezaei et al., 2014 and references therein). These works assume different customer types with adversarial arrivals and focus on developing competitive ratios for the worst-case performance. Under the competitive ratio criteria, recent works (Feng et al., 2024; Gong et al., 2019) further study the impact of reusable products in online assortment optimization. There is another line of research that assumes that the underlying choice model is unknown (note that we assume the utility parameters of the underlying MNL model are given). The goal is to learn the choice model and make the assortment selection simultaneously (see, e.g., Agrawal et al., 2017; Agrawal et al., 2019; Chen and Wang, 2018; Chen et al., 2020; Chen et al., 2021a; Chen et al., 2021b; Rusmevichientong et al., 2010; Saure and Zeevi, 2013). This line of research usually does not take the inventory constraint into consideration. Furthermore, when consumers’ demand model is unknown and needs to be learnt, it is theoretically not possible to achieve regret lower than $Ω (\sqrt{T})$ , as shown by the works of Agrawal et al. (2019); Chen and Wang (2018). This makes the learning-while-doing setting not directly comparable with the results derived in this article.

Regarding specifically results obtaining competitive ratios, (Golrezaei et al., 2014) studied online assortment planning with multiple consumer classes whose arrival patterns and preferences are adversarial, and derived an $1 - 1 / e$ competitive ratio for large inventory settings. With additional assumptions of stochastic arrivals, the competitive ratios can be further improved to 0.75 or 0.78. Gong et al. (2019) extends the method to reusable resources settings with random resource consumption times, improving over an earlier result of $1 / 2$ competitive ratio established in Rusmevichientong et al. (2020) for similar settings. Goyal et al. (2025) shows that when resource consumption durations are unknown, previously known methods are sub-optimal and a new policy must be designed to achieve the optimal $1 - 1 / e$ competitive ratio. We remark that, in all of the works mentioned in this paragraph, there is something inherently adversarial in the model such as arriving patterns or preference parameters in choice models, rendering competing against the best policy in hindsight impossible even with asymptotically long time horizons. In contrast, this work studies stochastic purchase behaviors of homogeneous consumers with a long time horizon, and therefore the “equivalent” competitive ratio could approach 1 as $T$ goes to infinity, and we are precisely characterizing how fast the performance of our propose policy approaches that of the optimal policy in hindsight.

The rest of the article is organized as follows. Section 2 introduces the background of the problem, including the problem setup, fluid approximations, and necessary technical assumptions. Section 3 describes the proposed re-solving policy. Section 4 provides the regret analysis and presents our main theoretical result in Theorem 1. Numerical results are given in Section 5. We conclude the article in Section 6.

2. Problem Formulation and Preliminaries

We study a stylized multi-period assortment optimization problem with knapsack constraints. At the beginning, the retailer has access to $M$ types of resources. Let us denote initial inventory for the type- $j$ resource by $C_{0, j} > 0$ for $j = 1, \dots, M$ . The retailer offers $N$ different types of substitutable products, with each unit of product $i$ consuming $A_{i j}$ units of inventory of resource $j$ . The entire dynamic assortment optimization problem consists of $T$ time periods. At the beginning of time period $t$ , the retailer offers an assortment $S_{t} \subseteq [N]$ of size at most $K$ , such that sufficient inventory levels are present for each single product in the offered assortment (i.e., $C_{t, j} \geq A_{i, j}$ for all $i \in S_{t}$ and $j \in [M]$ ). The customer then either chooses to purchase one of the presented product $i_{t} \in S_{t}$ , or leaves without purchasing anything (denoted as $i_{t} = 0$ ).

If a product $i \in S_{t}$ is purchased, the retailer collects profit $r_{i} \in [0, 1]$ and the inventory level of resource type $j \in [M]$ is depleted by an amount of $A_{i j}$ ; if no product is purchased then the retailer collects no revenue and no inventory is depleted. In this article, we use $y_{t} \in [0, 1]$ to denote the retailer’s profit at time $t$ . For notational simplicity, we denote by the $M$ -dimensional vector $C_{t} = (C_{t, 1}, \dots, C_{t, M})$ the remaining inventory for all $M$ resources at the beginning of time $t$ for $t = 0, \dots, T$ . We also denote by $A_{i, \cdot} = (A_{i, 1}, \dots, A_{i, M})$ the resource consumptions for each unit of product $i$ . Thus, if the product $i$ is purchased during the period $t$ , the remaining inventory at beginning of time $t + 1$ will be $C_{t + 1} = C_{t} - A_{i, \cdot}$ .

To model the consumers’ randomized discrete choices we use the classical multi-nomial logit (MNL) choice model. The MNL model associates each product type $i \in [N]$ with a preference score $v_{i} > 0$ (i.e., the exponential of the mean utility for the $i$ -th product). Given an assortment $S_{t} \subseteq [N]$ , the customer’s purchasing decision $i_{t}$ is governed by

Pr [i_{t} = i | S_{t}] = \frac{v_{i}}{v_{0} + \sum_{k \in S_{t}} v_{k}}, \forall i \in S_{t} \cup {0},

(1)

where

v_{0} \equiv 1

in the denominator denotes the preference score of the “no-purchase” activity, or outside options. The expected revenue of an assortment

S_{t}

can then be expressed as

R (S_{t}) = \sum_{i \in S_{t}} r_{i} Pr [i_{t} = i | S_{t}] = \frac{\sum_{i \in S_{t}} r_{i} v_{i}}{v_{0} + \sum_{i \in S_{t}} v_{i}} .

(2)

The objective of the retailer is to design a dynamic assortment optimization policy so that the expected profit is maximized subject to resource inventory constraints. More specifically, an admissible policy $π$ consists of $T$ mappings $π_{1}, π_{2}, \dots, π_{T}$ , with $π_{t}$ mapping the inventory levels $C_{t, 1}, \dots, C_{t, M}$ at the beginning of time $t$ to an assortment selection $S_{t} \subseteq [N]$ , $| S_{t} | \leq K$ . The expected total revenue for a policy $π$ with initial inventory vector $C_{0}$ can then be expressed as $V_{1}^{π} (C_{0}) = E^{π} [\sum_{t = 1}^{T} r_{i_{t}}]$ , with the understanding that $r_{0} = 0$ . Note that throughout the assortment optimization procedure, the retailer has full knowledge of the model $M = (A_{i j}, v_{i}, r_{i})_{i, j = 1}^{N, M}$ .

2.1. Fluid Approximation and Fractional Relaxations

In this section, we introduce a fluid approximation of the original DP problem. First, we introduce the following encoding scheme of an assortment. For a given assortment $S$ , we encode $S$ by a vector $x$ of length $N$ with each element $x_{i} = 1 {i \in S}$ for $i = 1, \dots, N$ . Here, the expression $1 {i \in S}$ denotes the indicator function, which takes the value 1 when $i \in S$ and the value 0 otherwise. For the computational tractability of the fluid approximation, we adopt a fractional relaxation approach by allowing $x$ to be a real-valued vector, that is, $x \in [0, 1]^{N}$ . This relaxation enables us to extend the domain of $R (\cdot)$ to $[0, 1]^{N}$ as follows:

R (x) := \frac{\sum_{i = 1}^{N} r_{i} v_{i} x_{i}}{1 + \sum_{i = 1}^{N} v_{i} x_{i}}, \forall x \in [0, 1]^{N} .

(3)

Note that for any

S \subseteq [N]

, the value of

R (x)

with

x_{i} = 1 {i \in S}

exactly matches the definition of

R (S)

in equation (2). We then introduce the fluid approximation formulation below, which maximizes

R (x)

over

x \in [0, 1]^{N}

with the inventory constraints relaxed so that they hold only in expectation:

Definition 1 (Fluid approximation)

For a given model $M = (A_{i j}, r_{i}, v_{i})_{i, j = 1}^{N, M}$ and initial inventory vector $C_{0} \in R_{+}^{M}$ , define $γ_{0, j} := C_{0, j} / T$ for all resource type $j \in [M]$ and $γ_{0} = (γ_{0, 1}, \dots, γ_{0, M}) \in R_{+}^{M}$ . The fluid approximation problem is formulated as

x^{F} := \arg max_{x \in [0, 1]^{N}} R (x) s . t . ‖ x ‖_{1} \leq K, A^{⊤} ν (x) \leq γ_{0},

(4)

where

[ν (x)]_{i} = v_{i} x_{i} / (1 + \sum_{k = 1}^{N} v_{k} x_{k})

It should be noted that the fluid approximation introduced in Definition 1 is “static” in nature because it is independent of the actual planning horizon $T$ , which is in contrast to certain “dynamic” approximation benchmarks such the “hindsight optimum” benchmark (Bumpensanti and Wang, 2020) and the dynamic programming benchmark (Wang and Wang, 2022) for network revenue management. Note that equation (4) involves the quantity $γ_{0}$ obtained by dividing the initial inventory levels $C_{0}$ by the time horizon $T$ , because it represents the target resource consumption “per period.” An interesting future direction of research would be to obtain more powerful constant regret bounds or to remove non-degeneracy conditions such as those listed in Assumption (A3), using such alternative approximation benchmarks.

The following lemma shows that Definition 1 serves as an upper bound to the expected revenues of any admissible policies, after normalization across time horizon is properly carried out.

Lemma 1

For any admissible policy $π$ over $T$ time periods, it holds that $E^{π} [\sum_{t = 1}^{T} R (S_{t})] \leq T R (x^{F})$ .

While Lemma 1 looks standard, its proof is highly non-trivial because we can no longer apply arguments involving Jensen’s inequality (which is how similar results on network revenue management are typically proved; see, e.g., Jasin, 2014; Wang and Wang, 2022) because the objective function $R (\cdot)$ in equation (4) is not concave. Instead, we construct two auxiliary LP formulations, one based on probability distributions over all possible assortments and the other based on the Charnes–Cooper transform of equation (4), and show that they share the same dual problem as equation (4), yielding the same optimal values that upper bound the value of any admissible policy $π$ .

To avoid interrupting the flow of this section, we place the complete proof of Lemma 1 in the appendix.

Remark 1

While $R (x^{F})$ upper bounds the per-period expected reward of any admissible policy, it is in general not true that $E [R (z)] = R (x^{F})$ if $E [z] = x^{F}$ , meaning that implementing a policy that uses i.i.d. assortment samples per period is likely sub-optimal in the long run. To correct for such bias, we use the strategy of offering assortments repetitively until the first no-purchase activity, which converges to $R (x^{F})$ in the long run. Further details are given in Algorithm 3 and Section 3.3 later this article.

While equation (4) has rather complex structures, it should be noted that the objective function $R (x)$ is a fractional of two linear functions of $x$ , and the constraint $A^{⊤} ν (x) \leq γ_{0}$ can be re-formulated so that it is a linear constraint in $x$ . The fluid approximation can then be efficiently solved by using fractional programming techniques, as we remark in Section 3.1 later.

Note that, when the model $M = (A_{i j}, v_{i})_{i, j = 1}^{N, M}$ and the capacity constraint $K$ is fixed, the solution and objective of the fluid approximation (4) only depends on the normalized inventory vector $γ_{0} \in R_{+}^{M}$ . Thus, we define $Φ (γ)$ as the optimal objective of the fluid approximation when the normalized inventory vector corresponds with $γ$ , or more specifically

Φ (γ) := max_{x \in [0, 1]^{N}} R (x) s . t . ‖ x ‖_{1} \leq K, A^{⊤} ν (x) \leq γ .

(5)

In this article, we also study a slightly different fluid approximation. For a normalized inventory vector $γ \in R_{+}^{M}$ and a denominator budget parameter $s \geq 1$ , define

\begin{aligned} Ψ (γ, s) & := max_{x \in [0, 1]^{N}} \sum_{i = 1}^{N} r_{i} v_{i} x_{i} \\ s . t . ‖ x ‖_{1} & \leq K, A^{⊤} ν (x) \leq γ, 1 + \sum_{i = 1}^{N} v_{i} x_{i} \leq s . \end{aligned}

(6)

Comparing

Ψ (γ, s)

with

Φ (γ)

, we note that

Ψ (γ, s)

can be converted into a linear program, making it easier to solve and analyze. The connection between

Φ

and

Ψ

is made explicit by the following lemma, which is proved in the appendix (see Appendix 6).

Lemma 2

For any $γ \geq 0$ , let $x^{F}$ be the optimal solution to $Φ (γ)$ and $s = 1 + \sum_{i = 1}^{N} v_{i} x_{i}^{F}$ . Then $Φ (γ) = R (x^{F}) = Ψ (γ, s) / s$ .

2.2. Assumptions

We make the following assumptions throughout this article.

(A1)
There exists finite constants $A_{0}, B_{0} < \infty$ such that $v_{i} \in [0, B_{0}]$ and $A_{i j} \leq A_{0}$ for all $i \in [N]$ , $j \in [M]$ ;
(A2)
There exists a positive constant $γ_{min} > 0$ such that $γ_{0, j} \geq γ_{min}$ for all $j \in [M]$ ;
(A3)
Recall the definition that $x^{F}$ is the optimal solution to the fluid approximation problem in equation (4). There exist positive constants $0 < ρ_{0}, χ_{0} < γ_{min}$ such that, for any $δ \in R^{M}, ϵ \in R$ satisfying $‖ δ ‖_{\infty} \leq ρ_{0}$ and $| ϵ | \leq ρ_{0}$ , the following hold: (a) $\sum_{i} v_{i} x_{i}^{F} > ρ_{0}$ ; (b) the set of binding/active constraints in $Ψ (γ_{0} + δ, 1 + \sum_{i} v_{i} x_{i}^{F} + ϵ)$ is the same as $Ψ (γ_{0}, 1 + \sum_{i} v_{i} x_{i}^{F})$ ; (c) after converting the $(M + 2)$ -linear constraints and $2 N$ bounded interval constraints $0 \leq x_{i} \leq 1$ of $Ψ$ into the standard form $\tilde{A} x \leq \tilde{b}$ for some numerical matrix $\tilde{A} \in R^{(M + 2 N + 2) \times N}$ , the sub-matrix of $\tilde{A}$ which corresponds to the binding constraints in $Ψ (γ_{0} + δ, 1 + \sum_{i} v_{i} x_{i}^{F} + ϵ)$ is invertible with its smallest singular value being greater than or equal to $χ_{0}$ .

Assumption (A1) assumes that the product utility parameters and the amount of resources consumed by each product sale are upper bounded. Assumption (A2) assumes that the initial inventory levels $C_{0, j}$ of all resources scale linearly with time horizon $T$ ; that is, $C_{0, j} \geq γ_{min} T$ for all $j$ , which is equivalent to $γ_{0, j} \geq γ_{min}$ where $γ_{0, j} = C_{0, j} / T$ is the normalized inventory level for resource type $j$ . Both assumptions are standard in the revenue management with inventory constraints literature (Besbes and Zeevi, 2012; Ferreira et al., 2018; Jasin, 2014; Wang et al., 2014).

Assumption (A3) is a non-degeneracy condition which needs more explanations. In essence, it assumes that the set of binding/active constraints in the re-formulated fluid approximation $Ψ (γ, s)$ is stable with respect to the input parameters, in the sense that a small perturbation of $γ$ or $s$ leads to the same set of binding/active resource constraints. It also assumes that the $M + 2 N + 2$ linear constraints in the LP formulation of $Ψ$ are “in general position,” in the sense that any of its square sub-matrices are invertible so that no row is a linear combination of fewer than $(N - 1)$ other rows/columns in the constraint matrix. At a higher level, this assumption is similar to the “non-degenerate” assumptions in the network revenue management literature (Bumpensanti and Wang, 2020; Jasin and Kumar, 2012; Wu et al., 2015), and people have shown that without certain non-degenerate conditions the re-solving heuristic does not necessarily work (Cooper, 2002). In particular, in our analysis Assumption (A3) implies that $Ψ$ is twice differentiable with respect to $γ$ and $s$ , a key property that is essential to our proof of an important Lemma 10 in the appendix. Overall, we leave the question of achieving logarithmic or even constant regret without degenerate conditions like Assumption (A3) as an interesting future direction, which likely requires new algorithms and analytical insights.
3. Re-Solving Policy

In this section, we present a re-solving policy that achieves a logarithmic regret under the assumptions (A1) through (A3). We start with two building blocks of the policy: to efficiently solve the fluid approximation problem, and to sample an assortment with its mean dictated by the fluid solution $x^{F}$ and subject to hard capacity constraints. We then present the proposed re-solving policy, and explain the design principles behind the policy. Regret analysis is presented in full details in the next section.

3.1. Solving the Fluid Approximation Problem

We first study the question of solving the fluid approximation $Φ (γ)$ efficiently. Note that $Φ (γ)$ is not a convex optimization problem: the objective function, being the ratio of two linear functions of optimization variables, is quasi-concave instead of concave. This makes classical first-order convex optimization techniques difficult to apply. Furthermore, the constraint sets are convex but it involves many constraints and therefore projection operators are difficult to design. Therefore, it is challenging to apply standard (projected) first-order optimization methods to solve $Φ (γ)$ .

In this section, we show that with some simple transforms the fluid approximation can be reduced to a series of LP problems, which can be subsequently solved efficiently using existing optimization software or packages.

The pseudocode description of the algorithm that solves the fluid approximation problem is given in Algorithm 1. The $λ$ parameter in the algorithm serves as a lower bound of the objective function. The idea of bi-section search of $λ$ is due to the work by Rusmevichientong et al. (2010), whose ideas can be traced back to fractional programming works by Megiddo (1979). More specifically, it is a simple observation that for any $λ \in [0, 1]$ , the optimal objective value in $Φ (γ)$ is larger than or equal to $λ$ if and only if the optimal objective value in equation (7) is larger than or equal to $λ$ , because for any feasible $x$ we have that $\frac{\sum_{i} r_{i} v_{i} x_{i}}{1 + \sum_{i} v_{i} x_{i}} \geq λ ⟺ \sum_{i} (1 - λ) r_{i} v_{i} x_{i} \geq λ$ . Consequently, we use a binary search approach to locate the largest $λ$ value for which the objective in equation (7) is at least $λ$ , which is then the optimal solution to the original $Φ (γ)$ problem. The formal proof of Lemma 3 is placed in the appendix (see Appendix 6).

Lemma 3
For any $ϵ \in (0, 1)$ , Algorithm 1 returns a solution ${\hat{x}}^{F} \in [0, 1]^{N}$ feasible to all constrains imposed in $Φ (γ)$ satisfying $R ({\hat{x}}^{F}) \geq Φ (γ) - ϵ$ by solving $O (\log (1 / ϵ))$ LPs with $N$ variables and $(M + 1)$ constraints.

Because the convergence of Algorithm 1 is very fast (logarithmic in the inverse of precision parameter $ϵ$ ), in the rest of the article we shall assume that Algorithm 1 returns exactly the optimal fluid solution $x^{F}$ such that $R (x^{F}) = Φ (γ)$ .
3.2. Sampling From the Fluid Solution

In Algorithm 2 we present a computationally efficient routine SampleAssortment to obtain a random assortment sample whose expected value is equal to a given fractional vector $x \in [0, 1]^{N}$ . Because the sampled assortment must satisfy a hard capacity constraint, it cannot be obtained by simply drawing independent product samples. Instead, we use a method based on the Birkhoff–von-Neumann decomposition of doubly stochastic matrices to implement the weighted sampling procedure. Similar method has been used for the classical question of fair random assignment (Budish et al., 2013), a problem that is similar in nature to the sampling question we have.

Below we explain the ideas of Algorithm 2 in more details. First, we manipulate the obtained solution $x$ (with $‖ x ‖_{1} \leq K$ ) such that the cardinality constraint is always tight, that is, $‖ x ‖_{1} = K$ . To this end, we construct $K$ additional “dummy” choices corresponding to “no product,” each with weight $1 - ‖ x ‖_{1} / K$ (see Line 2 in Algorithm 2). Then, the key step is to construct a doubly stochastic matrix $M$ (i.e., a matrix whose elements are in $[0, 1]$ , with every row and column of the matrix summing to one) where the first $K$ rows of $M$ are $x / K$ , and the last $N$ rows of $M$ are $(1 - x) / N$ . It is easy to verify that $M$ is an $(N + K) \times (N + K)$ doubly stochastic matrix. We then use the Birkhoff–von-Neumann algorithm (see, e.g., Dufossé and Uçar, 2016) to decompose the matrix $M$ into a weighted sum of permutation matrices $P_{1}, \dots, P_{L}$ :

M = α_{1} P_{1} + \dots + α_{L} P_{L},

where each

P_{ℓ}

corresponds to a permutation

σ_{ℓ} : [N + K] \to [N + K]

P_{ℓ, i j} = 1 {i = σ_{ℓ} (j)}

, and

α_{1}, \dots, α_{L} \in [0, 1]

α_{1} + \dots + α_{L} = 1

forms a convex combination of the involved permutation matrices. It is known that

M

can be decomposed into at most

L = (N + K)^{2}

permutation matrices, with the decomposition being computed in

O ((N + K)^{4})

time. The algorithm then samples a permutation matrix

P_{ℓ}

with probability

α_{ℓ}

, and reads out the first

K

rows of

P_{ℓ}

as the selected products in the returned assortment (see Line 6 in Algorithm 2). A rigorous proof of Proposition 1 is given in the appendix (see Appendix 6).

Proposition 1
Let $z \in {0, 1}^{N}$ be the output of Algorithm 2. Then $‖ z ‖_{1} \leq K$ almost surely and $E [z_{i}] = x_{i}$ for all $i \in [N]$ .
Remark 2
While directly applying the Birkhoff–von-Neumann algorithm leads to $L \leq (N + K)^{2}$ permutation matrices and $O ((N + K)^{4})$ time complexity for decomposing $M$ , it is possible to reduce the time complexity by utilizing the special structures of the doubly stochastic matrix $M$ constructed in our problem. In Appendix 6 we present a reduced form of the Birkhoff–von-Neumann algorithm that decomposes $M$ into $L \leq N + K$ permutation matrices with time complexity $O ((N + K)^{2})$ .
3.3. An Epoch-Based Algorithm With Re-Solving

Based on the fluid solution $x^{F}$ and the SampleAssortment( $x, K$ ) sub-routine, we are ready to describe an epoch-based policy with re-solving heuristics in Algorithm 3.

The first step of Algorithm 3 is to compute the fractional solution $x^{F}$ to the fluid approximation $Φ (γ_{0})$ . The algorithm then computes $τ_{0} = T / (1 + \sum_{i} v_{i} x_{i}^{F})$ , which is the expected number of epochs corresponding to $x^{F}$ if hypothetically $x^{F}$ is used throughout the entire $T$ time periods, because sampling assortments with respect to $x^{F}$ leads to $\sum_{i} v_{i} x_{i}^{F}$ number of consecutive purchases in expectation before the first no-purchase activity, as observed in (Agrawal et al., 2019: Corollary A.1).²

Afterwards, Algorithm 3 operates in epochs, separated by no-purchase activities. More specifically, an epoch consists of consecutive time periods starting with a time period immediately following one during which no purchase is made, and ending with the first time period during which no purchase is made by the arriving customer. After each no-purchase activity and the end of an epoch, the algorithm re-solves a fluid approximation, using the remaining number of inventories, time periods and epochs as input parameters. Note that the fluid approximation used in the resolving procedure $Ψ (γ^{τ}, s^{τ})$ has different formulation from the fluid approximation $Φ (γ_{0})$ solved at the beginning of the algorithm, and $Ψ (γ^{τ}, s^{τ})$ is a standard linear program. The reason for using a different fluid approximation formulation in the resolving steps is given in the next paragraph. After a new updated fractional solution $x^{τ}$ is obtained, the assortment to be offered for the next few customers is sampled from $x^{τ}$ using the sampling strategy outlined in Algorithm 2.

Compared with many existing re-solving heuristics (see, e.g., Jasin and Kumar, 2012; Jasin, 2014), there are two noticeable unique properties of Algorithm 3: that the re-solving optimization problems are different from the fluid approximation, and that each sampled assortment is offered repeatedly. We remark on the motivations of the two key design ideas as follows:

The primary motivation for using a different optimization problem in equation (8) from the direct fluid approximation $Φ (\cdot)$ is to ensure that the re-solving problem is a standard LP. This not only has computational advantages, but also offers an effective way to analyze the stability of the re-solved problem through the envelope theorem. To ensure that the LP problems are good approximation of the original fluid problem $Φ (\cdot)$ , we transform the denominator in the $Φ (\cdot)$ objective as a standalone constraint $1 + \sum_{i} v_{i} x_{i} \leq s^{τ}$ to make sure that the obtained continuous solution $x^{τ}$ will not have too large value in the denominator of $R (x) = (\sum_{i} v_{i} x_{i}) / (1 + \sum_{i} v_{i} x_{i})$ .

The “epoch-based approach” (i.e., offering the same assortment $S^{τ}$ repeatedly until the first no-purchase action occurs) was proposed and analyzed in the seminal work of Agrawal et al. (2019) to facilitate convenient estimates of parameters in an MNL choice model. More specifically, with an epoch-based approach the expected revenue during an epoch has a simple linear form in the product utility parameters, leading to more convenient theoretical analysis. In Algorithm 3, the epoch-based approach is adopted for a different motivation, to get around the non-linearity of $R (\cdot)$ . More specifically, if one samples a random assortment $z$ for every single time period, the probability of making a purchase when offering $z$ will not equal the objective of the fluid approximation (i.e., $E_{z \sim x} [R (z)] \neq R (E_{z \sim x} [z]) = R (x)$ ). By using the epoch-based approach, we decouple the numerator and denominator in the purchasing probability function $R (\cdot)$ and utilizing the linearity of $x$ in both the numerator and denominator of $R (\cdot)$ .

Finally, we remark on the computational efficiency of Algorithm 3. The main computational bottleneck is to re-solve an LP with $N$ variables and $M + 2$ constraints every epoch, and to sample from the fractional solution $x^{τ}$ using Algorithm 2, which takes time $O (N^{4})$ if implemented naively or $O (N^{2})$ with a better implementation given in the appendix. Overall, the total time complexity of Algorithm 3 is polynomial in $N$ and linear in $T$ . This is much faster than other alternatives, which have time complexity either exponential in $N$ (e.g., solving a multi-variable dynamic programming with discretized inventory levels) or quadratic/cubic in $T$ (e.g., solving a fluid approximation with $N T$ variables, such as in the works of Lei et al. (2021)).

4. Regret Analysis

For an admissible policy $π$ that respects resource inventory constraints almost surely, its regret is defined as the expected difference between the policy’s cumulative revenue over $T$ time periods and the cumulative revenue over $T$ time periods of the optimal DP policy, which is upper bounded by $R (x^{F})$ multiplied by $T$ thanks to Lemma 1, where $R (x^{F})$ is the optimal objective value of equation (4). Subsequently, for any admissible policy $π$ , its regret is upper bounded by

Regret (π) \leq T R (x^{F}) - E^{π} [\sum_{t = 1}^{T} R (S_{t})],

where

R (S_{t})

is the expected revenue of assortment

S_{t}

defined in equation (2). Note that, because

T R (x^{F})

upper bounds the cumulative expected revenue of any admissible policy, including the optimal one, the right-hand side of the above inequality is always non-negative for any admissible policy

π

, and a smaller regret indicates a policy with better performance.

The main objective of this section is to establish the following theorem that upper bounds the regret of Algorithm 3.

Theorem 1
Fix model $M = (A_{i j}, v_{i})_{i, j = 1}^{N, M}$ and normalized initial inventory vector $γ_{0} \in R_{+}^{M}$ that satisfy Assumptions (A1) through (A3) with parameters $A_{0}, B_{0}, γ_{min}$ and $ρ_{0}$ . Then for any $T$ , the regret of Algorithm 3 is upper bounded by
$const . \times \frac{A_{0}^{2} B_{0}^{7} K^{5} M^{2} N \ln T}{min {ρ_{0}^{2}, χ_{0}^{2}}},$
where $const .$ is a finite, universal numeric constant.
Remark 3
Theorem 1 shows that under Assumptions (A1) through (A3), the cumulative regret of Algorithm 3 scales logarithmically with the time horizon $T$ as $T$ increases to infinity.

In the rest of this section we present the proof of Theorem 1. To facilitate the proof we first define some key notations. For epoch $τ$ , define $n^{τ} (i)$ , $m^{τ}$ and $β^{τ}$ as follows: -
$n^{τ} (i)$ : the number of times product $i$ is purchased during epoch $τ$ ;
-
$m^{τ}$ : the length of epoch $τ$ , or $m^{τ} = 1 + \sum_{i = 1}^{N} n^{τ} (i)$ ;
-
$β^{τ}$ : the total revenue collected during the epoch $τ$ , or $β^{τ} = \sum_{i = 1}^{N} r_{i} n^{τ} (i)$ .
We also recall the definitions of $γ^{τ}, t^{τ}$ and $s^{τ}$ in Algorithm 3, representing the normalized remaining inventory, the number of remaining time periods over the entire time horizon of $T$ periods, and the normalized epoch size at the beginning of epoch $τ$ .
4.1. Recursion of $γ^{τ}$ and $s^{τ}$

Because the re-solved optimization problem $Ψ (γ^{τ}, s^{τ})$ crucially depends on $γ^{τ}$ and $s^{τ}$ , it is essential to analyze the recursion and evolving of both parameters across epochs. For a complete epoch $τ$ (a complete epoch is one that terminates without running out of inventory or reaching the time horizon $T$ , and therefore ends exactly on a time period during which no purchase occurs), define ${Δ^{τ} (i)}_{i = 1}^{N}$ and $Δ^{τ}$ as

Δ^{τ} (i) := n^{τ} (i) - v_{i} x_{i}^{τ}, Δ^{τ} := \sum_{i = 1}^{N} Δ^{τ} (i) .

(9)

The following lemma shows that

{Δ^{τ} (i)}_{i = 1}^{N}

(and subsequently

Δ^{τ}

as well) are conditionally centered random variables.

Lemma 4

For every complete epoch $τ$ and product $i \in [N]$ , $E [Δ^{τ} (i) | γ^{τ}, s^{τ}] = 0$ .

Proof. Proof of Lemma 4.

The proof is conditioned on $γ^{τ}$ and $s^{τ}$ . It is a well-known result (see, e.g., Agrawal et al., 2019, Corollary A.1) that $n^{τ} (i)$ is a geometrically distributed random variable with mean $E [n^{τ} (i) | z^{τ}] = z_{i}^{τ} v_{i}$ . Furthermore, by Proposition 1 we have $E [z_{i}^{τ} | x^{τ}] = x_{i}^{τ}$ . Lemma 4 is thus proved using the law of total expectation.

The following lemma is the key recursion formula for $γ^{τ}$ and $s^{τ}$ :

Lemma 5
Let $τ > 1$ be a complete epoch. Then
$\begin{aligned} s^{τ - 1} \geq s^{τ} - \frac{Δ^{τ}}{τ - 1}, \\ γ_{j}^{τ - 1} \geq γ_{j}^{τ} - \frac{[\sum_{i = 1}^{N} A_{i j} Δ^{τ} (i)] - min {γ_{j}^{τ}, A_{0} B_{0} K} Δ^{τ}}{t^{τ - 1}}, \\ \forall j \in [M] . \end{aligned}$

Lemma 5 is proved by painstakingly tracking the definitions and dynamics governing $s^{τ}$ and $γ^{τ}$ , and making relaxations to simplify lower bounds on these two quantities when necessary.
Proof. Proof of Lemma 5.

From Algorithm 3, for any resource type $j$ and epoch $τ$ , $γ_{j}^{τ} = C_{T - t^{τ} + 1, j} / t^{τ}$ where $t^{τ}$ is the remaining number of time periods at the beginning of epoch $τ$ and $C_{t - t^{τ} + 1, j}$ is the remaining amount of inventory for resource type $j$ at the beginning of epoch $τ$ . Similarly, $γ_{j}^{τ - 1} = C_{T - t^{τ - 1} + 1, j} / t^{τ - 1}$ . Note also that $C_{t - t^{τ} + 1, j} - C_{t - t^{τ - 1} + 1, j}$ is the amount of consumption of resource type $j$ during epoch $τ$ , which is equal to $\sum_{i, j = 1}^{N} A_{i j} n^{τ} (i)$ where $A$ is the resource consumption matrix and $n^{τ} (i)$ is the number of times product $i$ is purchased during epoch $τ$ . Subsequently,

\begin{aligned} γ_{j}^{τ - 1} & = \frac{γ_{j}^{τ} t^{τ} - \sum_{i = 1}^{N} A_{i j} n^{τ} (i)}{t^{τ - 1}} = \frac{γ_{j}^{τ} (t^{τ - 1} + m^{τ}) - \sum_{i = 1}^{N} A_{i j} n^{τ} (i)}{t^{τ - 1}} \\ = γ_{j}^{τ} + \frac{γ_{j}^{τ} [1 + \sum_{k} v_{k} x_{k}^{τ}] - \sum_{i = 1}^{N} A_{i j} v_{i} x_{i}^{τ}}{t^{τ - 1}} \\ - \frac{\sum_{i = 1}^{N} A_{i j} Δ^{τ} (i) - γ_{j}^{τ} Δ^{τ}}{t^{τ - 1}} \geq γ_{j}^{τ} \\ - \frac{\sum_{i = 1}^{N} A_{i j} Δ^{τ} (i) - γ_{j}^{τ} Δ^{τ}}{t^{τ - 1}}, \end{aligned}

where the last inequality holds with probability 1 because

\sum_{i = 1}^{N} A_{i j} v_{i} x_{i}^{τ} \leq γ_{j}^{τ} [1 + \sum_{k} v_{k} x_{k}^{τ}]

for every

j \in [M]

thanks to the constraints equation (8) in the optimization problem

Ψ

. When

γ_{j}^{τ} \geq A_{0} B_{0} K

, we use the facts that

m_{τ} \geq 1

and

\sum_{i = 1}^{N} A_{i j} v_{i} x_{i}^{τ} \leq A_{0} B_{0} ‖ x^{τ} ‖_{1} \leq A_{0} B_{0} K

to alternatively decompose

γ_{j}^{τ - 1}

\begin{aligned} γ_{j}^{τ - 1} & = \frac{γ_{j}^{τ} (t^{τ - 1} + m^{τ}) - \sum_{i = 1}^{N} A_{i j} n^{τ} (i)}{t^{τ - 1}} \geq γ_{j}^{τ} \\ + \frac{A_{0} B_{0} K m^{τ} - \sum_{i = 1}^{N} A_{i j} n^{τ} (i)}{t^{τ - 1}} \\ \geq γ_{j}^{τ} + \frac{A_{0} B_{0} K [\sum_{i = 1}^{N} n^{τ} (i)]}{t^{τ - 1}} - \frac{\sum_{i = 1}^{N} A_{i j} Δ^{τ} (i)}{t^{τ - 1}} \\ = γ_{j}^{τ} + \frac{A_{0} B_{0} K [\sum_{i = 1}^{N} v_{i} x_{i}^{τ}]}{t^{τ - 1}} + \frac{A_{0} B_{0} K Δ^{τ}}{t^{τ - 1}} \\ - \frac{\sum_{i = 1}^{N} A_{i j} Δ^{τ} (i)}{t^{τ - 1}} \\ \geq γ_{j}^{τ} - \frac{\sum_{i = 1}^{N} A_{i j} Δ^{τ} (i) - A_{0} B_{0} K Δ^{τ}}{t^{τ - 1}} \geq γ_{j}^{τ} \\ - \frac{\sum_{i = 1}^{N} A_{i j} Δ^{τ} (i) - min {γ_{j}^{τ}, A_{0} B_{0} K Δ^{τ}}}{t^{τ - 1}}, \end{aligned}

where the last inequality holds because the

A_{0} B_{0} K Δ^{τ}

term in the numerator is associated with a positive sign and therefore taking a minimum between it and

γ_{j}^{τ}

does not increase the right-hand side of the inequality. This proves the inequality on

γ_{j}^{τ - 1}

. We next consider

s^{τ - 1}

. By definition,

s^{τ} = t^{τ} / τ

(see Algorithm 3 for the definition of

s^{τ}

). Note also that

t^{τ - 1} = t^{τ} - m^{τ}

, where

m^{τ}

is the number of time periods involved in epoch

τ

. Subsequently,

s^{τ - 1} = \frac{t^{τ - 1}}{τ - 1} = \frac{t^{τ} - m^{τ}}{τ - 1} = \frac{s^{τ} τ - m^{τ}}{τ - 1} = s^{τ} + \frac{s^{τ} - m^{τ}}{τ - 1} = s^{τ} + \frac{s^{τ} - [1 + \sum_{i} v_{i} x_{i}^{τ}]}{τ - 1} - \frac{Δ^{τ}}{τ - 1} \geq s^{τ} - \frac{Δ^{τ - 1}}{τ - 1}

, where the last inequality holds because

1 + \sum_{i} v_{i} x_{i}^{τ} \leq s^{τ}

thanks to constraint equation (8) in the optimization problem

Ψ

. This proves the recursion inequality about

s^{τ - 1}

Lemmas 4 and 5 show that ${s^{τ}, γ^{τ}}_{τ}$ are sub-martingales: $E [s^{τ - 1} | s^{τ}] \geq s^{τ}$ and $E [γ^{τ - 1} | γ^{τ}] \geq γ^{τ}$ . For convenience, we also define the following notations:

\begin{aligned} ε^{τ} (j) & := \frac{\sum_{i = 1}^{N} A_{i j} Δ^{τ} (i) - min {γ_{j}^{τ}, A_{0} B_{0} K} Δ^{τ}}{t^{τ - 1}}, \\ ε^{\to τ} (j) & := \sum_{τ^{'} = τ}^{τ_{0}} ε^{τ^{'}} (j), Δ^{\to τ} := \sum_{τ^{'} = τ}^{τ_{0}} Δ^{τ^{'}} . \end{aligned}

(10)

Intuitively,

Δ^{τ}

is the time-normalized deviation of expected epoch lengths at epoch

τ

ε^{τ} (j)

is the time-normalized deviation of consumption of resource type

j

at epoch

τ

, and

Δ^{\to τ}

ε^{\to τ}

are cumulative deviations of corresponding quantities for all epochs prior to

τ

. Note also that

γ^{τ_{0}} = γ_{0}

and

s^{τ_{0}} = 1 + \sum_{i} v_{i} x_{i}^{F}

. Lemma 5 then implies that for every complete epoch

τ

and resource type

j \in [M]

γ_{j}^{τ - 1} \geq γ_{0, j} - ε^{\to τ} (j), s^{τ - 1} \geq 1 + \sum_{i} v_{i} x_{i}^{F} - Δ^{\to τ} .

(11)

For convenience we also define the martingales version of

{s^{τ}, γ^{τ}}_{τ}

{\tilde{γ}}_{j}^{τ - 1} := γ_{0, j} - ε^{\to τ} (j), {\tilde{s}}^{τ - 1} := 1 + \sum_{i} v_{i} x_{i}^{F} - Δ^{\to τ} .

(12)

It is clear from equation (11) that

{\tilde{γ}}^{τ} \leq γ^{τ}

and

{\tilde{s}}^{τ} \leq s^{τ}

for all

τ

almost surely.

4.2. Analysis of Stopping Time

Let $τ \circ$ be the last complete epoch during which the inventory levels of all resources remain positive and the time horizon $T$ is not reached. Because the dynamic assortment optimization procedure either terminates or has very poor performance after epoch $τ \circ$ , it is vital to upper bound the (expected value) of $τ \circ$ to ensure that there are enough complete epochs. This is the objective of this section.

To upper bound $E [τ \circ]$ we first define $τ \circ$ using the tracked quantities ${γ^{τ}, s^{τ}}$ . Note that if $γ_{j}^{τ} > 0$ then the inventory level of resource type $j$ is not depleted at the beginning of epoch $τ$ . Also, if $s^{τ} \geq 0$ then the time horizon $T$ has not yet been reached. Therefore, we have $τ \circ = min {τ : \forall τ^{'} \geq τ, γ^{τ^{'}} \geq 0 \land s^{τ^{'}} \geq 0} + 1$ . To allow the usage of stability results (to be established in the next section) of $Ψ$ defined in equation (6) earlier, we actually study a stopping time $τ^{♯}$ that upper bounds $τ \circ$ almost surely. More specifically, define

\begin{aligned} τ^{♯} := min {τ : \forall τ^{'} \geq τ, ‖ {\tilde{γ}}^{τ^{'}} - γ_{0} ‖_{\infty} \leq ρ_{0} \land | {\tilde{s}}^{τ^{'}} - s^{τ_{0}} | \leq ρ_{0}} + 1, \end{aligned}

(13)

where

\land

is the logical “AND” operator. It is easy to see that

τ^{♯}

is a stopping time and satisfies

τ^{♯} \geq τ \circ

almost surely, thanks to Assumption (A3) and the fact that

γ^{τ} \geq {\tilde{γ}}^{τ}

s^{τ} \geq {\tilde{s}}^{τ}

almost surely. Note that

| {\tilde{s}}^{τ^{'}} - s^{τ_{0}} | \leq ρ_{0}

implies

s^{τ^{'}} \geq s^{τ_{0}} - ρ_{0} = 1 + \sum_{i} v_{i} x_{i}^{F} - ρ_{0} \geq 1

thanks to Assumption (A3). The following Lemma gives an upper bound on

E [τ^{♯}]

Lemma 6

It holds that $E [τ^{♯}] \leq const . \times A_{0}^{2} B_{0}^{4} K^{4} M \ln T / ρ_{0}^{2}$ .

Proof. Proof of Lemma 6.

The first part of the proof is to upper bound $| {\tilde{s}}^{τ} - s^{τ_{0}} | = | Δ^{\to τ} |$ . Recall the definition that $Δ^{\to τ} = \sum_{τ^{'} = τ}^{τ_{0}} Δ^{τ^{'}} / (τ^{'} - 1)$ , where $Δ^{τ^{'}} = \sum_{i = 1}^{N} n^{τ^{'}} (i) - v_{i} x_{i}^{τ^{'}}$ . Now fix $τ = τ^{'} \geq τ^{♯}$ and decompose $Δ^{τ}$ as $Δ^{τ} = [\sum_{i = 1}^{N} v_{i} x_{i}^{F} - \sum_{i \in S^{τ}} v_{i}] + [\sum_{i \in S^{τ}} (n^{τ} (i) - v_{i})]$ . For the first term, note that both quantities are upper bounded by $B K$ almost surely. Hence,

E [| \sum_{i = 1}^{N} v_{i} x_{i}^{F} - \sum_{i \in S^{τ}} v_{i} |^{2}] \leq B_{0}^{2} K^{2} .

(14)

For the second term, note that for each

i \in S^{τ}

(

S^{τ}

is the assortment offered for all time periods in epoch

τ

), we have

Pr [n^{τ} (i) = n] = \frac{1}{1 + v_{i}} {(\frac{v_{i}}{1 + v_{i}})}^{n} = (1 - p_{i}) p_{i}^{n}

(Agrawal et al., 2019: Corollary A.1), where we define

p_{i} := v_{i} / (1 + v_{i})

, implying

E [n^{τ} (i)] = v_{i}

. Hence,

E [| n^{τ} (i) - v_{i} |^{2}] \leq E [(n^{τ} (i))^{2}] = (1 - p_{i}) \sum_{n = 0}^{\infty} n^{2} p_{i}^{n} = \frac{(1 + p_{i}) p_{i}}{(1 - p_{i})^{2}} = v_{i} (2 + v_{i}) \leq 2 B_{0}^{2} .

Noting that

(a_{1} + \dots + a_{K})^{2} \leq K^{2} (a_{1}^{2} + \dots + a_{K}^{2})

, we have that

E [| \sum_{i \in S^{τ}} (n^{τ} (i) - v_{i}) |^{2}] \leq 2 K^{2} B_{0}^{2} .

(15)

Combining equations (14,15) we have

E [| Δ^{τ} |^{2}] \leq 2^{2} \times (1 + 2) K^{2} B_{0}^{2} = 12 K^{2} B_{0}^{2}

. Note also that

{Δ^{τ}}

is a martingale difference sequence and therefore

E [Δ^{τ} | Δ^{1}, \dots, Δ^{τ - 1}] = 0

. Subsequently,

E [| Δ^{\to τ} |^{2}] = \sum_{ℓ = τ}^{τ_{0}} \frac{E [(Δ^{ℓ})^{2}]}{(ℓ - 1)^{2}} \leq 12 K^{2} B_{0}^{2} \times \int_{τ - 2}^{\infty} \frac{d u}{u^{2}} = \frac{12 K^{2} B_{0}^{2}}{τ - 2} .

(16)

Next, note that ${Δ^{\to τ^{'}}}_{τ^{'}}$ is a martingale difference sequence. Therefore, ${(Δ^{\to τ^{'}})^{4}}_{τ^{'}}$ is a sub-martingale. By Doob’s martingale inequality we have

Pr [sup_{τ \leq τ^{'} \leq τ_{0}} | Δ^{\to τ^{'}} | > ρ_{0}] \leq \frac{E [| Δ^{\to τ} |^{2}]}{ρ_{0}^{2}} \leq \frac{12 K^{2} B_{0}^{2}}{ρ_{0}^{2} (τ - 2)} .

(17)

We next focus on ${\tilde{γ}}_{j}^{τ}$ for some resource type $j \in [M]$ . Decompose the first term of $ε^{τ} (j) = \sum_{i = 1}^{N} A_{i j} Δ^{τ} (i) - min {γ_{j}^{τ}, A_{0} B_{0} K} Δ^{τ}$ as $\sum_{i = 1}^{N} A_{i j} Δ^{τ} (i) = [\sum_{i = 1}^{N} A_{i j} v_{i} x_{i}^{τ} - \sum_{i \in S^{τ}} A_{i j} v_{i}] + [\sum_{i \in S^{τ}} A_{i j} (n^{τ} (i) - v_{i})]$ . With $A_{i j} \leq A_{0}$ for all $i \in [N]$ , $\sum_{i = 1}^{N} v_{i} x_{i}^{τ} \leq B_{0} ‖ x^{τ} ‖_{1} \leq B_{0} K$ and equation (16), we have that $E [| ε^{τ} (j) |^{2}] \leq 9 (A_{0}^{2} B_{0}^{2} K^{2} + 12 A_{0}^{2} B_{0}^{2} K^{2} + A_{0}^{2} B_{0}^{2} K^{2} \times 12 B_{0}^{2} K^{2}) \leq 2700 A_{0}^{2} B_{0}^{4} K^{4} .$ Subsequently, using the same analysis as in equation (16), we have

E [| ε^{\to τ} (j) |^{2}] = \sum_{ℓ, ℓ^{'} = τ}^{τ_{0}} \frac{E [(ε^{ℓ} (j))^{2} (ε^{ℓ^{'}} (j))^{2}]}{(ℓ - 1)^{2} (ℓ^{'} - 1)^{2}} \leq \frac{2700 A_{0}^{2} B_{0}^{4} K^{4}}{τ - 2},

(18)

where

const .

is a numerical constant omitted here for presentation purposes. Note that

{ε^{τ^{'}} (j)}_{τ^{'}}

is a martingale difference sequence. This implies

{| ε^{τ^{'}} (j) |^{4}}_{τ^{'}}

is a sub-martingale difference sequence. By Doob’s martingale inequality we have

\begin{aligned} Pr [sup_{τ \leq τ^{'} \leq τ_{0}} | ε^{\to τ^{'}} (j) | > ρ_{0}] \leq \frac{E [| ε^{\to τ} (j) |^{2}]}{ρ_{0}^{2}} \leq \frac{2700 A_{0}^{2} B_{0}^{4} K^{4}}{ρ_{0}^{2} (τ - 2)} . \end{aligned}

(19)

Combining equations (17, 19) and using the union bound, we have

\begin{aligned} E [τ^{♯}] & = 2 + \sum_{τ = 3}^{τ_{0}} Pr [τ^{♯} \geq τ] \\ \leq \sum_{τ = 2}^{τ_{0}} Pr [\forall τ^{'} > τ, | Δ^{\to τ^{'}} | \leq ρ \land | ε^{\to τ} (j) | \leq ρ, \forall j \in [M]] \\ \leq 2 + \sum_{τ = 3}^{τ_{0}} (M + 1) \times const . \times \frac{A_{0}^{2} B_{0}^{4} K^{4}}{ρ_{0}^{2} (τ - 2)} \\ \leq const . \times A_{0}^{2} B_{0}^{4} K^{4} M \ln T / ρ_{0}^{2}, \end{aligned}

proves the desired result. Here,

const .

is a placeholder for a numerical, absolute constant independent of any problem parameters or constants involved in technical assumptions.

4.3. Stability Analysis of

Ψ

The third building block of our proof to Theorem 1 is to analyze the maximum objective value of $Ψ (γ^{τ}, s^{τ})$ for constraint parameters $γ^{τ}, s^{τ}$ that deviates from $γ_{0}$ and $s^{τ_{0}} = 1 + \sum_{i} v_{i} x_{i}^{F}$ . The following lemma analyzes such deviation in terms of $ε^{\to τ} = {ε^{\to τ} (j)}_{j = 1}^{M} \in R^{M}$ and $Δ^{\to τ}$ defined in equation (8).

Lemma 7
There exists a fixed vector $η_{γ} \in R_{+}^{M}$ and scalars $η_{s}, η_{h} \geq 0$ depending only on $M = (A_{i j}, v_{i})_{i, j = 1}^{N, M}$ , $K$ , $γ_{0}$ such that the following holds:
$\begin{aligned} Ψ (γ^{τ}, s^{τ}) & \geq Ψ ({\tilde{γ}}^{τ}, {\tilde{s}}^{τ}) \geq Ψ (γ_{0}, s^{τ_{0}}) - ⟨ η_{γ}, ε^{\to τ} ⟩ \\ - η_{s} Δ^{\to τ} - η_{h} (‖ ε^{\to τ} ‖_{2}^{2} + | Δ^{\to τ} |^{2}) . \end{aligned}$
Furthermore, the scalar $η_{h}$ satisfies $η_{h} \leq \frac{8 M^{2} K N B_{0}^{3}}{χ_{0}^{2}}$ .
Proof. Proof of Lemma 7.

The first inequality trivially holds because any solution feasible to $Ψ ({\tilde{γ}}^{τ}, {\tilde{s}}^{τ})$ is also feasible to $Ψ (γ^{τ}, s^{τ})$ , since $γ^{τ} \geq {\tilde{γ}}^{τ}$ and $s^{τ} \geq {\tilde{s}}^{τ}$ almost surely.

By Assumptions (A3), the set of binding/active constraints are the same for all ${(γ, s) : ‖ γ - γ_{0} ‖_{\infty} \leq ρ_{0} \land | s - s^{τ_{0}} | \leq ρ_{0}}$ . It is a standard result that this condition implies the differentiability of $Ψ (\cdot, \cdot)$ on ${(γ, s) : ‖ γ - γ_{0} ‖_{\infty} \leq ρ_{0} \land | s - s^{τ_{0}} | \leq ρ_{0}}$ (see, e.g., Gal and Greenberg, 2012; Terça and Wozabal, 2021). The derivative of $Ψ (\cdot, \cdot)$ can also be calculated by using the celebrated envelope theorem (Milgrom and Segal, 2002, see also Takayama, 1985: Theorem 1.F.1, (Terça and Wozabal, 2021: Theorem 1)). More specifically, let $x^{*}$ be the optimal solution to $Ψ (γ, η)$ , $λ_{j}^{*}$ be the Lagrangian multiplier of the constraint $\sum_{i = 1}^{N} A_{i j} v_{i} x_{i} \leq γ_{j}^{τ} (1 + \sum_{i = 1}^{N} v_{i} x_{i})$ and $λ_{s}^{*}$ be the Lagrangian multiplier of the constraint $1 + \sum_{i = 1}^{N} v_{i} x_{i} \leq s^{τ}$ , both Lagrangian multipliers corresponding to the optimal solution $x^{*}$ . Then $η_{γ, j} = \partial_{γ_{j}} Ψ (γ, s) = λ_{j}^{*} (1 + \sum_{i} v_{i} x_{i}) \geq 0$ and $η_{s} = \partial_{s} Ψ (γ, s) = λ_{s}^{*} \geq 0$ . Furthermore, Lemma 10 in the appendix shows that $Ψ$ is twice differentiable with bounded Hessian $\partial^{2} Ψ$ on ${(γ, s) : ‖ γ - γ_{0} ‖_{\infty} \leq ρ_{0} \land | s - s^{τ_{0}} | \leq ρ_{0}}$ . Let $η_{h} := max_{γ, s} ‖ \partial^{2} Ψ (γ, s) ‖_{op} \leq \frac{8 M^{2} K N B_{0}^{3}}{χ_{0}^{2}} < + \infty$ where $γ, s$ are in the closed neighborhood of ${(γ, s) : ‖ γ - γ_{0} ‖_{\infty} \leq ρ_{0} \land | s - s^{τ_{0}} | \leq ρ_{0}}$ . Subsequently, using Taylor expansion we have that $| Ψ ({\tilde{γ}}^{τ}, {\tilde{s}}^{τ}) - (Ψ (γ_{0}, s^{τ_{0}}) + ⟨ η_{γ}, {\tilde{γ}}^{τ} - γ_{0} ⟩ + η_{s} ({\tilde{s}}^{τ} - s^{τ_{0}})) | \leq η_{h} [‖ {\tilde{γ}}^{τ} - γ_{0} ‖_{2}^{2} + ({\tilde{s}}^{τ} - s^{τ_{0}})^{2}] .$ Plugging in the definitions of ${\tilde{γ}}^{τ}$ and ${\tilde{s}}^{τ}$ we complete the proof of Lemma 7.

4.4. Completing the Proof

Recall the definition that $β^{τ} = \sum_{i = 1}^{N} r_{i} n^{τ} (i)$ is the total revenue collected during the epoch $τ$ . The expected total revenue of the proposed policy can be lower bounded as $E [\sum_{t = 1}^{T} r_{i_{t}}] \geq E [\sum_{τ = τ^{♯}}^{τ_{0}} β^{τ}]$ . Therefore, it suffices to lower bound $E [\sum_{τ = τ^{♯}}^{τ_{0}} β^{τ}]$ . Next, fix an arbitrary epoch $τ \geq τ^{♯}$ . We have that

\begin{aligned} E [β^{τ} | γ^{τ}, s^{τ}] & = \sum_{i = 1}^{N} r_{i} E [n^{τ} (i) | γ^{τ}, s^{τ}] \\ = \sum_{i = 1}^{N} r_{i} v_{i} E [x_{i}^{τ} | γ^{τ}, s^{τ}] = Ψ (γ^{τ}, s^{τ}) . \end{aligned}

(20)

Invoke Lemma 7 and note that

E [ε^{\to τ}] = 0

E [Δ^{\to τ}] = 0

. We have that

E [Ψ (γ^{τ}, s^{τ})] \geq Ψ (γ_{0}, s^{τ_{0}}) - η_{h} E [‖ ε^{\to τ} ‖_{2}^{2} + | Δ^{\to τ} |^{2}] .

(21)

By equations (14,16) in the proof of Lemma 6, we have for every

τ

and

j \in [M]

that

E [| ε^{\to τ} (j) |^{2}] \leq \frac{2700 A_{0}^{2} B_{0}^{4} K^{4}}{τ - 2}, E [| Δ^{\to τ} |^{2}] \leq \frac{12 K^{2} B_{0}^{2}}{τ - 2} .

(22)

Combining equations (19,20), we obtain

E [Ψ (γ^{τ}, s^{τ})] \geq Ψ (γ_{0}, s^{τ_{0}}) - const . \times η_{h} A_{0}^{2} B_{0}^{4} K^{4} / (τ - 2)

. Additionally, because

s^{τ_{0}} = 1 + \sum_{i} v_{i} x_{i}^{F}

, by Lemma 2 we have that

Ψ (γ_{0}, s^{τ_{0}}) = s^{τ_{0}} Φ (γ_{0})

. Incorporating the bounds on

E [Ψ (γ^{τ}, s^{τ})]

s^{τ_{0}}

into equations (18,19) and using the law of total expectation, we obtain

E [β^{τ}] \geq s^{τ_{0}} Φ (γ_{0}) - const . \times η_{h} A_{0}^{2} B_{0}^{4} K^{4} / (τ - 2) .

(23)

Because $τ^{♯}$ is a stopping time, the Doob’s optional stopping theorem implies that

\begin{aligned} E [\sum_{τ = τ^{♯}}^{τ_{0}} β_{τ}] & \geq s^{τ_{0}} Φ (γ_{0}) \times (τ_{0} - E [τ^{♯}]) - const . \\ \times \sum_{τ = 1}^{T} \frac{η_{h} A_{0}^{2} B_{0}^{4} K^{4}}{τ} \\ \geq T Φ (γ_{0}) - s^{τ_{0}} Φ (γ_{0}) \times const . \times A_{0}^{4} B_{0}^{8} K^{8} M \ln T / ρ_{0}^{4} \\ - const . \times \sum_{τ = 1}^{T} \frac{η_{h} A_{0}^{2} B_{0}^{4} K^{4}}{τ} \end{aligned}

(24)

\begin{aligned} \geq T Φ (γ_{0}) - s^{τ_{0}} Φ (γ_{0}) \times const . \times A_{0}^{4} B_{0}^{8} K^{8} M \ln T / ρ_{0}^{4} \\ - const . \times η_{h} A_{0}^{2} B_{0}^{4} K^{4} \ln T . \end{aligned}

(25)

where equation (22) holds by invoking Lemma 6 and noting that

s^{τ_{0}} τ_{0} = T

by definition; equation (23) holds because

\sum_{τ = 1}^{T} τ^{- 1} = O (\ln T)

thanks to the Harmonic series. The regret of the proposed re-solving policy is then at most

const . \times s^{τ_{0}} Φ (γ_{0}) \times A_{0}^{2} B_{0}^{4} K^{4} M \ln T / ρ_{0}^{2} + const . \times η_{h} A_{0}^{2} B_{0}^{4} K^{4} \ln T \leq const . \times A_{0}^{2} B_{0}^{4} K^{4} M \ln T / ρ_{0}^{2} + const . \times \frac{8 M^{2} K N B_{0}^{3}}{χ_{0}^{2}} \times A_{0}^{2} B_{0}^{4} K^{4} \ln T

, which proves Theorem 1.

5. Numerical Results

We verify the effectiveness of the proposed resolving heuristics using numerical experiments. We compare the proposed Algorithm 3 (denoted as Resolving throughout this section) with the fluid approximation upper bound $Φ (γ)$ , as well as two other obvious baseline methods: Sampling-per-period and Sampling-per-epoch, which involve solving the fluid problem only once and then sampling from it in an independent manner. Details of these two baseline methods are given in Appendix 6. Details of experimental settings we implemented are also placed in Appendix 6.

In Figure 1 we report the average revenue and regret performances of our proposed algorithm and the two mentioned baseline methods. Each method is run for 500 independent trials and the mean revenue/regret is reported. As we can see from Figure 1, the Sampling-per-period method has an inferior performance because of the non-linearity of the $x \mapsto v^{⊤} x / (1 + v^{⊤} x)$ function. In fact, the average revenue of the Sampling-per-period method does not converge to the fluid approximation benchmark even when the time horizon $T$ is very large, indicating that it has linear regret. On the other hand, the average revenue of both Sampling-per-epoch and Resolving converges to the fluid benchmark as $T$ increases, indicating that both methods have sub-linear regret. Furthermore, Resolving clearly outperforms Sampling-per-epoch to various degrees under virtually all different settings, demonstrating the practical effectiveness of re-solving fluid optimization problems in the process of dynamic assortment optimization.

Figure 1.

Average revenue (top panel) and regret (bottom) performances for $N = 10$ products and $K = 3$ capacity constraint, with the number of resources $M$ ranging from 5 to 15 and the number of time periods $T$ ranging from $2^{5} = 32$ to $2^{15} = 32, 768$ .

In Figure 2 we further report the average revenue and regret of the algorithms on slightly larger problem instances with $N = 20$ products and the number of resources $M$ ranging from 10 to 30. We have also increased the cardinality constraint $K$ from 3 to 5. The results are similar to those reported in Figure 1, with even larger performance gaps between Sampling-per-epoch and Resolving on these larger problem instances.

Figure 2.

Average revenue (top panel) and regret (bottom) performances for $N = 20$ products and $K = 5$ capacity constraint, with the number of resources $M$ ranging from 10 to 30 and the number of time periods $T$ ranging from $2^{5} = 32$ to $2^{15} = 32, 768$ .

Finally, we remark that both Figures 1 and 2 show that our proposed method has superior performance compared with baseline methods even for shorter time horizons where $T$ is small. This empirical observation complements our theoretical findings in Theorem 1 which is focused primarily for longer time horizons. We also remark that both benchmarks are computationally cheaper than the resolving policy because they only need to compute the optimal solution to the fluid approximation once; nevertheless, both benchmarks still require obtaining fresh samples of assortments every time period or epoch, invoking Algorithm 2 many times.

6. Conclusions and Future Directions

In this article, we propose a new epoch-based re-solving technique for dynamic assortment optimization under knapsack inventory constraints. The proposed re-solving technique addresses several technical challenges arising from the non-linear objective due to the MNL choice model. There are a few important future directions. For example, it would be interesting to extend the current problem into a learning problem where the choice model is unknown. The learning problem is closely related to multi-armed bandit (MAB) with knapsack constraints (Badanidiyuru et al., 2018). On the other hand, the special structure of MNL could make this problem much more complicated than the standard (MAB). In addition, it would be interesting to consider more complicated choice models beyond the standard MNL model, such as nested logit model (McFadden, 1980; Williams, 1977) or other choice models (see, e.g., Désir et al., 2020; Farias et al., 2013 and references therein).

Appendix A. Proof of Lemma 1

We first define some notations. Let $S := {S \subseteq [N] : | S | \leq K}$ denote the set of all possible assortments of size at most $K$ . Let $Δ^{S} := {q \in [0, 1]^{| S |} : \sum_{S \in S} q_{S} = 1}$ denote the set of all probability distributions over $S$ . For any $S \in S$ , define

R (S) := \frac{\sum_{i \in S} r_{i} v_{i}}{1 + \sum_{i \in S} v_{i}}, ν_{i} (S) = \frac{1 {i \in S} v_{i}}{1 + \sum_{j \in S} v_{j}}

as the expected revenue and the probability of choosing item

i

when assortment

S

is produced. Let also

ν (S) = (ν_{1} (S), \dots, ν_{N} (S)) \in R^{N}

be the concatenated expected purchase probability vector.

An alternative fluid approximation

We present the following optimization problem, serving as an alternative fluid approximation:

O P T_{1} := max_{q \in Δ^{S}} \sum_{S \in S} q_{S} R (S) s . t . \sum_{S \in S} q_{S} A^{⊤} ν (S) \leq γ_{0} .

(24)

Note that equation (24) is an LP having

| S |

variables and

N

constraints. Because it has an enormously large number of variables, it is not suitable for practical optimization but the formulation serves as an important tool for mathematical analysis of other optimization problems. An important result below shows that

O P T_{1}

upper bounds the (normalized) expected revenue of any admissible policy.

Lemma 8

For any admissible policy $π$ over $T$ periods, it holds that $E^{π} [\sum_{t = 1}^{T} R (S_{t})] \leq T \times O P T_{1}$ .

Proof. Proof of Lemma 8.

Let $S_{1}, \dots, S_{T}$ be the assortments offered by policy $π$ over $T$ periods, which are correlated random variables forming a Markov chain. For any $S \in S$ , define ${\hat{q}}_{S} := \frac{1}{T} \sum_{t = 1}^{T} E^{π} [1 {S_{t} = S}]$ . Clearly ${\hat{q}}_{S} \geq 0$ and $\sum_{S \in S} {\hat{q}}_{S} = 1$ by definition. Because $π$ is an admissible policy, $\sum_{t = 1}^{T} A^{⊤} ν (S_{t}) \leq γ_{0} T$ almost surely and therefore $\sum_{t = 1}^{T} A^{⊤} E^{π} [ν (S_{t})] \leq γ_{0} T$ , implying that $\hat{q} = ({\hat{q}}_{S})_{S \in S}$ is feasible to equation (24) because

\begin{aligned} \sum_{S \in S} {\hat{q}}_{S} A^{⊤} ν (S) & = \sum_{S \in S} \frac{1}{T} \sum_{t = 1}^{T} E^{π} [1 {S_{t} = S}] A^{⊤} ν (S) \\ = \frac{1}{T} \sum_{t = 1}^{T} A^{⊤} E^{π} [ν (S_{t})] \leq γ_{0} . \end{aligned}

Subsequently,

E^{π} [\sum_{t = 1}^{T} R (S_{t})] = T \times \sum_{S \in S} {\hat{q}}_{S} R (S) \leq T \times O P T_{1}

, which is to be proved.

Remark 4
Equation (24) is a general formulation for fluid approximation in sequential decision making with aggregated inventory constraints and unchanged action spaces, and Lemma 8 is somewhat folklore which can be found, perhaps in different forms, in many existing literature (e.g., Miao et al., 2025). On the other hand, the fact (which we are going to rigorously establish in the remainder of this section) that equation (24) has the same optimal objective as equation (4) is highly non-trivial and is a consequence of strong duality of both formulations sharing the same dual function in this particular application of assortment optimization.

It is also helpful to derive the Lagrangian dual function of equation (24). Let $λ_{j} \geq 0$ be a Lagrangian multiplier associated with the constraint involving $γ_{0 j}$ on the right-hand side of the constraints. Let also $λ = (λ_{1}, \dots, λ_{M}) \in R_{+}^{M}$ be the concatenated Lagrangian multiplier vector. The dual function of equation (24) is then derived as
$\begin{aligned} g_{1} (λ) & := max_{q \in Δ^{S}} \sum_{S \in S} R (S) q_{S} - λ^{⊤} (\sum_{S \in S} q_{S} A^{⊤} ν (S) - γ_{0}) \\ = max_{S \in S} R (S) - λ^{⊤} A^{⊤} ν (S) + λ^{⊤} γ_{0} \end{aligned}$
(25)

$\begin{aligned} = max_{S \in S} \frac{\sum_{i \in S} (r_{i} - φ_{i}) v_{i}}{1 + \sum_{i \in S} v_{i}} + λ^{⊤} γ_{0}, \end{aligned}$
(26)
where $φ := λ^{⊤} A^{⊤} \in R^{N}$ , and the second inequality in equation (25) holds because we are optimizing a linear function over a probability simplex.

Dual function of fluid approximation in Definition 1

Define $β = (β_{1}, \dots, β_{N}) \in R^{N}$ where $β_{i} = r_{i} v_{i}$ , and $v = (v_{1}, \dots, v_{N}) \in R^{N}$ . Define also $B \in R^{N \times M}$ as $B_{i j} = A_{i j} v_{i}$ . Let $X := {x \in [0, 1]^{N} : 1^{⊤} x \leq K}$ . The fluid approximation problem in Definition 1 can then be written as
$O P T_{2} := max_{x \in X} \frac{β^{⊤} x}{1 + v^{⊤} x} s . t . \frac{B^{⊤} x}{1 + v^{⊤} x} \leq γ_{0} .$
(27)

We next derive the dual problem to equation (27). Let $λ \in R_{+}^{M}$ be the Lagrangian vector. Then the dual function can be derived as
$\begin{aligned} g_{2} (λ) & = max_{x \in X} \frac{β^{⊤} x}{1 + v^{⊤} x} - λ^{⊤} (\frac{B^{⊤} x}{1 + v^{⊤} x} - γ_{0}) \\ = max_{x \in X} \frac{(β - B λ)^{⊤} x}{1 + v^{⊤} x} + λ^{⊤} γ_{0} . \end{aligned}$
(28)

Fluid approximation via Charnes–Cooper transform

Note that Equation (27) can be re-formulated as a linear fractional programming as
$O P T_{2} = max_{x \in X} \frac{β^{⊤} x}{1 + v^{⊤} x} s . t . (B^{⊤} - γ_{0} v^{⊤}) x \leq γ_{0},$
(29)
because $1 + v^{⊤} x \geq 1$ for all $x \in X$ and therefore an ( $1 + v^{⊤} x$ ) term can be multiplied on both sides of inequality constraints in equation (27). Using the celebrated Charnes–Cooper transform of linear fractional programming (see, e.g., (Charnes and Cooper, 1962), and also Appendix 6 this article for a brief summary) $z = x / (1 + v^{⊤} x)$ and $t = 1 / (1 + v^{⊤} x)$ , equation (29) is equivalent to
$\begin{aligned} O P T_{2} & = max_{z, t} β^{⊤} z s . t . (B^{⊤} - γ_{0} v^{⊤}) z \leq γ_{0} t, \\ v^{⊤} z + t & = 1, t \geq 0, z / t \in X, \end{aligned}$
which is further equivalent to
$O P T_{2} = max_{z, t \in Z} β^{⊤} z s . t . (B^{⊤} - γ_{0} v^{⊤}) z \leq γ_{0} t,$
(30)
where $Z = {(z, t) : v^{⊤} z + t = 1, z \geq 0, t \geq 0, z \leq t, 1^{⊤} z \leq K t}$ . Note that equation (30) is an LP over $z, t$ , and the domain $Z$ is a polytope in $R^{N + 1}$ .

It is also instructive to derive the Lagrangian dual function of equation (30). For any Lagrangian multiplier vector $λ \in R_{+}^{M}$ , the dual function is derived as
$\begin{aligned} g_{3} (λ) & := max_{z, t \in Z} β^{⊤} z - λ^{⊤} ((B^{⊤} - γ_{0} v^{⊤}) z - γ_{0} t) \\ = max_{z, t \in Z} (β - B λ)^{⊤} z + λ^{⊤} γ_{0}, \end{aligned}$
(31)
where the second equality holds because $t = 1 - v^{⊤} z$ for any $(z, t) \in Z$ .

We next present the central lemma to our proof, showing that the three dual functions $g_{1} (\cdot), g_{2} (\cdot), g_{3} (\cdot)$ are equivalent.
Lemma 9
For any $λ \in R_{+}^{M}$ , $g_{1} (λ) = g_{2} (λ) = g_{3} (λ)$ .
Proof. Proof of Lemma 9.

Fix arbitrary $λ \in R_{+}^{M}$ . We first focus on dual functions $g_{1}$ and $g_{2}$ . Consider arbitrary $S^{*} \in \arg max_{| S | \leq K} \frac{\sum_{i \in S} (r_{i} - φ_{i}) v_{i}}{1 + \sum_{i \in S} v_{i}}$ . Define $x_{i} := 1 {i \in S^{*}}$ . It is easy to verify that $x \in X$ . Furthermore, $\frac{\sum_{i \in S} (r_{i} - φ_{i}) v_{i}}{1 + \sum_{i \in S} v_{i}} = \frac{(β - B λ)^{⊤} x}{1 + v^{⊤} x}$ . This shows that $g_{1} (λ) \leq g_{2} (λ)$ .

To show the other direction, note that there exists $x^{*} \in {0, 1}^{N} \cap X$ such that $\frac{(β - B λ)^{⊤} x^{*}}{1 + v^{⊤} x^{*}} = g (λ) - γ_{0}^{⊤} λ$ . To see the existence of such $x^{*}$ , consider arbitrary $x^{♯} \in \arg max_{x \in X} \frac{(β - B λ)^{⊤} x}{1 + v^{⊤} x}$ . By definition, $((β - B λ)^{⊤} x^{♯}) / (1 + v^{⊤} x^{♯}) = g^{*} =: g (λ) - γ_{0}^{⊤} λ$ , which implies

(β - B λ - g^{*} v)^{⊤} x^{♯} \geq g^{*} .

(32)

For every

i \in [N]

let

ς_{i} := (β - B λ - g^{*} v)_{i}

. Now define

x_{i}^{*} = 1

ς_{i} \geq 0

and

ς_{i}

is within the top-

K

{ς_{i}}_{i = 1}^{N}

(ties broken arbitrarily), and

x_{i}^{*} = 0

otherwise. It is easy to see that such defined

x^{*} \in X

achieves the maximum possible value on the left-hand side of equation (32). Therefore,

(β - B λ - g^{*} v)^{⊤} x^{*} \geq g^{*}

, which implies

\frac{(β - B λ)^{⊤} x^{*}}{1 + v^{⊤} x^{*}} \geq g^{*}

. Because

g (λ)

maximizes over all

x \in X

, this actually means

\frac{(β - B λ)^{⊤} x^{*}}{1 + v^{⊤} x^{*}} = g^{*}

With such an $x^{*} \in {0, 1}^{N} \cap X$ that $\frac{(β - B λ)^{⊤} x^{*}}{1 + v^{⊤} x^{*}} = g (λ) - γ_{0}^{⊤} λ$ , define $S := {i \in [N] : x_{i}^{*} = 1}$ . Clearly $S \in S$ and $\frac{\sum_{i \in S} (r_{i} - φ_{i}) v_{i}}{1 + \sum_{i \in v_{i}}} = \frac{(β - B λ)^{⊤} x^{*}}{1 + v^{⊤} x^{*}}$ . This shows that $g_{2} (λ) \leq g_{1} (λ)$ . Combined with the argument in the previous paragraph we proved $g_{1} (λ) = g_{2} (λ)$ .

We next focus on the dual functions $g_{2}$ and $g_{3}$ . For any $x^{*} \in \arg max_{x \in X} \frac{(β - B λ)^{⊤} x}{1 + v^{⊤} x}$ , define $z := x^{*} / (1 + v^{⊤} x^{*})$ and $t := 1 / (1 + v^{⊤} x^{*})$ . It is easy to see that $z, t \in Z$ and furthermore $\frac{(β - B λ)^{⊤} x^{*}}{1 + v^{⊤} x^{*}} = (β - B λ)^{⊤} z$ . This proves $g_{2} (λ) \leq g_{3} (λ)$ . For the other direction, consider arbitrary $z^{*}, t^{*} \in \arg max_{(z, t) \in Z} (β - B λ)^{⊤} z$ . Define $x := z^{*} / t^{*}$ . It is easy to verify that $x \in X$ and furthermore $(β - B λ)^{⊤} z^{*} = \frac{(β - B λ)^{⊤} (z^{*} / t^{*})}{1 / t^{*}} = \frac{(β - B λ)^{⊤} (z^{*} / t^{*})}{(v^{⊤} z^{*} + t^{*}) / t^{*}} = \frac{(β - B λ)^{⊤} (z^{*} / t^{*})}{1 + v^{⊤} z^{*} / t^{*}} = \frac{(β - B λ)^{⊤} x^{*}}{1 + v^{⊤} x^{*}}$ . This proves that $g_{3} (λ) \leq g_{2} (λ)$ . Combining both directions we proved that $g_{2} (λ) = g_{3} (λ)$ .

With Lemma 9, we know that all three dual problems have the same optimal value $G^{*} := max_{λ \geq 0} g_{1} (λ) = max_{λ \geq 0} g_{2} (λ) = max_{λ \geq 0} g_{3} (λ)$ . Because $g_{1}$ and $g_{3}$ are dual functions of LPs, strong duality holds and therefore $O P T_{1} = G^{*} = O P T_{2}$ . Combining this with Lemma 8 we complete the proof of Lemma 1.

Appendix B. Proofs of Some Technical Lemmas

Proof. Proof of Lemma 2.

Because $x^{F}$ is feasible and optimal to $Φ (γ)$ , it holds that $‖ x^{F} ‖_{1} \leq K$ and $A^{⊤} ν (x^{F}) \leq γ$ . Because $s$ is defined as $s = 1 + \sum_{i = 1}^{N} v_{i} x_{i}^{F}$ , we know that $x^{F}$ is feasible to $Ψ (γ, s)$ too. Furthermore, $\sum_{i = 1}^{N} r_{i} v_{i} x_{i}^{F} = R (x^{F}) \times (1 + \sum_{i = 1}^{N} v_{i} x_{i}^{F}) = R (x^{F}) s$ . Therefore, $Ψ (γ, s) \geq \sum_{i = 1}^{N} r_{i} v_{i} x_{i}^{F} = R (x^{F}) s = Φ (γ) s$ .

Next, let $z^{F}$ the optimal solution to $Ψ (γ, s)$ , where $s = 1 + \sum_{i = 1}^{N} v_{i} x_{i}^{F}$ . We then have $Ψ (γ, s) = \sum_{i = 1}^{N} r_{i} v_{i} z_{i}^{F} = R (z^{F}) \times [1 + \sum_{i = 1}^{N} v_{i} z_{i}^{F}] \leq R (z^{F}) s$ , where the last inequality holds because $1 + \sum_{i = 1}^{N} v_{i} z_{i}^{F} \leq s$ since $z^{F}$ is feasible to $Ψ (γ, s)$ . On the other hand, because $z^{F}$ is feasible to $Φ (γ)$ , from optimality we have that $R (z^{F}) \leq Φ (γ) = R (x^{F})$ . Subsequently, $Ψ (γ, s) \leq R (z^{F}) s \leq Φ (γ) s$ .

Combining both cases, we conclude that $Ψ (γ, s) = Φ (γ) s$ .

Proof. Proof of Lemma 3.

It is clear that ${\hat{x}}^{F}$ constructed in Algorithm 1 is also feasible because of the constraints in equation (7). In addition, it is easy to verify that if $(1 - λ) {[\sum_{i} {\hat{x}}_{λ}^{F}]}_{i} \geq λ$ then $Φ (γ) \geq λ$ , and vice versa. Hence, the bisection search procedure in Algorithm 1 will never exclude the optimal $R (γ)$ from $[λ_{L}, λ_{U}]$ , and furthermore at the end of the algorithm, $(1 - λ_{L}) [\sum_{i} v_{i} {\hat{x}}_{i}^{F}] \geq λ_{L}$ , which implies $R ({\hat{x}}^{F}) \geq λ_{L} = λ_{U} - ϵ \geq R (γ) - ϵ$ . Finally, Algorithm 1 solves $O (\log (1 / ϵ))$ LPs because this is the total number of iterations until $λ_{U} - λ_{L} \leq ϵ$ .

Proof. Proof of Proposition 1.

The fact that $‖ z ‖_{1} \leq K$ almost surely is obvious from the observation that $P_{u}$ is a permutation matrix, and hence the first $K$ rows of $P_{u}$ consists of exactly $K$ ones. To prove $E [z_{i}] = x_{i}$ , note that $z_{i} \in {0, 1}$ and $Pr [z_{i} = 1] = \sum_{ℓ = 1}^{L} \sum_{k = 1}^{K} Pr [u = ℓ] P_{ℓ, k i} = \sum_{ℓ = 1}^{L} \sum_{k = 1}^{K} α_{ℓ} P_{ℓ, k i} = \sum_{k = 1}^{K} M_{k i} = x_{i}$ . This completes the proof.

Appendix C. Second-Order Stability of Linear Programming

Lemma 10

Under Assumptions (A1) to (A3), for any $γ, s$ satisfying $‖ γ - γ_{0} ‖_{\infty} \leq ρ_{0}$ and $| s - s^{τ_{0}} | \leq ρ_{0}$ , $Ψ$ is differentiable in $(γ, s)$ and furthermore $‖ \partial^{2} Ψ (γ, s) ‖_{op} \leq \frac{8 M^{2} K N B_{0}^{3}}{χ_{0}^{2}} .$

Proof.

Recall that $Ψ$ can be written as the following LP problem:

\begin{aligned} Ψ (γ, s) & = max_{x \in [0, 1]^{N}} \sum_{i = 1}^{N} r_{i} v_{i} x_{i}, s . t . \sum_{i = 1}^{N} x_{i} \leq K, 1 + \sum_{i = 1}^{N} v_{i} x_{i} \leq s, \\ \sum_{i = 1}^{N} A_{j i} v_{i} x_{i} & \leq γ_{j} [1 + \sum_{k = 1}^{N} v_{k} x_{k}], \forall j \in [M] . \end{aligned}

We convert the constraints of

Ψ

into the standard form

\tilde{A} x \leq \tilde{b}

, where

\tilde{A} \in R^{(M + 2 + 2 N) \times N}

denotes the coefficient matrix in the left hand side of constraints, and

\tilde{b} \in R^{M + 2 + 2 N}

denotes the vector in the right hand side of constraints. The first row of matrix

\tilde{A}

is an all-one vector. For row index

i

from 2 to

M + 1

, each entry in

\tilde{A}

(A_{(i - 1), j} - γ_{i - 1}) v_{j}

, for column index

j = 1, \dots, N

. The

(M + 2)

-th row of

\tilde{A}

is the same as

v

. The last

2 N \times N

submatrix of

\tilde{A}

[I_{N}, - I_{N}]^{⊤}

. The vector

\tilde{b}

[K, γ, s - 1, [1, \dots, 1]_{N}, [0, \dots, 0]_{N}]^{⊤}

. We use

{\tilde{λ}}^{*} \in R^{M + 2 + 2 N}

to denote the optimal dual variables of constraints

\tilde{A} x \leq \tilde{b}

for

Ψ

. Notice that both

{\tilde{λ}}^{*}

and

x^{*}

depend on

γ

and

s

We first consider the first order derivative of $Ψ (γ, s)$ using the envelope theorem. We notice that $γ_{j}$ only appears in the $(j + 1)$ -th row in constraints, and $s$ only appears in the last row of constraints. Thus, according to the envelope theorem, the partial derivatives of $Ψ$ with respect to the parameters $γ$ and $s$ are given by: $\frac{\partial Ψ}{\partial γ_{j}} = {\tilde{λ}}_{j + 1}^{*} {(\frac{\partial \tilde{b}}{\partial γ_{j}} - \frac{\partial \tilde{A}}{\partial γ_{j}} x^{*})}_{(j + 1)},$ and $\frac{\partial Ψ}{\partial s} = {\tilde{λ}}_{M + 2}^{*} {(\frac{\partial \tilde{b}}{\partial s} - \frac{\partial \tilde{A}}{\partial s} x^{*})}_{(M + 2)} .$

By the value of $\tilde{A}$ and $\tilde{b}$ , we have that ${(\frac{\partial \tilde{b}}{\partial γ_{j}} - \frac{\partial \tilde{A}}{\partial γ_{j}} x^{*})}_{(j + 1)} = 1 + \sum_{i} r_{i} v_{i} x_{i}$ , and ${(\frac{\partial \tilde{b}}{\partial s} - \frac{\partial \tilde{A}}{\partial s} x^{*})}_{(M + 2)} = 1$ . Thus, we obtain that $\frac{\partial Ψ}{\partial γ_{j}} = {\tilde{λ}}_{j + 1}^{*} (1 + \sum_{i} r_{i} v_{i} x_{i}), for j \in [1, \dots ., M], and \frac{\partial Ψ}{\partial s} = {\tilde{λ}}_{M + 2}^{*}$ .

Next, we consider the second derivative of $Ψ (γ, s)$ . We denote the basis of the binding constraints at $x^{*}$ by ${\tilde{B}}^{*} (γ, s) \in R^{N \times N}$ and denote its corresponding right hand side by ${\tilde{b}}_{B} \in R^{N}$ . Thus, we have that ${\tilde{B}}^{*} (γ, s) x^{*} = {\tilde{b}}_{B}$ . We further denote the optimal dual variables for the binding constraints by ${\tilde{λ}}_{B} \in R^{N}$ . By the complementary slackness, the optimal dual variables for nonbinding constraints are zero, so we have that ${\tilde{B}}^{*} (γ, s)^{⊤} {\tilde{λ}}_{B} = v ⊙ r$ , where $⊙$ represents the entrywise product of two vectors.

The major part of analyzing the Hessian matrix $\partial^{2} Ψ (γ, s)$ is to examine how ${\tilde{λ}}^{*}$ and $x^{*}$ depend on $(γ, s)$ . By Assumption (A3), for any $(γ, s) \in {(γ, s) : ‖ γ - γ_{0} ‖ \leq ρ_{0} \land | s - s^{τ_{0}} | \leq ρ_{0}}$ , the minimum singular value of ${\tilde{B}}^{*}$ is greater than or equal to $χ_{0} > 0$ . It implies that there exisits a unique solution $x^{*}$ for $Ψ (γ, s)$ , and that the basis ${\tilde{B}}^{*}$ remains unchanged when $(γ, s)$ is within the set of ${(γ, s) : ‖ γ - γ_{0} ‖ \leq ρ_{0} \land | s - s^{τ_{0}} | \leq ρ_{0}}$ . Thus, for the non-binding constraints regarding to resource $j$ , for any $k = 1, \dots, M$ , we have that $\frac{\partial {\tilde{λ}}_{j + 1}^{*}}{\partial γ_{k}} = 0, \frac{\partial {\tilde{λ}}_{j + 1}^{*}}{\partial s} = 0.$ Similarly, for the non-binding constraints regarding to resource $j$ , we have that $\frac{\partial x^{*}}{\partial γ_{j}} = 0.$

Thus, when analyzing the upper bound for the operator norm of the hessian matrix, $‖ \partial^{2} Ψ (γ, s) ‖_{op}$ , it suffices to consider the binding constraints. Since ${\tilde{B}}^{*} (γ, s)^{⊤} {\tilde{λ}}_{B} = v$ and the minimum singular value of ${\tilde{B}}^{*}$ is no smaller than $χ_{0}$ , we have that $‖ v ‖ = ‖ {\tilde{B}}^{*} {\tilde{λ}}_{B} ‖ \geq χ_{0} ‖ {\tilde{λ}}_{B} ‖$ . Since $‖ v ‖ \leq \sqrt{N} B_{0}$ , we have that $‖ {\tilde{λ}}_{B} ‖ \leq \frac{\sqrt{N} B_{0}}{χ_{0}}$ . By taking the derivative of $(γ, s)$ on both sides of ${\tilde{B}}^{*} (γ, s)^{⊤} {\tilde{λ}}_{B} = v ⊙ r$ , we obtain that $\frac{\partial {\tilde{B}}^{*}}{\partial (γ, s)} {\tilde{λ}}_{B} + {\tilde{B}}^{*} \frac{\partial {\tilde{λ}}_{B}}{\partial (γ, s)} = 0.$ Therefore, we have that $‖ {\tilde{B}}^{*} \frac{\partial {\tilde{λ}}_{B}}{\partial (γ, s)} ‖ = ‖ \frac{\partial {\tilde{B}}^{*}}{\partial (γ, s)} {\tilde{λ}}_{B} ‖ .$

Since $\tilde{B}$ is a submatrix of $\tilde{A}$ , we have that each entry of $\frac{\partial {\tilde{B}}^{*}}{\partial (γ, s)}$ is smaller than or equal to $B_{0}$ . Thus, the right hand side $‖ \frac{\partial {\tilde{B}}^{*}}{\partial (γ, s)} {\tilde{λ}}_{B} ‖$ is smaller than or equal to $(M + 1) B_{0} \times \frac{\sqrt{N} B_{0}}{χ_{0}} = \frac{(M + 1) \sqrt{N} B_{0}^{2}}{χ_{0}}$ . Thus, we have that $‖ {\tilde{B}}^{*} \frac{\partial {\tilde{λ}}_{B}}{\partial (γ, s)} ‖ \leq \frac{(M + 1) \sqrt{N} B_{0}^{2}}{χ_{0}}$ . Again, by the minimum singular value of ${\tilde{B}}^{*}$ , we have that

‖ \frac{\partial {\tilde{λ}}_{B}}{\partial (γ, s)} ‖ \leq \frac{(M + 1) \sqrt{N} B_{0}^{2}}{χ_{0}^{2}} .

(33)

Next, we consider the upper bound for $‖ \frac{\partial x^{*}}{\partial (γ, s)} ‖$ . Since ${\tilde{B}}^{*} x^{*} = {\tilde{b}}_{B}$ , by taking the derivative on both sides, we have that $\frac{\partial {\tilde{B}}^{*}}{\partial (γ, s)} x^{*} + {\tilde{B}}^{*} \frac{\partial x^{*}}{\partial (γ, s)} = \frac{\partial {\tilde{b}}_{B}}{\partial (γ, s)} .$

Since ${\tilde{b}}_{B}$ is subvector of $\tilde{b}$ , we have that $‖ \frac{\partial {\tilde{b}}_{B}}{\partial (γ, s)} ‖ \leq \sqrt{N}$ . By $‖ x^{*} ‖_{2} \leq ‖ x^{*} ‖_{1} \leq K$ , we have that $‖ {\tilde{B}}^{*} \frac{\partial x^{*}}{\partial (γ, s)} ‖ \leq \sqrt{N} + (M + 1) B_{0} K$ . Again, by the minimum singular value of ${\tilde{B}}^{*}$ , we have that

‖ \frac{\partial x^{*}}{\partial (γ, s)} ‖ \leq \frac{\sqrt{N} + (M + 1) B_{0} K}{χ_{0}} .

(34)

By taking the derivatives of $\partial Ψ / \partial γ$ and $\partial Ψ / \partial s$ , we have that for the hessian matrix $\partial^{2} Ψ (γ, s)$ , each entry is no larger than $‖ \partial {\tilde{λ}}_{B} / \partial (γ, s) ‖ (1 + B_{0} K) + ‖ {\tilde{λ}}_{B} ‖ \cdot B_{0} \cdot ‖ \partial x^{*} / \partial (γ, s) ‖ .$ Combining the upper bounds in (33) and (34), we have that each entry in the hessian matrix is no larger than $((M + 1) \sqrt{N} B_{0}^{2} (1 + B_{0} K)) / χ_{0}^{2} + \sqrt{N} B_{0}^{2} / χ_{0} (\sqrt{N} + (M + 1) B_{0} K) / χ_{0},$ which is further no larger than $(4 M K N B_{0}^{3}) / (χ_{0}^{2})$ . Thus, the operator norm of the hessian matrix $\partial^{2} Ψ (γ, s)$ is no larger than $(8 M^{2} K N B_{0}^{3}) / χ_{0}^{2}$ .

Appendix D. The Charnes–Cooper Transformation

Given a linear fractional programming

max_{x} \frac{c^{⊤} x + α}{d^{⊤} x + β} s . t . A x \leq b

restricted to the domain

{x : d^{⊤} x + β > 0}

, the Charnes–Cooper transformation transforms it into an LP

max_{y, t} c^{⊤} y + α t s . t . A y \leq b t, d^{⊤} y + β t = 1, t \geq 0

where

y

is a vector of the same length as

x

, and

t

is a scalar. The transformed LP is equivalent to the original linear fractional programming, via the following equivalence:

y = \frac{1}{d^{⊤} x + β} x, t = \frac{1}{d^{⊤} x + β} and x = \frac{1}{t} y .

When the domain of

x

is further restricted beyond

d^{⊤} x + β > 0

, the domain of

(y, t)

is adjusted so that the above equivalence remains valid.

Appendix E. Implementation and Experimental Details

Methods we implemented in Section 5 are summarized as follows.

The first method, denoted as Sampling-per-period, obtains unbiased assortment samples $z_{1}, z_{2}, \dots$ from $x^{F}$ that solves the fluid approximation $Φ (γ)$ during every single time period. That is, the assortments offered to arriving customers are constantly changing from period to period;

The second method, denoted as Sampling-per-epoch, obtains unbiased assortment samples $z_{1}, z_{2}, \dots$ from $x^{F}$ that solves the fluid approximation $Φ (γ)$ whenever a no-purchase activity arises. That is, the algorithm offers the same assortment to arriving customers until the first customer purchased nothing, at which time the algorithm will obtain a fresh sample $z$ and updates its offered assortment for future customers.

Note that both the above-mentioned baseline methods solve the fluid approximation

Φ (γ)

only once at the beginning of the algorithms, and no re-solve or re-optimization is carried out during the assortment planning process.

We numerically synthesize problem instances with $N$ products, $M$ resources and capacity constraint $K$ as follows. The utility parameters ${v_{i}}_{i = 1}^{N}$ are uniformly distributed on $[0, 1]$ . The normalized initial inventory levels ${C_{0, j}}_{j = 1}^{M} / T$ are uniformly distributed on $[0, 0.1]$ . For the resource consumption matrix $A \in R^{N \times M}$ , each element of $A$ is uniformly distributed on $[0, 1 / K]$ . Such synthesized problem instances achieve quite good balance between capacity and resource inventory constraints.

We also implemented an efficient BwK decomposition algorithm in the numerical results section. For ease of presentation we assume that $x_{1} + \dots + x_{N} = K$ . The case of $x_{1} + \dots + x_{N} < K$ can be easily handled by adding $K$ extra “dummy” variables, as shown in Algorithm 2. Without loss of generality we assume also that each $x_{i}$ belong to $(0, 1)$ , as those $x_{i} = 1$ will always be selected and $x_{i} = 0$ always excluded in the sampled assortments. For a general $N \times N$ doubly stochastic matrix $M$ , the standard Birkhoff’s algorithm uses up to $L = O (N^{2})$ permutation matrices in its decomposition and it takes $O (N^{4})$ time to compute them. In this section we present a more efficient algorithm that decomposes $M$ into at most $O (N)$ permutation matrices, with the total time complexity reduced to $O (N^{2})$ . This algorithm is also what we implemented to conduct our numerical experiments in Section 5.

Algorithm 4 gives a pseudocode description of the improved algorithm. As we can see, each iteration of Algorithm 4 will reduce at least one $y_{i}$ or ${\bar{y}}_{i}$ to zero, meaning that the algorithm will terminate in at most $N$ iterations. Furthermore, the computational time for each iteration is linear in $N$ . Hence, the total time complexity of Algorithm 4 is $O (N^{2})$ .

Footnotes

Acknowledgments

The authors thank the department editor, the senior editor and two anonymous referees for their helpful suggestions that greatly improved this article. Yuan Zhou was supported by the National Natural Science Foundation of China Grant 52494974.

Declaration of Conflicting Interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The authors received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Yining Wang

Notes

How to cite this article

Chen X, Liu M, Wang Y and Zhou Y (2026) A Re-Solving Heuristic for Dynamic Assortment Optimization With Knapsack Constraints. Production and Operations Management 35(5): 2073–2091.

References

Agrawal

Avadhanula

Goyal

, et al. (2017) Thompson sampling for the MNL-bandit. In: Conference on Learning Theory, pp.76–78. PMLR.

Agrawal

Avadhanula

Goyal

, et al. (2019) MNL-bandit: A dynamic learning approach to assortment selection. Operations Research 67(5): 1453–1485.

Badanidiyuru

Kleinberg

Slivkins

(2018) Bandits with knapsacks. Journal of the ACM 65(3): 1–55.

Besbes

Zeevi

(2012) Blind network revenue management. Operations Research 60(6): 1537–1550.

Budish

Che

Kojima

, et al. (2013) Designing random allocation mechanisms: Theory and applications. American Economic Review 103(2): 585–623.

Bumpensanti

Wang

(2020) A re-solving heuristic with uniformly bounded loss for network revenue management. Management Science 66(7): 2993–3009.

Charnes

Cooper

(1962) Programming with linear fractional functionals. Naval Research Logistics Quarterly 9(3-4): 181–186.

Chen

Jasin

Duenyas

(2015) Real-time dynamic pricing with minimal and flexible price adjustment. Management Science 62(8): 2437–2455.

Chen

Jasin

Duenyas

(2019) Nonparametric self-adjusting control for joint learning and optimization of multiproduct pricing with finite resource capacity. Mathematics of Operations Research 44(2): 601–631.

10.

Chen

Simchi-Levi

, et al. (2023) Dynamic recommendation at checkout under inventory constraint. Mathematics of Operations Research 49(1): 297–325.

11.

Chen

Wang

(2018) A note on tight lower bound for MNL-bandit assortment selection models. Operations Research Letters 46(5): 534–537.

12.

Chen

Wang

Zhou

(2020) Dynamic assortment optimization with changing contextual information. Journal of Machine Learning Research 21(216): 1–44.

13.

Chen

Wang

Zhou

(2021a) Dynamic assortment selection under the nested logit models. Production and Operations Management 30(1): 85–102.

14.

Chen

Wang

Zhou

(2021b) Optimal policy for dynamic assortment planning under multinomial logit models. Mathematics of Operations Research 46(4): 1639–1657.

15.

Cooper

(2002) Asymptotic behavior of an allocation policy for revenue management. Operations Research 50(4): 720–727.

16.

Désir

Goyal

Segev

, et al. (2020) Capacity constrained assortment optimization under the Markov chain based choice model. Management Science 66(2): 698–721.

17.

Dufossé

Uçar

(2016) Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices. Linear Algebra and Its Applications 497: 108–115.

18.

Farias

Jagabathula

Shah

(2013) A nonparametric approach to modeling choice with limited data. Management Science 59(2): 305–322.

19.

Fata

Simchi-Levi

(2019) Multi-stage and multi-customer assortment optimization with inventory constraints. arXiv preprint arXiv:1908.09808.

20.

Feng

Niazadeh

Saberi

(2024) Technical note: Near-optimal Bayesian online assortment of reusable resources. Operations Research 72(5): 1861–1873.

21.

Ferreira

Simchi-Levi

Wang

(2018) Online network revenue management using Thompson sampling. Operations Research 66(6): 1586–1602.

22.

Gal

Greenberg

(2012) Advances in Sensitivity Analysis and Parametric Programming, Vol. 6. New York NY: Springer Science & Business Media.

23.

Gallego

Iyengar

Phillips

, et al. (2004) Managing flexible products on a network. Technical Report CORC TR-2004-01, Department of Industrial Engineering and Operations Research, Columbia University.

24.

Gallego

van Ryzin

(1997) A multiproduct dynamic pricing problem and its applications to network yield management. Operations Research 45(1): 24–41.

25.

Golrezaei

Nazerzadeh

Rusmevichientong

(2014) Real-time optimization of personalized assortments. Management Science 60(6): 1532–1551.

26.

Gong

Goyal

Iyengar

, et al. (2019) Online assortment optimization with reusable resources. Management Science 68(7): 4772–4785.

27.

Goyal

Iyengar

Udwani

(2025) Asymptotically optimal competitive ratio for online allocation of reusable resources. Operations Research 73(4): 1897–1915.

28.

Jasin

(2014) Reoptimization and self-adjusting price control for network revenue management. Operations Research 62(5): 1168–1178.

29.

Jasin

Kumar

(2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Mathematics of Operations Research 37(2): 313–345.

30.

Jiang

Zhang

(2025) Online stochastic optimization with Wasserstein based non-stationarity. Management Science 71(11): 9104–9122.

31.

Lei

Jasin

(2020) Real-time dynamic pricing for revenue management with reusable resources, advance reservation, and deterministic service time requirements. Operations Research 68(3): 676–685.

32.

Lei

Jasin

Uichanco

, et al. (2021) Joint product framing (display, ranking, pricing) and order fulfillment under the multinomial logit model for e-commerce retailers. Manufacturing & Service Operations Management 24(3): 1529–1546.

33.

Liu

van Ryzin

(2008) On the choice-based linear programming model for network revenue management. Manufacturing & Service Operations Management 10(2): 288–310.

34.

Maglaras

Meissner

(2006) Dynamic pricing strategies for multiproduct revenue management problems. Manufacturing & Service Operations Management 8(2): 136–148.

35.

Mahajan

van Ryzin

(2001) Stocking retail assortments under dynamic consumer substitution. Operations Research 49: 334–351.

36.

McFadden

(1972) Conditional logit analysis of qualitative choice behavior .

37.

McFadden

(1980) Econometric models for probabilistic choice among products. Journal of Business 53(3): 13–29.

38.

McFadden

Train

(2000) Mixed MNL models for discrete response. Journal of Applied Econometrics 15(5): 447–470.

39.

Megiddo

(1979) Combinatorial optimization with rational objective functions. Mathematics of Operations Research 4(4): 414–424.

40.

Miao

Wang

Zhang

(2025) A primal–dual framework for resource constrained revenue management with demand learning and large action space. Operations Research (accepted).

41.

Milgrom

Segal

(2002) Envelope theorems for arbitrary choice sets. Econometrica 70(2): 583–601.

42.

Reiman

Wang

(2008) An asymptotically optimal policy for a quantity-based network revenue management problem. Mathematics of Operations Research 33(2): 257–282.

43.

Rusmevichientong

Shen

ZJM

Shmoys

(2010) Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations Research 58(6): 1666–1680.

44.

Rusmevichientong

Sumida

Topaloglu

(2020) Dynamic assortment optimization for reusable products with random usage durations. Management Science 66(7): 2820–2844.

45.

Saure

Zeevi

(2013) Optimal dynamic assortment planning with demand learning. Manufacturing & Service Operations Management 15(3): 387–404.

46.

Secomandi

(2008) An analysis of the control-algorithm re-solving issue in inventory and revenue management. Manufacturing & Service Operations Management 10(3): 468–483.

47.

Takayama

(1985) Mathematical Economics. Cambridge University Press.

48.

Talluri

van Ryzin

(2004) Revenue management under a general discrete choice model of consumer behavior. Management Science 50(1): 15–33.

49.

Terça

Wozabal

(2021) Envelope theorems for multistage linear stochastic optimization. Operations Research 69(5): 1608–1629.

50.

van Ryzin

Mahajan

(1999) On the relationships between inventory costs and variety benefits in retail assortments. Management Science 45(11): 1496–1509.

51.

Vera

Banerjee

Gurvich

(2021) Online allocation and pricing: Constant regret via bellman inequalities. Operations Research 69(3): 821–840.

52.

Wang

(2022) Constant regret re-solving heuristics for price-based revenue management. Operations Research 70(6): 3538–3557.

53.

Wang

Deng

(2014) Close the gaps: A learning-while-doing algorithm for single-product revenue management problems. Operations Research 62(2): 318–331.

54.

Williams

HCWL

(1977) On the formation of travel demand models and economic evaluation measures of user benefit. Environment and Planning A: Economy and Space 9: 285–344.

55.

Srikant

Liu

, et al. (2015) Algorithms with logarithmic or sublinear regret for constrained contextual bandits. In: Advances in Neural Information Processing Systems, Vol. 28.

56.

anh Truong

(2021) Reoptimization algorithms for contextual bandits with knapsack constraints. Technical report, Columbia University.