容量分类优化：硬度和近似值-研究论文资源-CSDN文库

Optimization

需积分: 14 89 浏览量 2021-06-09 14:15:47 上传评论收藏 458KB PDF 举报

资源推荐

资源详情

资源评论

Capacitated Assortment Optimization: Hardness and

Approximation

Antoine D´esir

Technology and Operations Management, INSEAD antoine.desir@insead.edu

Vineet Goyal

Department of Industrial Engineering and Operations Research, Columbia University vgoyal@ieor.columbia.edu

Jiawei Zhang

Leonard N. Stern School of Business, New York University jzhang@stern.nyu.edu

Assortment optimization is an important problem that arises in many practical applications such as retailing

and online advertising. In this problem, the goal is to select a subset of items that maximizes the expected

revenue in the presence of (1) the substitution behavior of consumers speciﬁed by a choice model, and (2) a

potential capacity constraint bounding the total weight of items in the assortment. The latter is a natural

constraint arising in many applications. We begin by showing how challenging these two aspects are from an

optimization perspective. First, we show that adding a general capacity constraint makes the problem NP-

hard even for the simplest choice model, namely the multinomial logit model. Second, we show that even the

unconstrained assortment optimization for the mixture of multinomial logit model is hard to approximate

within any reasonable factor when the number of mixtures is not constant.

In view of these hardness results, we present near-optimal algorithms for the capacity constrained assort-

ment optimization problem under a large class of parametric choice models including the mixture of multino-

mial logit, Markov chain, nested logit and d-level nested logit choice models. In fact, we develop near-optimal

algorithms for a general class of capacity constrained optimization problems whose objective function depends

on a small number of linear functions. For the mixture of multinomial logit model (resp. Markov chain

model), the running time of our algorithm depends exponentially on the number of segments (resp. rank

of the transition matrix). Therefore, we get eﬃcient algorithms only for the case of constant number of

segments (resp. constant rank). However, in light of our hardness result, any near-optimal algorithm will

have a super polynomial dependence on the number of mixtures for the mixture of multinomial logit choice

model.

Key words : Assortment Optimization, FPTAS, choice models

1. Introduction

In many practical applications such as retailing or online advertising, the decision maker needs to

select a subset of items to oﬀer customers in order to maximize expected revenue. This problem

is known as the assortment optimization problem and has become a classical problem in revenue

Electronic copy available at: https://ssrn.com/abstract=2543309

D´esir, Goyal and Zhang: Capacitated Assortment Optimization: Hardness and Approximation

management (see Chapters 4 and 5 of Gallego and Topaloglu (2019) for a recent survey). Due

to the substitution behavior of consumers, the demand of any item depends on the set of oﬀered

items. For instance, a consumer might only buy a product X because his favorite product Y is not

oﬀered. Consequently, the retailer cannot make oﬀering decisions independently for each item and

must solve a combinatorial problem. Moreover, in practice, there is often a capacity constraint on

the oﬀer set, either coming from budget or capacity constraint.

More formally, consider a universe of n substitutable items where each item i ∈ [n] := {1, 2, · · · , n}

is associated with a positive revenue r

and a positive weight w

. The assortment optimization

problem can be formulated as the following mathematical program

max

S⊆[n]

(

i∈S

· π(i, S)



i∈S

≤ W

)

, (Cap-Assort)

where

• The decision variable S is the oﬀered assortment, which is a subset of [n] = {1,2, · · · , n}.

• The objective function the expected revenue for a given oﬀer set. For each item i ∈ [n], r

is its

associated revenue. In order to capture substitution behavior, the probability that a customer buys

item i is a function of the entire oﬀered assortment dictated by a customer choice model π(i, S)

for every S ⊆ [n] and i ∈ S.

• The constraint states that the total weight of the items selected in the oﬀer set should be no

more than a given capacity, denoted by W .

When all the weights are equal to one, the capacity constraint reduces to a cardinality constraint

which limits the number of items in the assortment. We refer to the cardinality constrained assort-

ment optimization problem as (Card-Assort) and to the unconstrained assortment optimization

problem as (Assort). More precisely,

max

S⊆[n]

i∈S

· π(i, S) (Assort)

and, max

S⊆[n]

(

i∈S

· π(i, S) | |S| ≤ W

)

. (Card-Assort)

In this paper, our goal is to design eﬃcient near-optimal algorithms for (Cap-Assort) under a

variety of customer choice models.

1.1. Related work

We brieﬂy introduce the diﬀerent choice models that we consider in this paper as well as existing

results on the assortment optimization problem under each of these.

Electronic copy available at: https://ssrn.com/abstract=2543309

D´esir, Goyal and Zhang: Capacitated Assortment Optimization: Hardness and Approximation

Multinomial logit model. The multinomial logit (MNL) model is by far the most popular model

in practice (Luce 1959, Plackett 1975, McFadden 1978). Under the MNL model, each item i ∈ [n]

