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

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 when decision variables are part of the choice model. To this end, a simulation procedure proposed by Paneque et al. (2021) is applied to get a formulation as a mixed integer linear program (MILP). However, due to the large number of variables stemming from the simulation, 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 for general-purpose solvers. 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 fastest commercially available 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.