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

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

The choice-based pricing problem (CPP) consists in optimizing product prices while accounting for consumer preferences and potential capacity constraints. Demand is typically modeled using a discrete choice model (DCM). We introduce the Breakpoint Heuristic Algorithm (BHA) to address the CPP with and without capacity constraints as well as an extension of the Breakpoint Exact Algorithm (BEA) to handle capacities, together with 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. Capacity management is handled by an exogenous priority queue. Results show that, in the capacitated case, the BEA solves a larger set of instances within the time limit than the state-of-the-art MILP formulation, achieving identical revenues on all completed instances and better solutions in cases where the MILP fails to converge. The proposed BHA heuristic performs well across both low- and high-dimensional instances, consistently producing near-optimal solutions with an average gap below 0.2%. In the uncapacitated case, BHA and its ILS extension solve all tested instances—including high-dimensional ones—for which exact methods such as BEA and B\&BD often exceed time limits. The BHA also improves the performance of B&BD when used to guide the search and generate valid inequalities. In mixed-logit pricing problems, both BHA and ILS solve benchmark instances significantly faster than methods specialized for this setting, while maintaining solution quality; the ILS matches all known optima, and the BHA maintains an average gap below 0.02%.