Hoang Giang Pham, Tien Mai
10 min
Abstract
The mixed logit model is a flexible and widely used demand model in pricing and revenue management. However, existing work on mixed-logit pricing largely focuses on unconstrained settings, limiting its applicability in practice where prices are subject to business or regulatory constraints. We study the constrained pricing problem under multinomial and mixed logit demand models. For the multinomial logit model, corresponding to a single customer segment, we show that the constrained pricing problem admits a polynomial-time approximation scheme (PTAS) via a reformulation based on exponential cone programming, yielding an $\varepsilon$-optimal solution in polynomial time. For finite mixed logit models with $T$ customer segments, we reformulate the problem as a bilinear exponential cone program with $O(T)$ bilinear terms. This structure enables a Branch-and-Bound algorithm whose complexity is exponential only in $T$. Consequently, constrained pricing under finite mixtures of logit admits a PTAS when the number of customer segments is bounded. Numerical experiments demonstrate strong performance relative to state-of-the-art baselines.
Alex: Huh—so for one group, it's fully convex after tweaks, giving exact solutions fast. But with multiple groups, those peaks multiply—does it break?
Sam: Yes, mixtures add layers: revenue sums segment-specific terms, each with its own denominator, creating products of variables—one per segment—that curve wrongly. They isolate those T tricky products into bilinear terms, like y_t equals θ_t times z_t, reformulating the rest convex via similar exp cones. A tailored branch-and-bound then systematically splits bounds on just those T terms, relaxing each branch with tight linear bounds called McCormick envelopes—like fencing in a bilinear curve with four straight lines that hug it close—yielding near-optimum prices in time exploding only with segments, polynomial otherwise.
Alex: So managers get global near-optima if segments stay few, avoiding heuristic traps.
Sam: The paper notes local methods risk big losses from multi-peaks, projecting unconstrained prices ignores constraints badly, but this exploits structure for reliability with moderate segments—like airlines segmenting business and leisure without overkill. It urges parsimonious grouping for efficiency.
Alex: For that single-group case, what makes the transformed problem so reliable—beyond just the binary search?
Sam: After swapping to u variables that track the exponential drop in product appeal, the revenue curve becomes strictly quasiconcave. Picture a single smooth hill in the math landscape—no wiggles or multiple tops—so any peak you climb to is the global best, unlike the bumpy original where prices can fool you into side hills. They prove this mathematically, meaning solvers find the unique top reliably.
Alex: A single hill... that explains why gradient climbs work in principle. But the paper skips those for bisection and cone checks—why?
Sam: Gradient methods need tricky step choices and slow down near flat spots, plus projecting onto limits adds hassle without accuracy promises. Bisection turns it to convex checks via exponential cones that interior-point solvers handle in polynomial time, scaling well with products. This yields near-exact solutions efficiently despite original bumps.
Alex: Now for mixtures—how does isolating those T bilinear products enable the branch-and-bound without exploding everywhere?
Sam: They introduce y_t for each segment's revenue numerator sum and z_t for its denominator, with bilinear y_t equals θ_t times z_t linking segment revenue guess to totals—all else convex via exp cones. Branch-and-bound splits only on those T products' bounds, relaxing each with McCormick envelopes: four straight lines hugging the curved y=θz tightly from above and below, like a snug wireframe cage letting convex solvers prune bad branches fast. Complexity grows exponentially just in T, polynomial in products and constraints—fine if segments stay few, like two or three for airlines.
Alex: That structure keeps it practical then. Local searches miss those global spots, but this fences in the nonconvex bits systematically.
Sam: Yes—the first approximation scheme for mixtures with limits, handling real rules like capacity or pairwise price gaps under equal sensitivities, without heuristic risks. Practitioners gain near-optimal prices reliably when grouping customers simply.
Alex: How does the branch-and-bound actually relax those tricky products at each step to prune bad paths?
Sam: At any point in the search, they have rough bounds on each segment's guess θ_t and denominator z_t—like a box around possible values. The curved link y_t equals θ_t times z_t gets fenced in by four straight lines: two under and two over it, forming a tight cage that any point inside must obey. This McCormick envelope turns the node into a convex problem solvable exactly, giving an upper bound—if too low compared to known good solutions, discard the whole branch.
Alex: So those lines hug the curve closer as bounds shrink—like refining a sketch until it matches perfectly?
Sam: Exactly. They start bounds from price limits, branch on the biggest violation—bisect the widest variable in that θz pair—and prune if infeasible or upper bound too low.
Alex: So even constrained mixtures scale if segments stay few—smarter than full grids.
Sam: Right. For single segment, bisection's faster, exploiting unimodality—but mixtures need the tailored tree.
Alex: How does it stack up against common practical methods, like gradient searches companies might use?
Sam: The paper tests it on simulated airline-like data with up to 100 products and 2 to 4 customer segments. They compare against a gradient-based local search—which climbs hills by following the steepest profit slope at each step, adjusting prices bit by bit while respecting limits—and an older branch-and-bound for unlimited prices. In tough cases with both capacity limits and rules like no product priced over half another, the new method scales steadily as products grow, hitting near-perfect prices within an hour, while gradients slow sharply and leave revenue on the table.
Alex: Why do those gradient climbs fail here more than usual?
Sam: Gradients chase local peaks, but constraints like capacity—total weighted prices can't exceed a budget—and pairwise gaps couple products tightly, twisting the landscape into traps. The paper shows this in their hardest tests: local search runtime explodes for big instances, stuck far from best. Their branch-and-bound prunes systematically using those tight linear cages on bilinears, proving reliable even then.
Alex: Huh—and what about shortcuts, like pretending multiple segments are just one averaged group to use the fast single-case solver?
Sam: They test collapsing segments into one by averaging tastes and sensitivities, solving that easy single-hill problem. It loses substantially because varied groups react differently to prices under limits, distorting the fit. The gap stays structural, so ignoring variety costs persistently.
Alex: Distorted decisions from averaging... that warns against oversimplifying customers.
Sam: Exactly. They also check ignoring limits: solve unlimited prices, then project closest feasible by minimizing distance squared to constraints. Losses average substantial revenue, as unconstrained optima often violate capacities or gaps badly. This underscores directly tackling limits with mixtures for real value.
Alex: So heuristics and proxies falter under constraints, but this delivers close-to-best reliably. Practical edge clear.
Sam: Precisely—this unified cone framework gives the first approximation scheme for mixtures under constraints. Firms avoid heuristic pitfalls, capturing pricing flexibility in heterogeneous settings.
Alex: A solid step for reliable pricing tools. Thanks, Sam—that clarifies the value.
Sam: My pleasure, Alex. That's the key from this work. Thanks for listening to ResearchPod.