← Areas of expertise/Revenue Management/2026

A Pricing Heuristic With <0.2% Optimality Gap and Up to 37 Million × Speedup Over the State-of-the-Art

The Breakpoint Heuristic Algorithm: solves capacitated pricing where every exact method times out, scales to 1,000,000 demand scenarios at six prices in under 8 minutes, beats LAG (capacitated specialist) by 79× and CoBiT (mixed-logit specialist) by up to 37 million ×

Exact algorithms are beautiful in print and inconvenient in production. Real pricing teams need answers in seconds, on instances with capacity constraints, and they need a quality guarantee they can defend in a meeting.

Our Breakpoint Heuristic Algorithm hits both. Published in Computers & Operations Research, it solves the capacitated and uncapacitated CPP with sub-0.2% gap on average, beating, in speed and quality, every published heuristic for this problem class.

<0.2%

average optimality gap on capacitated benchmarks where every exact method times out

37 × 10⁶ ×

max speedup over CoBiT, the published state-of-the-art for ML-specific pricing

79×

minimum speedup over LAG, the previous capacitated-pricing heuristic

1,000,000

demand scenarios solved at 6 prices in under 8 minutes

The challenge

The capacitated choice-based pricing problem (CPP), pricing under discrete-choice demand when products have finite capacity, is significantly harder than its uncapacitated cousin. Adding capacity destroys the per-customer knapsack's total-unimodularity, forcing the model back into MILP form: the Paneque et al. (2022) Lagrangian heuristic times out at 50 draws and 4 prices, and exact MILP only handles toy instances. None of the existing heuristics work across demand models.

Practitioners need a single, robust heuristic that performs across model classes, scales to high-dimensional instances, and gives them a defensible answer about how close they are to the true optimum.

Our approach

We extended our Breakpoint Exact Algorithm into a heuristic regime: the BHA enumerates breakpoints along a coordinate-descent path, accepting fast moves when they improve the objective and sidestepping the combinatorial blow-up of exact methods on multi-price instances.

Capacity is handled by an exogenous priority queue, a clean, model-agnostic trick that keeps the inner subproblem linear and lets us reuse all our uncapacitated machinery without touching the outer enumeration logic.

We combined the BHA with iterated local search to escape local optima; the resulting ILS variant matches all known optima on the mixed-logit benchmarks and finds higher-revenue solutions than the exact BEA when the exact method times out.

On the exact side we engineered new valid inequalities for the QCQP-L formulation, accelerating our Branch-and-Benders Decomposition; the BHA also serves as a top-class warm-starter for it (total speedups of up to 54% at the 10% gap, depending on dimension).

The outcome

Deliverable: the Breakpoint Heuristic Algorithm and its Iterated Local Search extension, a fast and scalable heuristic for the capacitated and uncapacitated choice-based pricing problem under any DCM with linear-in-price utility. On the parking-pricing benchmark with capacities, the BHA delivers an average optimality gap below 0.2% across all completed instances, and scales to 1,000,000 demand scenarios at six prices in 439 seconds (~ 7.3 minutes) on the uncapacitated case.

Versus LAG (Paneque et al. 2022), the previous capacitated-CPP heuristic, the BHA is at least 79× faster on every instance class tested. Versus CoBiT (Marandi and Lurkin 2023), the previous state-of-the-art for ML-specific pricing, the BHA hits up to 37-million-× speedups (Table 12, R = 100,000) and the ILS extension matches every known optimum. We also derived new valid inequalities for the spatial Branch-and-Benders Decomposition from our prior OR Spectrum paper, with the BHA serving as a top-class warm-starter — combined effect is up to 54% speedup at the 10% optimality gap. Published open-access in Computers & Operations Research, 2026.

Technical deep dive

The model behind the result.

The model

Adding capacity constraints to the choice-based pricing problem breaks everything that made the uncapacitated case tractable. The per-customer knapsack is no longer totally unimodular, so the QCQP-L relaxation isn't integral anymore, the problem reverts to a genuinely combinatorial MILP. Worse, when a product runs out of capacity, every customer's optimal choice depends on every other customer's choice, which means the BEA's incremental update trick fails: the objective can only be evaluated after assigning every customer through the priority queue. The BHA is built around this constraint: keep the BEA's breakpoint enumeration, but use it only along one price dimension at a time, evaluating the full objective each step.

U_{in r} = c_{in r} + β_{p}^{in} p_{i}, ω_{in r} \in {0, 1}, y_{in r} \in {0, 1}, m = 1 \sum n ω_{im r} \leq c_{i} - (c_{i} - 1) (1 - y_{in r}) .

