Haering, T., Legault, R., Torres, F., and Bierlaire, M. (2024)

Heuristics and Exact Algorithms for Choice-Based Capacitated and Uncapacitated Continuous Pricing

We introduce the Breakpoint Heuristic Algorithm (BHA) to address the choice-based pricing problem (CPP) with and without capacity constraints as well as valid inequalities for the QCQP-L (quadratically constrained quadratic program with linear objective) formulation of the uncapacitated CPP, allowing us to speed up the exact Branch & Benders Decomposition (B&BD) approach. The BHA is based on the Breakpoint Exact Algorithm (BEA) which we extend to handle capacity constraints, implemented using an exogenous priority queue. Results show that, when optimizing the prices of two capacitated alternatives simultaneously, the BEA reports runtimes up to 20 times faster than the state-of-the-art mixed-integer linear programming (MILP) approach, while the BHA, leveraging a coordinate descent method, overall performs up to 5000 times faster than the MILP, while producing high-quality solutions. For the uncapacitated case, the BHA outspeeds the BEA as well as the B&BD approach by multiple orders of magnitude, especially for high-dimensional instances. Our results further show significant improvements in computational time for the exact method (B&BD) when adding the valid inequalities together with the heuristic solution to guide the algorithm. The BHA significantly surpasses state-of-the-art methods, including those tailored for mixed logit models, in speed while maintaining an optimality gap of less than 0.02%.