has a preference weight u

∈ R

and there is an additional parameter u

∈ R

representing the

preference weight of the no-purchase or outside option. For any S ⊆ [n], the choice probability of

some item j ∈ S is given by

π(j, S) =

i∈S

. (1)

Under the MNL model, both (Assort) and (Card-Assort) are polynomially solvable (see Talluri and

Van Ryzin (2004) and Davis et al. (2013) respectively). However, some of the model justiﬁcations

such as the Independence of Irrelevant Alternatives (IIA) property which states that the odds of

choosing among two products are not aﬀected by the presence of a third product are not reasonable

for many applications (see Ben-Akiva and Lerman (1985)). To overcome these limitations and

capture richer substitution behavior, more complex choice models have been considered.

Mixture of MNL model. A mixture of MNL (MMNL) model is given by a distribution over K

diﬀerent MNL models and allows capturing customers’ heterogeneity. For all k ∈ [K] and j ∈ [n],

let u

j,k

∈ R

denote the MNL parameters for segment k and θ

denote the probability of segment

k. For any S ⊆ [n], the choice probability of item j ∈ S is given by

π(j, S) =

k=1

j,k

0,k

i∈S

i,k

. (2)

McFadden and Train (2000) show that any choice model arising from the random utility model

can be approximated as closely as required by a mixture of a ﬁnite (but unknown) number of MNL

models. However, Rusmevichientong et al. (2014) show that under the MMNL model, (Assort) is

NP-hard even when the number of mixture is two.

The next two choice models that we consider in this paper are the nested logit (NL) model

and the Markov chain model. Both also generalize the MNL model but are less general than the

mixture of MNL model. We give the exact choice model formulation under these models later in

the paper but give some informal deﬁnition and review some of the previous work next.

Nested logit model. In the nested logit (NL) model, also sometimes referred to as the 2-level

nested logit model, the items are clustered into diﬀerent nests. Customers ﬁrst choose a nest

and then pick among items in the chosen nest according to an MNL model. The NL model was

introduced by Williams (1977) and alleviates the IIA property by introducing correlation between

the utilities of items in the same nest. Davis et al. (2014) give a polynomial time algorithm for

(Assort) when the dissimilarity parameter for each nest is smaller than one and the utility of the

no purchase option is 0 for each nest. Gallego and Topaloglu (2014) and Feldman and Topaloglu

(2015) give constant factor approximation algorithms for (Cap-Assort). The d-level nested logit

Electronic copy available at: https://ssrn.com/abstract=2543309

D´esir, Goyal and Zhang: Capacitated Assortment Optimization: Hardness and Approximation

(d-NL) model generalises the NL model: customers ﬁrst choose a nest by going down a decision

tree of depth d and then pick an item in the chosen nest. Li et al. (2015) give an exact algorithm

for (Assort) under the d-NL model.

Markov chain model. In the Markov chain choice model (Zhang and Cooper 2005, Blanchet

et al. 2016) substitutions are captured by transitions in a Markov chain. In particular, each item

(including the no-purchase option) corresponds to a state, and substitutions are modelled using

transitions in the Markov chain. Blanchet et al. (2016) study the predictive power of this model.

In particular, they show that the Markov chain strictly generalizes the MNL model and that it

provides a good approximation to a large class of choice models. They also show that (Assort)

can be solved in polynomial time under the Markov chain model. D´esir et al. (2020) show that

(Card-Assort) is APX-hard even under a Markov chain model, i.e., it is NP-hard to approximate

this assortment optimization problem within some constant strictly smaller than 1. D´esir et al.

(2020) give a constant factor approximation algorithm for (Cap-Assort) under the Markov chain

model.

1.2. Our contributions

In this paper, we develop approximation algorithms for a large class of choice models. We summarize

our contributions below.

Hardness of approximation. We begin by establishing two hardness results. The ﬁrst one is that

(Cap-Assort) is NP-hard even for the simplest parametric model, namely the MNL model. Note

that this is in stark contrast to (Assort) and (Card-Assort) which are polynomially solvable under

the MNL model. These hardness results help deﬁne what type of approximation is achievable. In

particular, the ﬁrst hardness result implies that the best possible algorithm for (Cap-Assort) is an

approximation scheme. In particular, for any  > 0, we focus in this paper on fully polynomial time

approximation schemes (FPTASes) where an FPTAS gives a (1−)-approximation for the problem

in time polynomial in the input size and 1/.

We next show a stronger hardness result for (Assort) under the MMNL model which is already

known to be NP-hard (Rusmevichientong et al. 2014). In particular, we show that (Assort) under

the MMNL model is hard to approximate within any reasonable factor when the number of mixtures

is not constant. More speciﬁcally, there is no polynomial time algorithm (polynomial in n, K and

the input size) with an approximation factor better than O(1/K

1−δ

) for any constant δ > 0 for

