Assortment Optimization with General Linear Constraints Under the Paired Combinatorial Logit Choice Model

We consider the assortment optimization problem under general linear constraints, where the customer choice behavior is governed by the paired combinatorial logit model. In the literature, only the unconstrained problem and the problem with constraints that can be written as “Formula: see text” linear inequalities with nonnegative coefficients, such as cardinality and knapsack constraints, are studied, and only approximation algorithms exist for these problems. We develop four exact solution approaches to solve the problem with any linear constraints to optimality. First, we reformulate the problem, which in its original form is a fractional program, as a mixed-integer linear programming (MILP) model, and solve the resulting formulation directly by a commercial solver. We then develop a classical Benders decomposition algorithm and enhance it with additional cuts. We further develop a parametric search method to solve the original fractional program optimally by solving a series of nonfractional parametric problems. Our extensive computational experiments show that, although the direct MILP approach and the classical Benders decomposition can solve instances with up to 100 products to optimality, the parametric search approach and the enhanced Benders decomposition approach are far more effective and can solve much larger instances (with 500 products) to optimality within reasonable computation time. We also derive several valuable insights regarding how each of the major problem parameters impacts the optimal expected revenue, and how the products included in the optimal assortment differ from those not included. In addition, we consider three extensions of the problem to include pricing decisions or to a more general setting with multiple customer segments or multiple stages and develop exact solution approaches for each extension. Funding: This work was supported by the National Natural Science Foundation of China Grants 72471189, 72310107003, 71901176, and 72271201. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0830 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0830 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .