Exact algorithms for continuous pricing with advanced discrete choice demand models
We present a spatial Branch and Bound and spatial Branch and Benders Decomposition approach together with the Breakpoint Exact Algorithm (BEA) to tackle the uncapacitated choice-based pricing problem (CPP) where demand is captured by a discrete choice model (DCM) based on the random utility principl...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2024
|
| Online Access: | https://hdl.handle.net/1721.1/157700 |
| _version_ | 1824458433992065024 |
|---|---|
| author | Haering, Tom Legault, Robin Torres, Fabian Ljubić, Ivana Bierlaire, Michel |
| author2 | Massachusetts Institute of Technology. Operations Research Center |
| author_facet | Massachusetts Institute of Technology. Operations Research Center Haering, Tom Legault, Robin Torres, Fabian Ljubić, Ivana Bierlaire, Michel |
| author_sort | Haering, Tom |
| collection | MIT |
| description | We present a spatial Branch and Bound and spatial Branch and Benders Decomposition approach together with the Breakpoint Exact Algorithm (BEA) to tackle the uncapacitated choice-based pricing problem (CPP) where demand is captured by a discrete choice model (DCM) based on the random utility principle. We leverage problem characteristics to reformulate the state-of-the-art simulation-based formulation of the CPP as a mixed-integer linear program (MILP) into a non-convex quadratically constrained quadratic program (QCQP), and then into a non-convex QCQP with linear objective (QCQP-L). We solve this reformulation with an efficient spatial Branch and Bound procedure utilizing the McCormick envelope for relaxations, which are then solved using Benders decomposition. We further exploit utility breakpoints to develop the BEA, which scales polynomially in the number of customers and draws, providing a fast option for low numbers of prices. Our methods are evaluated against solving the MILP, QCQP, or QCQP-L with GUROBI on a mixed logit (ML) parking space operator case study. We outspeed the MILP by several orders of magnitude when optimizing one or two prices and reduce computational time drastically for larger numbers of prices. When comparing to algorithms tailored for the CPP with ML demand specifically, our approaches significantly outperform the state of the art. Our methodology suits all choice-based optimization problems with linear-in-price utilities, given any DCM. |
| first_indexed | 2025-02-19T04:25:49Z |
| format | Article |
| id | mit-1721.1/157700 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:25:49Z |
| publishDate | 2024 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1577002025-01-02T04:17:01Z Exact algorithms for continuous pricing with advanced discrete choice demand models Haering, Tom Legault, Robin Torres, Fabian Ljubić, Ivana Bierlaire, Michel Massachusetts Institute of Technology. Operations Research Center We present a spatial Branch and Bound and spatial Branch and Benders Decomposition approach together with the Breakpoint Exact Algorithm (BEA) to tackle the uncapacitated choice-based pricing problem (CPP) where demand is captured by a discrete choice model (DCM) based on the random utility principle. We leverage problem characteristics to reformulate the state-of-the-art simulation-based formulation of the CPP as a mixed-integer linear program (MILP) into a non-convex quadratically constrained quadratic program (QCQP), and then into a non-convex QCQP with linear objective (QCQP-L). We solve this reformulation with an efficient spatial Branch and Bound procedure utilizing the McCormick envelope for relaxations, which are then solved using Benders decomposition. We further exploit utility breakpoints to develop the BEA, which scales polynomially in the number of customers and draws, providing a fast option for low numbers of prices. Our methods are evaluated against solving the MILP, QCQP, or QCQP-L with GUROBI on a mixed logit (ML) parking space operator case study. We outspeed the MILP by several orders of magnitude when optimizing one or two prices and reduce computational time drastically for larger numbers of prices. When comparing to algorithms tailored for the CPP with ML demand specifically, our approaches significantly outperform the state of the art. Our methodology suits all choice-based optimization problems with linear-in-price utilities, given any DCM. 2024-12-02T17:48:08Z 2024-12-02T17:48:08Z 2024-11-26 2024-12-01T04:16:23Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/157700 Haering, T., Legault, R., Torres, F. et al. Exact algorithms for continuous pricing with advanced discrete choice demand models. OR Spectrum (2024). PUBLISHER_CC en https://doi.org/10.1007/s00291-024-00799-3 OR Spectrum Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Haering, Tom Legault, Robin Torres, Fabian Ljubić, Ivana Bierlaire, Michel Exact algorithms for continuous pricing with advanced discrete choice demand models |
| title | Exact algorithms for continuous pricing with advanced discrete choice demand models |
| title_full | Exact algorithms for continuous pricing with advanced discrete choice demand models |
| title_fullStr | Exact algorithms for continuous pricing with advanced discrete choice demand models |
| title_full_unstemmed | Exact algorithms for continuous pricing with advanced discrete choice demand models |
| title_short | Exact algorithms for continuous pricing with advanced discrete choice demand models |
| title_sort | exact algorithms for continuous pricing with advanced discrete choice demand models |
| url | https://hdl.handle.net/1721.1/157700 |
| work_keys_str_mv | AT haeringtom exactalgorithmsforcontinuouspricingwithadvanceddiscretechoicedemandmodels AT legaultrobin exactalgorithmsforcontinuouspricingwithadvanceddiscretechoicedemandmodels AT torresfabian exactalgorithmsforcontinuouspricingwithadvanceddiscretechoicedemandmodels AT ljubicivana exactalgorithmsforcontinuouspricingwithadvanceddiscretechoicedemandmodels AT bierlairemichel exactalgorithmsforcontinuouspricingwithadvanceddiscretechoicedemandmodels |