Text

Constrained Assortment Optimization Under the Paired Combinatorial Logit Model

We study the assortment optimization problem when customer choices are governed by the paired combinatorial logit model. We study unconstrained, cardinality-constrained, and knapsack-constrained versions of this problem, which are all known to be NP-hard. We design efficient algorithms that compute approximately optimal solutions, using a novel relation to the maximum directed cut problem and suitable linear-program rounding algorithms. We obtain a randomized polynomial time approximation scheme for the unconstrained version and performance guarantees of 50% and ≈50% for the cardinality-constrained and knapsack-constrained versions, respectively. These bounds improve significantly over prior work. We also obtain a performance guarantee of 38.5% for the assortment problem under more general constraints, such as multidimensional knapsack (where products have multiple attributes and there is a knapsack constraint on each attribute) and partition constraints (where products are partitioned into groups and there is a limit on the number of products selected from each group). In addition, we implemented our algorithms and tested them on random instances available in prior literature. We compared our algorithms against an upper bound obtained using a linear program. Our average performance bounds for the unconstrained, cardinality-constrained, knapsack-constrained, and partition-constrained versions are over 99%, 99%, 96%, and 99%, respectively.

Ketersediaan

Informasi Detail

Judul Seri

OPERATIONS RESEARCH; Vol.70 No.2 March-April 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 786-804

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

ASSORTMENT OPTIMIZATION
SUBMODULARITY
LINEAR AND SEMIDEFINITE PROGRAMMING

Info Detail Spesifik

https://doi.org/10.1287/opre.2021.2188

Pernyataan Tanggungjawab

Rohan Ghuge, Joseph Kwon, Viswanath Nagarajan, Adetee Sharma

Versi lain/terkait

Lampiran Berkas

Komentar