Exact algorithms for continuous pricing with advanced discrete choice demand models
Open Access
- 26 November 2024
- journal article
- research article
- Published by Springer Nature in OR Spectrum
- p. 1-47
Abstract
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.Keywords
Funding Information
- EPFL Lausanne
This publication has 30 references indexed in Scilit:
- Delivery Time Slot Management Problem2023
- An exact algorithm for the static pricing problem under discrete mixed logit demandEURO Journal on Computational Optimization, 2023
- A Lagrangian decomposition scheme for choice-based optimizationComputers & Operations Research, 2022
- Integer Programming2020
- Mathematical programming approaches to pricing problems4OR, 2015
- ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear EquationsJournal of Global Optimization, 2014
- Mixed-logit network pricingComputational Optimization and Applications, 2013
- Mixed MNL models for discrete responseJournal of Applied Econometrics, 2000
- BARON: A general purpose global optimization software packageJournal of Global Optimization, 1996
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problemsMathematical Programming, 1976