Exaktes Choice-Based Pricing, bis zu 1,67 Millionen Mal schneller als die MILP-Baseline
Ein räumlicher Branch-and-Benders-Algorithmus + ein polynomialer Breakpoint Exact Algorithm, der 1’000’000 Nachfrageszenarien in 77 Sekunden löst und den bisherigen ML-spezifischen Stand der Technik (CoBiT) um 300× schlägt
Pricing unter modernen Nachfragemodellen, Mixed Logit, Nested Logit, allem reicher als ein Sales-101-Spreadsheet, war jahrzehntelang eine algorithmische Sackgasse. Die Lehrbuch-MILP-Formulierung knickt nach zwei Preisen ein. Der Stand der Technik räumte ein, dass ‘exakt’ schlicht ausser Reichweite ist.
Unsere Arbeit hat das geändert. Publiziert in OR Spectrum: unsere räumliche Branch-and-Benders-Dekomposition und der Breakpoint Exact Algorithm schlagen Gurobis MILP-Solver um Grössenordnungen, und unser Komplexitätsresultat liefert ein polynomiales Schema in Kunden- und Draw-Anzahl.
Die Herausforderung
Choice-basiertes Pricing, Preise wählen, die den Umsatz maximieren, wenn die Nachfrage aus einem Discrete-Choice-Modell aus der Random-Utility-Theorie stammt, ist fundamental für Airlines, Hotels, Händler und Parkplatzbetreiber. Die bestehende exakte Formulierung, das simulationsbasierte MILP von Paneque et al. (2021), skaliert jedoch exponentiell mit der Anzahl Preis-Draws.
Standard-Solver kriechen über triviale Grössen hinaus; spezialisierte Heuristiken funktionieren nur für eingeschränkte Nachfragespezifikationen. Es gab keinen generellen, exakten Algorithmus für dieses Problem.
Unser Vorgehen
Wir haben das kanonische MILP in ein nicht-konvexes Quadratically Constrained Quadratic Program mit linearer Zielfunktion (QCQP-L) reformuliert und damit Struktur freigelegt, die das MILP versteckt. Dann haben wir ein massgeschneidertes räumliches Branch-and-Bound entworfen, das McCormick-Hüllen für enge Relaxierungen nutzt und nach maximaler Verletzung verzweigt, nicht nach längster Kante.
An jedem B&B-Knoten haben wir mit Benders-Dekomposition beschleunigt, sodass der teure Teil der Relaxierung als Folge billiger Subprobleme gelöst wird, nicht als ein monolithisches LP. Die volle Pipeline nennen wir B&BD, räumliche Branch-and-Benders-Dekomposition.
Wir haben dann die stückweise-konstante Struktur der Choice-Wahrscheinlichkeiten entlang der Preisachse genutzt, um den Breakpoint Exact Algorithm (BEA) zu entwickeln, dessen Komplexität polynomial in Kunden- und Simulations-Draw-Anzahl ist (und nur exponentiell in der Anzahl bepreister Produkte), die erste Wahl, wenn die Preisdimension klein ist.
Das Ergebnis
Deliverable: drei exakte Algorithmen für kontinuierliches Choice-basiertes Pricing unter jedem DCM mit linear-in-Preis-Nutzen (Mixed Logit, Nested Logit, Probit, Paired Combinatorial Logit, alles aus der Familie), plus ein vollständiger Benchmark auf der Ibeas-et-al.-(2014)-Parkplatz-Fallstudie mit Mixed-Logit-Nachfrage. Der Breakpoint Exact Algorithm löst 1’000’000 Nachfrageszenarien in 77 Sekunden, wo Gurobis QCQP-L-Reformulation bereits bei R = 5’000 Szenarien 83’651 Sekunden braucht — eine 1,67-Millionen-fache Beschleunigung. Die Branch-and-Bound- und Branch-and-Benders-Varianten dominieren, wenn drei oder mehr Preise gleichzeitig optimiert werden, mit bis zu 20×-Beschleunigung gegenüber Gurobi bei vier Preisen.
Gegenüber CoBiT (Marandi und Lurkin 2023), dem publizierten Stand der Technik für ML-spezifisches Pricing, sind unsere Methoden auf Zwei-Preis-Instanzen durchschnittlich 42× schneller (B&B), 8× schneller (B&BD) und 300× schneller (BEA). CoBiT ist handgebaut für Mixed Logit; unsere Methoden funktionieren auf jedem DCM mit linear-in-Preis-Nutzen — und die breitere Anwendbarkeit kostet keine Laufzeit, sie gewinnt sie. Publiziert in OR Spectrum, Haering et al. 2024.
Technischer Deep Dive
Das Modell hinter dem Ergebnis.
Das Modell
Das Problem: J kontrollierte Preise setzen, um den erwarteten Umsatz zu maximieren, wenn N Kunden zwischen J + K Alternativen unter Random-Utility-abgeleiteter Nachfrage wählen. Für moderne DCMs (Mixed Logit, Probit, Nested Logit) haben die Choice-Wahrscheinlichkeiten keine geschlossene Form, Paneque et al. (2021) approximierten sie also, indem sie R Monte-Carlo-Szenarien der Fehlerterme ziehen, jedes Draw zu einer deterministischen Utility einfrieren und ein riesiges simulationsbasiertes MILP schreiben. Der Haken: Jedes Tripel (i, n, r) führt ein bilineares Produkt pᵢ ωᵢₙᵣ zwischen Preis und Choice-Indikator ein, das das MILP per Big-M-Hilfsvariablen linearisiert, und das Modell wächst exponentiell in R. Unsere Reformulierungs-Kette streift diese Struktur ab.
Simulationsrahmen. Für jedes Monte-Carlo-Draw r ∈ {1, …, R} besteht der Nutzen von Kunde n für Produkt i aus einer deterministischen Konstanten c_inr plus einem preislinearen Term β_p · p_i. Die Choice-Variable ω_inr ist 1 genau dann, wenn Produkt i das Arg-Max für (n, r) gewinnt. Das Mittel von ω über die R Draws ist ein erwartungstreuer Schätzer der wahren Choice-Wahrscheinlichkeit, und konvergiert für R → ∞ gegen die zugrunde liegende ML/Probit/NL-Nachfrage.
Das MILP von Paneque et al. (Formulierung 4). Die Zielfunktion ist der erwartete Umsatz. Constraints erzwingen, dass die Choice-Variablen ω einen Per-(n, r)-Nutzenmaximierungs-Knapsack lösen, kodiert über starke Dualität (primäre Zulässigkeit + duale Zulässigkeit + Komplementarität). Die Bilinearitäten p_i · ω_inr in der Zielfunktion werden mit Big-M-Hilfsvariablen η_inr linearisiert, diese Linearisierung zerstört die totale Unimodularität des Knapsacks und zwingt das Problem zu exponentiellem Wachstum in R.
Unsere erste Reformulierung. Wir lassen die Ganzzahligkeit auf ω fallen (der Per-(n, r)-Knapsack ist total unimodular, also ist die LP-Relaxierung ganzzahlig, sobald die Utilities verschieden sind) und behalten die Bilinearität η_inr = p_i ω_inr als explizite nicht-konvexe quadratische Gleichung. Resultat: ein nicht-konvexes QCQP mit linearer Zielfunktion. Die gesamte Nicht-Konvexität sitzt jetzt in einem Block bilinearer Constraints, der Rest des Modells ist linear.
McCormick-Hülle. Jede Bilinearitätsgleichung η_inr = p_i ω_inr wird durch vier lineare Ungleichungen ersetzt, gültig über die aktuelle Box [p_i^L, p_i^U] × [0, 1]. Das ist die engste lineare konvexe Relaxierung der Bilinearität; enger, je kleiner die Box. Das resultierende LP (Formulierung 7) liefert eine obere Schranke auf den QCQP-L-Umsatz an jedem B&B-Knoten.
Massgeschneiderte Verzweigungsregel. Statt längster Kante (Lehrbuch-räumliches-B&B) verzweigen wir auf den Preis, dessen Bilinearitäts-Constraint an der aktuellen Relaxierungslösung im Mittel über (n, r) am stärksten verletzt ist. Empirisch dominiert das längste Kante, marktanteilsgewichtete und zufällige Verzweigung in jeder getesteten Instanzklasse. Wir verzweigen nur auf die J Preisvariablen, niemals auf die JNR η oder ω, was den Suchbaum gegenüber dem, was Gurobi auf dem rohen QCQP-L tut, um Grössenordnungen schrumpft.
Breakpoint-Struktur. Bei jedem optimalen Preis p_i* muss ein Kunde n in einem Szenario r exakt indifferent zwischen Alternative i und der nächstbesten Option sein, sonst könnten wir p_i um ε erhöhen, ohne jemanden zu verlieren. Auflösung der Indifferenzgleichung liefert höchstens NR + 2 Kandidatenpreise pro Produkt (inkl. Box-Endpunkte). Aufzählen über J Produkte ergibt den Suchbaum, den der BEA erkundet.
BEA-Komplexität. Der erste polynomial-in-(Kunden, Draws)-Algorithmus für choice-basiertes Pricing. Bei ein oder zwei bepreisten Produkten dramatisch schneller als jedes Branch-and-Bound, der BEA löst das Ein-Preis-Problem bei einer Million Draws in 77 Sekunden; Gurobis QCQP-L-Formulierung läuft bei 7 000 Draws nach einem ganzen Tag ins Zeitlimit. Bei drei oder mehr bepreisten Produkten lässt das J im Exponenten den BEA explodieren, und der B&B/B&BD-Ansatz gewinnt.
Drei Algorithmen, ein Paper. Das räumliche B&B mit massgeschneiderter Verzweigung schlägt Gurobi-auf-dem-MILP und Gurobi-auf-dem-QCQP-L sauber um eine Grössenordnung. Benders-Dekomposition an jedem Knoten (B&BD) projiziert die JNR η und ω heraus, was umso wichtiger wird, je grösser die Instanz: B&BD zieht ab 500 Draws bei vier Preisen, 1 000 Draws bei zwei Preisen, 3 000 Draws bei einem Preis am reinen B&B vorbei. Der BEA dominiert alles für J ≤ 2, weil die Breakpoint-Struktur aufzählbar ist; B&B/B&BD dominieren für J ≥ 3, weil der Breakpoint-Baum exponentiell in J ist. Der richtige Algorithmus hängt von der Preisdimension ab, und unser Paper macht die Wahl explizit, mit dem zugehörigen Komplexitätsresultat.
Benchmark
Zwei-Preis-Optimierung auf der Parking-Fallstudie von Ibeas et al. (2014) (J = 2, N = 50 Kunden, variables R = Anzahl Simulations-Draws). Alle Zeiten in Sekunden, 0,01 % Optimalitätstoleranz, 72 h Zeitlimit, Gurobi 10.0.3 mit Hyperparameter-Tuning. Alle fünf Methoden finden dieselben optimalen Preise p₁ ≈ 0,56 und p₂ ≈ 0,67 mit Umsatz ≈ 27,0.
| Draws R | MILP (Paneque) | QCQP | QCQP-L | B&B (unser) | B&BD (unser) | BEA (unser) |
|---|---|---|---|---|---|---|
| 200 | 9 042 | 4 195 | 3 403 | 1 386 | 3 015 | 11 |
| 300 | 42 804 | 9 503 | 7 951 | 2 998 | 5 418 | 24 |
| 400 | 112 335 | 22 567 | 19 283 | 6 378 | 11 858 | 41 |
| 500 | 242 877 | 32 886 | 25 030 | 7 963 | 12 064 | 69 |
Das MILP skaliert katastrophal mit der Anzahl Draws, von 2,5 Stunden bei R = 200 auf 67,5 Stunden bei R = 500, eine 27×-Laufzeitexplosion für 2,5× mehr Draws. Die kontinuierliche Reformulierung (QCQP, QCQP-L) bringt bereits Faktor 5–9 durch Entfernen der Big-M-Steuer. Unser räumliches B&B mit massgeschneiderter Verzweigung schlägt das MILP überall um ~30×; das B&BD tauscht etwas von diesem Vorsprung gegen Overhead, der sich nur bei grösseren Skalen auszahlt. Der BEA spielt in einer anderen Liga: Bei R = 500 findet er das nachgewiesene Optimum in 69 Sekunden statt 242 877 Sekunden wie das MILP, ein 3 520×-Speed-up. Die Geschichte wird bei grossen R dramatischer: Bei 5 000 Draws löst der BEA in 0,05 Sekunden, wo Gurobis QCQP-L 83 651 Sekunden braucht (Faktor 1,6 × 10⁶); bei 1 000 000 Draws bleibt der BEA bei 77 Sekunden.
Aus den Unterlagen
![Abbildung 3 und Formulierung 7 aus dem Paper: der räumliche B&B-Baum (oben) und die McCormick-LP-Relaxierung, die an jedem Knoten gelöst wird (unten). Jedes Subproblem erbt eine engere Box [p̂_i^L, p̂_i^U]; die McCormick-Ungleichungen λ¹ – λ⁴ ersetzen die Bilinearität η_inr = p_i ω_inr durch die engste lineare konvexe Hülle über die aktuelle Box. Wir verzweigen nur auf die J Preisvariablen (nicht auf die JNR η oder ω), was den Baum bei wachsender Instanzgrösse beherrschbar hält.](/figures/pricing1/p-14.png)
Techniken
- Räumliches Branch-and-Bound
- Benders-Dekomposition
- McCormick-Hüllen-Relaxierungen
- Breakpoint-Enumeration
- Random Utility / DCM-Modellierung
Stack
- Python
- Gurobi 10
- Julia (CoBiT-Vergleich)
- Discrete-Choice-Modellierungs-Stack
Ein Problem wie dieses?