Haering, T., Legault, R., Torres, F., and Bierlaire, M.

Fast Algorithms for (Capacitated) Continuous Pricing with Discrete Choice Demand Models

Speaker: Haering Tom

STRC 2024

May 15, 2024

We introduce the Breakpoint Exact Algorithm with Capacity (BEAC), based on the state-of-the-art Breakpoint Exact Algorithm (BEA) to address the choice-based pricing problem (CPP) with capacity constraints, together with the Breakpoint Heuristic Algorithm (BHA) for both uncapacitated and capacitated instances. In addition, we develop valid inequalities for the MILP formulation of the CPP, allowing us to use the heuristic solution to speed up the exact Branch \& Benders Decomposition (B\&BD) approach. When including capacity, an approach based on an exogenous priority queue, as well as a supplier-controlled queuing strategy to generate maximal or minimal profit for robust optimization, is developed. The BHA leverages a coordinate descent method, which produces high-quality solutions in a short time. Results show that when optimizing two prices simultaneously, in the capacitated case, the BEAC reports runtimes up to 20 times faster than the state-of-the-art mixed-integer linear programming (MILP) approach, while the BHA performs from 100 to 5000 times faster than the MILP. 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 show significant improvements in computational time for the exact method (B\&BD) when using the heuristic solution to guide the algorithm.