Capacitated CPP variables and the priority-queue constraint. Customers are processed in an exogenous order (ticket-queue, arrival time, segment priority, whatever the application demands). The new binary y_inr indicates whether alternative i is still available when customer n arrives in scenario r; the constraint family (f_inr, g_inr in the paper) says that y_inr flips to 0 the moment the cumulative selections of alternative i reach its capacity c_i. Removing the priority queue and replacing it with a global capacity inequality would let the solver re-prioritize customers endogenously, which is unrealistic and would understate revenue volatility.

η_{in r} = p_{i} ω_{in r} ⟶ η_{in r} \leq p_{i}^{U} ω_{in r}, η_{in r} \leq p_{i}, η_{in r} \geq p_{i} - (1 - ω_{in r}) p_{i}^{U} . (Big-M is back.)

What capacity costs you. Now that ω is genuinely binary, the bilinear p_i ω_inr must be linearized with big-M auxiliaries (Paneque et al.'s original MILP). The QCQP-L reformulation that powered our uncapacitated work no longer applies: the LP relaxation isn't integral, so we can't relax ω. Translation: the entire pricing1 algorithmic chain (spatial B&B, B&BD, McCormick envelopes) collapses, and the only remaining exact approach is the MILP, which empirically times out at R ≥ 50.

T_{BEA-cap} (N, R, J) = O (J! (N R J)^{J + 1} lo g (N R J)) .

Capacitated BEA complexity. We extended the BEA by replacing its incremental objective update with a priority-queue allocation pass at the leaves of the enumeration tree. That fix preserves correctness but adds an NRJ factor per recursion level (we have to consider all J alternatives at each breakpoint, not just one). Asymptotically: still polynomial in N and R, still exponential in J, but the constant in front is meaningfully worse than the uncapacitated O(J!(NR)^J log NR) bound.

BHA: p_{j (t)}^{(t + 1)} = ar g p_{j (t)} \in B_{j (t)} (p_{- j}^{(t)}) max R (p_{- j (t)}^{(t)}, p_{j (t)}), j (t + 1) = (j (t) mod J) + 1.

Breakpoint Heuristic Algorithm: coordinate-ascent over the price vector, where each step solves a single-price BEA (the dimension where the BEA is cheap, only NR breakpoints to evaluate, no permutation tree). At iteration t we freeze all prices except j(t), enumerate the at-most-NR + 2 candidate prices for that coordinate under the current state of the queue, evaluate the full capacitated objective at each candidate, and pick the best. Cycle through dimensions until J consecutive coordinate passes produce no improvement.

T_{BHA} (N, R, J) = O (K \cdot J \cdot N R \cdot N R J) = O (K (N R)^{2} J^{2}),

BHA effective complexity. K is the number of outer cycles (empirically 5–20 on benchmark instances), J is the number of coordinate sweeps per cycle, NR is the breakpoint count per coordinate, and NRJ is the cost of one priority-queue objective evaluation. The exponential-in-J term that crushes the exact BEA-cap is gone, replaced by a quadratic-in-(NR) cost, which is exactly why the BHA scales to instances the exact method can't touch. The price: no optimality certificate.

ILS perturbation: δ \leftarrow γ δ whenever a full BHA pass fails to improve; p_{i} \leftarrow p_{i} \pm k δ, k \in {1, \dots, K} .

Iterated Local Search wrapping. Instead of mutating the incumbent solution after each BHA termination (textbook ILS), we expand the step size and re-run the line search. This is the perturbation operator: when local search exhausts the small-step neighborhood, jump to a coarser one, re-explore, and accept on improvement. Continue until δ exceeds Δ_max. Empirically this closes the residual gap on benchmark instances, ILS matches every known optimum where BHA leaves ~0.04% on the table.

BHA-guided B&BD: LB \leftarrow R_{BHA}, η_{in r} \leq p_{i}^{BHA} + \nabla R \cdot (p - p^{BHA}) (valid inequalities) .

Heuristic-guided exact method. We feed the BHA's solution into our (uncapacitated) spatial Branch-and-Benders Decomposition as a strong initial lower bound, and we derive new valid inequalities for the QCQP-L formulation around it. Combined effect on B&BD runtime to reach 10% optimality gap: up to 54% speedup at J = 4 (the regime where exact methods are still feasible). The heuristic and the exact method now help each other.

Four algorithmic contributions in one paper: the capacitated BEA, the BHA, the ILS extension, and the BHA-guided B&BD with new valid inequalities. The BHA is the keystone, it's the algorithm that goes into production, because it produces near-optimal solutions in tractable time on the realistic-scale instances the exact methods can't reach. The ILS layer is the option you turn on when solution quality matters more than runtime. The valid inequalities and heuristic guidance are how the exact B&BD now competes with specialized mixed-logit algorithms (CoBiT, LAG) on their home turf, and wins, by factors of 10⁴ – 10⁷.

Benchmark

Test 2 from the paper: capacitated parking-pricing on the Ibeas et al. (2014) case study, N = 50 customers, capacities (20, 20) for J = 2 and (15, 15, 15, 15) for J = 4. All times in seconds. MILP and BEA are exact (gap = 0); CMA-ES is a general-purpose evolution-strategy baseline; BHA and ILS are ours. On every completed instance, the BHA returns the same revenue as the exact methods to within 0.2%, and the ILS matches the exact optimum exactly.

R	J	MILP	BEA (capacitated)	CMA-ES	BHA (ours)	ILS (ours)
2	2	5	0.5	0.6	0.2	1.2
10	2	173	12	2.3	0.6	21
25	2	3,224	174	8	3.6	129
50	2	> 5 h	1,291	18	8	558
100	2	> 25 h	9,914	132	51	2,793
250	2	> 45 h	> 45 h	1,084	435	16,357
10	4	> 10 h	> 10 h	23	6	517
100	4	> 45 h	> 45 h	1,693	828	34,963

The MILP gives up at R = 50 (5-hour limit hit, revenue gap > 8% vs. true optimum). The BEA carries the exact-method banner further, solving R = 100, J = 2 in 2.75 hours, but it's already two orders of magnitude slower than the BHA, which finishes the same instance in 51 seconds. By R = 250 even the BEA times out, while the BHA still terminates in 7 minutes. The four-price story is sharper: every exact method fails at R = 10, J = 4, but the BHA returns near-optimal solutions across the entire R = 10..200 range. CMA-ES is a useful sanity check, a respected metaheuristic, but it's slower than the BHA by 2–10× and consistently returns 2–3% lower revenue. Beyond this test: Table 6 in the paper shows the BHA solving J = 6, R = 1,000,000 in 439 seconds (under 8 minutes); Table 12 shows BHA outpacing the mixed-logit-specific CoBiT by speedup factors of 3.5 × 10⁴ to 3.7 × 10⁶.

From the record

Formulations 1 and 2 from the paper: the QCQP-L formulation that powered our uncapacitated pricing work (left) sits next to the capacitated MILP (right). The capacitated version adds the availability variables y_inr, the discounted utility variables υ_inr, and the priority-queue constraints (f_inr, g_inr). Notice the size of the change: nearly every constraint family expands, and the bilinear linearization with big-M comes back. This is why the capacitated case is genuinely a different algorithmic problem, not just the uncapacitated one with an extra inequality.

Figure 1 from the paper: the capacitated BEA enumeration tree for three simulated customers and two priced alternatives. Each node is a partial price configuration; each branch corresponds to fixing the next coordinate's price to one of the customer-scenario breakpoints. The exponential-in-J growth visible here is exactly what motivates the BHA: by running a 1D BEA at a time (instead of a J-dimensional one) we walk a single root-to-leaf path per coordinate sweep instead of enumerating the full tree.

Algorithms 1–4 from the paper: the uncapacitated BEA (Algorithms 1–2) and its capacitated extension (Algorithms 3–4). The structural change is in `enumerate_cap`: at each recursion level it can't reuse intermediate customer decisions, because capacity-induced interdependencies between alternatives mean the objective has to be re-evaluated from scratch via the priority queue at every leaf. That extra NRJ-factor at the leaves is why the capacitated BEA's complexity gets the +1 in the exponent.

Glossary of the algorithm family. CPP is the choice-based pricing problem; QCQP-L is the non-convex reformulation from our prior work; BEA is the exact algorithm; BHA is the new heuristic; ILS is its iterated-local-search extension; B&B and B&BD are the spatial branch-and-bound methods used for exact uncapacitated solves. LAG (Paneque et al.) and CoBiT (Marandi and Lurkin) are the prior state-of-the-art heuristics for the capacitated and mixed-logit settings respectively, the algorithms we benchmark against in Test 8.

Techniques

Coordinate-ascent breakpoint search
Iterated local search (adaptive step size)
Priority-queue capacity handling
Valid inequalities for QCQP-L
Heuristic guidance for spatial B&BD

Stack

Python
Gurobi 13
Julia (CoBiT comparison)
C++ inner loops

A problem like this?

We'd like to hear about it.

contact@optimally.ch