Haering, T., and Bierlaire, M. (2023)

A Spatial Branch and Bound Algorithm for Continuous Pricing with Advanced Discrete Choice Demand Modeling

23rd Swiss Transport Research Conference, Ascona, Switzerland

In this paper, we present a spatial branch and bound algorithm to tackle the continuous pricing problem, where demand is captured by an advanced discrete choice model (DCM). Advanced DCMs, like mixed logit or latent class models, are capable of modeling demand on the level of individuals very accurately due to a focus on behavioral realism. The downside of such realistic models is that it is highly nontrivial to include the resulting demand probabilities into an optimization problem, as they usually do not have a convex or even closed-form expression. To this end, a simulation procedure is applied to get a formulation as a mixed integer linear program (MILP). However, due to its size, this MILP is very hard to solve. We first propose to solve the problem as a non-convex quadratically constrained quadratic program (QCQP) instead, where total unimodularity guarantees the integrality of the solution. Isolating all non-convexity into a set of bilinear constraints leads to a formulation as a non-convex quadratically constrained linear program (QCLP) that proves computationally beneficial. Lastly, we present a spatial branch and bound algorithm that employs the McCormick envelope to obtain relaxations and makes use of total unimodularity to generate feasible solutions and thus lower bounds for the maximization fast. We compare the proposed method to the general purpose solver GUROBI, on a parking choice case study from Ibeas et al. (2014). The results show that the custom spatial branch and bound approach outspeeds GUROBI by a factor of at least 35x for the MILP formulation and at least 2.5x for the QCLP in single-price optimization, and a factor of at least 4.5x for the QCQP and 1.3x for the QCLP when optimizing multiple prices simultaneously. The ratio of the speedup further increases with the size of the instance.