Publication Type

Book Chapter

Version

acceptedVersion

Publication Date

1-2026

Abstract

This work concerns the assortment optimization problem that refers to selecting a subset of items that maximizes the expected revenue in the presence of the substitution behavior of consumers specified by a random utility choice model. The key challenge lies in the computational difficulty of finding the best subset solution, which often requires exhaustive search. The literature on constrained assortment optimization lacks a practically efficient method that is general to deal with different types of customer choice models (e.g., the multinomial logit, mixed logit or general multivariate extreme value models). In this work, we propose a new approach that allows to address this issue. The idea is that, under a general choice model, we formulate the problem into a binary nonlinear programming model, and use an iterative algorithm to find a binary solution. At each iteration, we propose a way to approximate the objective (expected revenue) by a linear function, and a polynomial-time algorithm to find a candidate solution using this approximate function. We also develop a greedy local search algorithm to further improve the solutions. We test our algorithm on instances of different sizes under various discrete choice model structures and show that our algorithm dominates existing exact and heuristic approaches in the literature, both in terms of solution quality and computing cost.

Keywords

Assortment optimization, Binary nonlinear optimization, Choice models

Discipline

Numerical Analysis and Scientific Computing | Theory and Algorithms

Research Areas

Data Science and Engineering

Publication

Data Science and Optimization

Volume

91

Editor

Sanjeena Dang, Antoine Deza, Swati Gupta, Paul D. McNicholas, Sebastian Pokutta, & Masashi Sugiyama

First Page

1

Last Page

40

ISBN

9783032038449

Identifier

10.1007/978-3-032-03844-9_1

Publisher

Springer

City or Country

Cham

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1007/978-3-032-03844-9_1

Download

Share

COinS