Enumerative algorithms for choice-based pricing under capacity constraints

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 is managed in all algorithms by the use of 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 iterated local search-based (ILS) extension solve all tested instances 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.03%. • Breakpoint Heuristic Algorithm (BHA) solves choice-based pricing problems with and without capacity. • BHA and ILS deliver near-optimal solutions drastically faster than exact meth- ods for large-scale CPP. • BHA can be used to guide exact Branch and Bound methods together with valid inequalities. • BHA outperforms CMA-ES in computational time and solution quality for choice-based pricing. • Mixed-logit pricing problems solved faster with BHA and ILS than with spe- cialized methods.