Haering, T., Legault, R., Torres, F., Ljubic, I., and Bierlaire, M. (2023)

Exact Algorithms for Continuous Pricing with Advanced Discrete Choice Demand Models

We present the Breakpoint Exact Algorithm (BEA) together with a Spatial Branch and Bound (B&B), and Spatial Branch and Benders Decomposition (B&BD) ap- proach to tackle the uncapacitated choice-based pricing problem (CPP) where de- mand is captured by a discrete choice model (DCM). Integrating advanced DCMs into optimization problems is challenging, due to the lack of closed-form probabil- ity expressions. 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 exploit utility breakpoints to develop the BEA, which scales polynomially in the number of customers and draws, along with an efficient Spatial Branch and Bound algo- rithm utilizing the McCormick envelope for relaxations, which are then solved using Benders decomposition. Our methods are evaluated against solving the MILP, QCQP, or QCQP-L with GUROBI, on a mixed logit parking space op- erator case study. We outspeed the state of the art by several orders of magnitude when optimizing one or two prices and reduce computational time drastically for larger numbers of prices. This methodology suits all choice-based optimization problems with linear-in-price utilities, given any random utility model.