Capacitated assortment and price optimization under the nested logit model

Rui Chen () and Hai Jiang ()
Additional contact information
Rui Chen: Tsinghua University
Hai Jiang: Tsinghua University

Journal of Global Optimization, 2020, vol. 77, issue 4, No 8, 895-918

Abstract: Abstract We study the capacitated assortment and price optimization problem, where a retailer sells categories of substitutable products subject to a capacity constraint. The goal of the retailer is to determine the subset of products as well as their selling prices so as to maximize the expected revenue. We model the customer purchase behavior using the nested logit model and formulate this problem as a non-linear binary integer program. For this NP-complete problem, we show that there exists a pseudo polynomial time approximation scheme that finds its $$\epsilon $$ ϵ -approximate solution. We first convert the original problem into an equivalent fixed point problem. We then show that finding an $$\epsilon $$ ϵ -approximate solution to the fixed point problem can be achieved by binary search, where a non-linear auxiliary problem is repeatedly approximated by a dynamic programing based algorithm involving an approximation to a series of multiple-choice parametric knapsack problems. For the special case when the capacity constraints are cardinal and nest-specific, we develop an algorithm that finds the optimal solution in strongly polynomial time. Moreover, our algorithm can be directly applied to find an $$\epsilon $$ ϵ -approximate solution to the capacitated assortment optimization problem under the nested logit model, which is the first approximate algorithm that is polynomial with respect to the number of nests in the literature.

Keywords: Assortment optimization; Nested logit model; Approximate algorithm; Combinatorial optimization (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-020-00896-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:77:y:2020:i:4:d:10.1007_s10898-020-00896-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-020-00896-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().