Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.26056 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918412580552704 |
|---|---|
| author | He, Taotao Wu, Zhongqi Zhang, Yating |
| author_facet | He, Taotao Wu, Zhongqi Zhang, Yating |
| contents | We study logit-based multi-purchase choice models and develop an exact solution methodology for the resulting assortment optimization problems, which we show are NP-hard to approximate. We introduce a hypergraph representation that captures general bundle-based choice structures and subsumes several models in the literature, including the BundleMVL-K and multivariate MNL models (Tulabandhula et al. 2023, Jasin et al. 2024). Leveraging this representation, we derive mixed-integer programming (MIP) formulations by integrating polyhedral relaxations from multilinear optimization with a perspective reformulation of the logit choice model. Our approach preserves the strength of the underlying polyhedral relaxations, yielding formulations with provably tighter linear programming (LP) bounds than the prevalent Big-M approach. We further characterize structural conditions on the hypergraph under which the formulations are locally sharp, thereby generalizing existing LP characterizations for path-based models. The framework extends naturally to heterogeneous and robust settings. Computational experiments demonstrate that the proposed formulations significantly improve both solution quality and scalability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_26056 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On MIP Formulations for Logit-Based Multi-Purchase Choice Models and Applications He, Taotao Wu, Zhongqi Zhang, Yating Optimization and Control We study logit-based multi-purchase choice models and develop an exact solution methodology for the resulting assortment optimization problems, which we show are NP-hard to approximate. We introduce a hypergraph representation that captures general bundle-based choice structures and subsumes several models in the literature, including the BundleMVL-K and multivariate MNL models (Tulabandhula et al. 2023, Jasin et al. 2024). Leveraging this representation, we derive mixed-integer programming (MIP) formulations by integrating polyhedral relaxations from multilinear optimization with a perspective reformulation of the logit choice model. Our approach preserves the strength of the underlying polyhedral relaxations, yielding formulations with provably tighter linear programming (LP) bounds than the prevalent Big-M approach. We further characterize structural conditions on the hypergraph under which the formulations are locally sharp, thereby generalizing existing LP characterizations for path-based models. The framework extends naturally to heterogeneous and robust settings. Computational experiments demonstrate that the proposed formulations significantly improve both solution quality and scalability. |
| title | On MIP Formulations for Logit-Based Multi-Purchase Choice Models and Applications |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2603.26056 |