(Assort) under the MMNL model unless NP ⊆ BP P . This second hardness result implies that if

we require a near-optimal algorithm for the assortment optimization under the MMNL model, its

running time must have a super-polynomial dependence on the number of mixtures. Moreover,

Electronic copy available at: https://ssrn.com/abstract=2543309

D´esir, Goyal and Zhang: Capacitated Assortment Optimization: Hardness and Approximation

our reduction gives a natural family of hard benchmark instances for the assortment optimization

problem under the MMNL model that may be of independent interest.

Approximation schemes for MMNL and MC models. We present a general framework

to design FPTASes when the expected revenue objective depends on a small number of linear

functions of the assortment. Note that for the MNL model, the expected revenue objective given

in (1) is a ratio of two linear functions of the assortment. For the MMNL model, it is a sum of

ratios of linear functions (see (2)). The main idea of our framework is to try to ﬁnd an assortment

that simultaneously approximates all those linear functions values corresponding to the optimal

assortment.

Our framework gives an FPTAS for (Cap-Assort) under the MMNL model when the number of

mixture is constant. Indeed, the running time of our algorithm is polynomial in the input size and

1/ but is exponential in the number of mixture for the MMNL model. Note that for the MMNL

model, a super-polynomial dependence on the number of mixture is unavoidable given our hardness

result.

Our framework also gives an FPTAS for (Cap-Assort) under the Markov chain model when the

rank of the underlying Markov chain is constant. Indeed, the running time of our algorithm is

polynomial in the input size and 1/ but is exponential in the rank of the underlying Markov chain.

For the Markov chain model, D´esir et al. (2020) show that (Cap-Assort) is NP-hard to approximate

this assortment optimization problem within some constant strictly smaller than 1. Therefore

additional assumptions (such as constant rank) are needed if one wants to get a near-optimal

algorithm. We would like to remark that unlike for the MMNL model, the choice probabilities

in the Markov chain model do not admit simple closed form expression but rather are expressed

through a system of linear equations. Therefore, one needs to express the revenue function into

carefully chosen linear functions in order to apply our framework.

We would like to note that our framework is quite related to the multi-dimensional knapsack

problem which is strongly NP-hard and does not admit an FPTAS (see Frieze and Clarke (1984)).

In the multi-dimensional knapsack problem, all the capacity constraints need to be satisﬁed strictly.

In contrast, we can allow small deviations as compared to the values of these linear functions for

optimal assortment; thereby, allowing us to overcome the strong NP-hardness of the multidimen-

sional knapsack problem and give an FPTAS.

Approximation schemes for d-level nested logit model. We also consider the nested logit

(NL) and d-level nested (d-NL) models.

While the revenue function for the NL model is also of the form of sum of ratios, naively adapting

our framework would lead to an exponential dependence on the number of nests. In contrast, we

Electronic copy available at: https://ssrn.com/abstract=2543309

剩余29页未读，继续阅读

评论收藏

内容反馈

weixin_38502814

粉丝: 5
资源: 927

容量分类优化：硬度和近似值-研究论文

论文研究-磁共振灌注成像血容量优化量化.pdf

论文研究 - 锂硅纳米线各向异性体积膨胀的减小和比电荷容量的优化

具有有限资源容量和未知需求参数的多产品定价的联合学习和优化-研究论文

数学学科分类指南MathematicsSubjectClassication(MSC 2010)

模拟滤波器设计：使用 Butterworth & Chebyshev 近似值的模拟滤波器设计。-matlab

模拟滤波器设计：使用 Butterworth & Chebyshev 近似值的模拟滤波器设计。-matlab开

pytorch-kfac：KFAC的Pytorch实现-这是https：github.comtensorflowkfac的端口

论文研究-基于航班时刻优化的跑道运行容量提升方法.pdf

用于评估智能交通系统峰值容量利用率的优化模型-研究论文

Asymptotic inferences for an AR(1) model with a change point: stationary and nearly non-stationary cases

组合优化：精确算法和近似算法Combinatorial Optimization: Exact and Approximate Algorithms

使用函数求余弦函数的近似值

基于C++使用泰勒级数求e的x次方（ex）近似值

在数组中快速查找近似值

求sinx和cosx的近似值代码

20210225-招商证券-“琢璞”系列报告之三十：基于遗传算法的股票分类和组合优化.pdf

云计算平台下基于近似ε-约束的多目标作业调度优化算法.pdf

行业分类-设备装置-一种实时移动空间关键字近似Top-k查询方法.zip

优化设计-fmincon函数介绍-序列二次规划(SQP)-subspace_trust_region-active_sett

论文研究 - 关于近似值函数的梯度

多伦多大学首篇《逆优化: 理论与应用》综述论文

论文研究-S-粗信息矩阵与它的动态特征.pdf

响应自适应临床试验设计的近似方法-研究论文

Approximation algorithms 近似算法 - Vazirani.pdf

组合最优化算法和复杂性

最新资源