Outer Approximation and Super-modular Cuts for Constrained Assortment Optimization under Mixed-Logit Model
In this paper, we study the assortment optimization problem under the mixed-logit customer choice model. While assortment optimization has been a major topic in revenue management for decades, the mixed-logit model is considered one of the most general and flexible approaches for modeling and predicting customer purchasing behavior. Existing exact methods have primarily relied on mixed-integer linear programming (MILP) or second-order cone (CONIC) reformulations, which allow for exact problem solving using off-the-shelf solvers. However, these approaches often suffer from weak continuous relaxations and are slow when solving large instances. Our work addresses the problem by focusing on components of the objective function that can be proven to be monotonically super-modular and convex. This allows us to derive valid cuts to outer-approximate the nonlinear objective functions. We then demonstrate that these valid cuts can be incorporated into Cutting Plane or Branch-and-Cut methods to solve the problem exactly. Extensive experiments show that our approaches consistently outperform previous methods in terms of both solution quality and computation time.
Code (0)
등록된 구현이 없습니다.
Tasks
Assortment OptimizationManagementvalidSimilar Papers 제목 키워드 기반
A disjunctive cut strengthening technique for convex MINLP
Generating polyhedral outer approximations and solving mixed-integer linear relaxations remains one of the main approaches for solving convex mixed-integer nonlinear programming (MINLP) problems. There are several algori…
validRobust Submodular Minimization with Applications to Cooperative Modeling
Robust Optimization is becoming increasingly important in machine learning applications. This paper studies the problem of robust submodular minimization subject to combinatorial constraints. Constrained Submodular Minim…
Image SegmentationSemantic SegmentationAn Outer-approximation Guided Optimization Approach for Constrained Neural Network Inverse Problems
This paper discusses an outer-approximation guided optimization method for constrained neural network inverse problems with rectified linear units. The constrained neural network inverse problems refer to an optimization…
Submodular Function Minimization and Polarity
Using polarity, we give an outer polyhedral approximation for the epigraph of set functions. For a submodular function, we prove that the corresponding polar relaxation is exact; hence, it is equivalent to the Lov\'asz e…
A Unified Framework of Constrained Robust Submodular Optimization with Applications
Robust optimization is becoming increasingly important in machine learning applications. In this paper, we study a unified framework of robust submodular optimization. We study this problem both from a minimization and m…
BIG-bench Machine Learningspeech-recognitionSpeech Recognition