← Domaines d'expertise/Revenue Management/2025

Tarification exacte basée sur les choix, jusqu'à 1,67 million de fois plus rapide que la baseline MILP

Un algorithme spatial Branch-and-Benders + un Breakpoint Exact Algorithm en temps polynomial qui résout 1 000 000 scénarios de demande en 77 secondes et bat le précédent état de l'art ML-spécifique (CoBiT) d'un facteur 300×

La tarification sous modèles de demande modernes, mixed logit, nested logit, tout ce qui est plus riche qu'un tableur Sales 101, est une impasse algorithmique depuis des décennies. La formulation MILP de référence cale au-delà de deux prix. L'état de l'art admettait qu'« exact » était hors d'atteinte.

Nos travaux ont changé cela. Publiée dans OR Spectrum, notre décomposition spatiale Branch-and-Benders et notre Breakpoint Exact Algorithm battent le solveur MILP de Gurobi de plusieurs ordres de grandeur, et notre résultat de complexité fournit un schéma en temps polynomial en le nombre de clients et de tirages.

1,67 × 10⁶ ×

accélération sur Gurobi MILP en optimisation à un prix à R = 5 000 scénarios

1 000 000

scénarios de demande résolus en 77 secondes par le Breakpoint Exact Algorithm

300×

plus rapide que CoBiT, le précédent état de l'art pour la tarification ML-spécifique

OR Spectrum

évalué par les pairs et publié, Haering et al. 2024

Le défi

La tarification basée sur les choix, choisir des prix qui maximisent le revenu quand la demande est générée par un modèle de choix discret dérivé de la théorie d'utilité aléatoire, est fondamentale pour les compagnies aériennes, les hôtels, les détaillants et les exploitants de parking. Pourtant la formulation exacte existante, le MILP basé sur la simulation de Paneque et al. (2021), passe exponentiellement à l'échelle en nombre de tirages.

Les solveurs standards traînent au-delà de tailles triviales ; les heuristiques spécialisées ne fonctionnent que pour des spécifications de demande restreintes. Il n'existait pas d'algorithme exact général pour ce problème.

Notre démarche

Nous avons reformulé le MILP canonique en un Quadratically Constrained Quadratic Program avec objectif linéaire (QCQP-L), exposant une structure que le MILP enterrait. Nous avons ensuite conçu un Branch-and-Bound spatial sur mesure qui utilise des enveloppes de McCormick pour des relaxations serrées et branche par violation maximale plutôt que par arête la plus longue.

Nous avons accéléré chaque nœud de B&B avec la décomposition de Benders, de sorte que la partie coûteuse de la relaxation soit résolue par une séquence de sous-problèmes bon marché plutôt qu'un seul LP monolithique. Le pipeline complet est ce que nous appelons B&BD, Branch-and-Benders Decomposition spatiale.

Nous avons ensuite exploité la structure constante par morceaux des probabilités de choix le long de l'axe des prix pour développer le Breakpoint Exact Algorithm (BEA), dont la complexité est polynomiale en nombre de clients et de tirages (et exponentielle seulement en nombre de produits tarifés), ce qui en fait l'algorithme de choix quand la dimension de prix est petite.

Le résultat

Livrable : trois algorithmes exacts pour la tarification continue basée sur les choix sous tout DCM à utilité linéaire en prix (mixed logit, nested logit, probit, paired combinatorial logit, toute la famille), plus un benchmark complet sur l'étude de cas parking d'Ibeas et al. (2014) avec demande mixed-logit. Le Breakpoint Exact Algorithm résout 1 000 000 scénarios de demande en 77 secondes, là où la reformulation QCQP-L de Gurobi prend 83 651 secondes à seulement R = 5 000 scénarios — une accélération de 1,67 million de fois. Les variantes Branch-and-Bound et Branch-and-Benders dominent quand trois prix ou plus sont optimisés simultanément, avec jusqu'à 20× d'accélération sur Gurobi à quatre prix.

Face à CoBiT (Marandi et Lurkin 2023), l'état de l'art publié pour la tarification ML-spécifique, nos méthodes sont en moyenne 42× plus rapides (B&B), 8× plus rapides (B&BD) et 300× plus rapides (BEA) sur les instances à deux prix. CoBiT est fait main pour le mixed logit ; nos méthodes fonctionnent sur tout DCM à utilité linéaire en prix — et l'applicabilité plus large ne coûte pas de temps d'exécution, elle en gagne. Publié dans OR Spectrum, Haering et al. 2024.

Plongée technique

Le modèle derrière le résultat.

Le modèle

Le problème consiste à fixer J prix contrôlés pour maximiser le revenu attendu quand N clients choisissent parmi J + K alternatives sous une demande dérivée de l'utilité aléatoire. Pour les DCMs modernes (mixed logit, probit, nested logit), les probabilités de choix n'ont pas de forme close, donc Paneque et al. (2021) les ont approchées en tirant R scénarios Monte Carlo des termes d'erreur, en figeant chaque tirage en une utilité déterministe, et en écrivant un énorme MILP basé sur la simulation. Le piège : chaque triplet (i, n, r) introduit un produit bilinéaire pᵢ ωᵢₙᵣ entre le prix et l'indicateur binaire de choix, que le MILP linéarise avec des auxiliaires big-M, et le modèle explose exponentiellement en R. Notre chaîne de reformulations supprime cette structure.

U_{in r} = c_{in r} + β_{p}^{in} p_{i}, ω_{in r} = 1 [U_{in r} = j \in C_{n} max U_{j n r}], P_{n} (i) \approx \frac{1}{R} r \sum ω_{in r} .

Cadre de simulation. Pour chaque tirage Monte Carlo r ∈ {1, …, R}, l'utilité du produit i pour le client n est une constante déterministe c_inr plus un terme linéaire en prix β_p · p_i. La variable de choix ω_inr vaut 1 ssi le produit i gagne l'arg-max pour (n, r). La moyenne de ω sur les R tirages donne un estimateur sans biais de la vraie probabilité de choix, et converge vers la demande ML/probit/NL sous-jacente quand R → ∞.

p, ω, U, h max \frac{1}{R} r \in R \sum n \in N \sum i \in C_{n} \sum p_{i} ω_{in r} s.t. ω \in {0, 1}^{(J + 1) N R}, KKT for each (n, r) .

MILP de Paneque et al. (Formulation 4). L'objectif est le revenu attendu. Les contraintes imposent que les variables de choix ω résolvent un knapsack par (n, r) de maximisation d'utilité, encodé via la dualité forte (faisabilité primale + duale + complémentarité). Les bilinéaires p_i · ω_inr dans l'objectif sont linéarisés avec des auxiliaires big-M η_inr, cette linéarisation détruit la totale unimodularité du knapsack et force le problème à croître exponentiellement en R.

ω \in [0, 1]^{(J + 1) N R}, η_{in r} = p_{i} ω_{in r}, (QCQP-L, Formulation 6).

Notre première reformulation. On relâche l'intégrité sur ω (le knapsack par (n, r) est totalement unimodulaire, donc la relaxation LP est entière dès que les utilités sont distinctes) et on garde la bilinéarité η_inr = p_i ω_inr comme égalité quadratique non convexe explicite. Résultat : un QCQP non convexe avec objectif linéaire. Toute la non-convexité est désormais isolée dans un seul bloc de contraintes bilinéaires, le reste du modèle est linéaire.

η_{in r} \geq p_{i}^{L} ω_{in r}, η_{in r} \leq p_{i}^{L} ω_{in r} + p_{i} - p_{i}^{L}, η_{in r} \geq p_{i}^{U} ω_{in r} + p_{i} - p_{i}^{U}, η_{in r} \leq p_{i}^{U} ω_{in r} .

Enveloppe de McCormick. On remplace chaque égalité bilinéaire η_inr = p_i ω_inr par quatre inégalités linéaires valides sur la boîte courante [p_i^L, p_i^U] × [0, 1]. C'est la relaxation convexe linéaire la plus serrée de la bilinéarité ; plus serrée à mesure que la boîte rétrécit. Le LP résultant (Formulation 7) fournit une borne supérieure sur le revenu QCQP-L à chaque nœud B&B.

branch_index = ar g i \in {1, \dots, J} max n, r \sum \overset{η}{ˉ}_{in r} - \overset{p}{ˉ}_{i} \overset{ω}{ˉ}_{in r} .

Règle de branchement sur mesure. Au lieu de brancher sur l'arête la plus longue (B&B spatial de manuel), nous branchons sur le prix dont la contrainte bilinéaire est la plus violée en moyenne sur (n, r) à la solution de relaxation courante. Empiriquement cela domine le branchement par arête, pondéré par part de marché et aléatoire sur toutes les classes d'instances testées. Nous branchons uniquement sur les J variables de prix, jamais sur les JNR η ou ω, ce qui effondre l'arbre de plusieurs ordres de grandeur par rapport à ce que Gurobi fait sur le QCQP-L brut.

p_{i}^{⋆} \in {\frac{c _{0 n r} - c _{in r}}{β _{p}^{in}} : n \in N, r \in R} \cup {p_{i}^{L}, p_{i}^{U}}, ∣ B_{i} ∣ \leq N R + 2.

Structure des points de rupture. À tout prix optimal p_i*, un client n dans un scénario r doit être exactement indifférent entre l'alternative i et la suivante, sinon nous pourrions augmenter p_i de ε sans perdre personne. Résoudre l'équation d'indifférence donne au plus NR + 2 prix candidats par produit (bornes de la boîte incluses). L'énumération sur J produits donne l'arbre de recherche que le BEA explore.

T_{BEA} (N, R, J) = O ((N R)^{J}) - polynomial in N, R; exponential only in J .

Complexité du BEA. Le premier algorithme en temps polynomial en (clients, tirages) pour la tarification basée sur les choix. Pour un ou deux produits tarifés, dramatiquement plus rapide que tout branch-and-bound, le BEA a résolu le problème à un prix avec un million de tirages en 77 secondes ; la formulation QCQP-L de Gurobi a expiré à 7 000 tirages après un jour complet. Pour trois produits tarifés ou plus, le J dans l'exposant fait exploser le BEA, et l'approche B&B / B&BD gagne.

Trois algorithmes, un article. Le B&B spatial avec branchement sur mesure bat Gurobi-sur-le-MILP et Gurobi-sur-le-QCQP-L proprement d'un ordre de grandeur. Ajouter la décomposition de Benders à chaque nœud (B&BD) projette les JNR η et ω, ce qui compte d'autant plus que l'instance est grande : il dépasse le B&B simple à 500 tirages pour quatre prix, 1 000 tirages pour deux prix, 3 000 tirages pour un prix. Le BEA domine tout quand J ≤ 2 car la structure de points de rupture est énumérable ; B&B / B&BD dominent quand J ≥ 3 car l'arbre de points de rupture est exponentiel en J. Le bon algorithme dépend de la dimension de prix, et notre article rend le choix explicite, avec le résultat de complexité à l'appui.

Benchmark

Optimisation à deux prix sur l'étude de cas de parking d'Ibeas et al. (2014) (J = 2, N = 50 clients, R = nombre de tirages de simulation variable). Tous les temps en secondes, tolérance d'optimalité 0,01 %, limite 72 h, Gurobi 10.0.3 avec réglage des hyperparamètres. Les cinq méthodes retrouvent les mêmes prix optimaux p₁ ≈ 0,56 et p₂ ≈ 0,67 avec un revenu ≈ 27,0.

Tirages R	MILP (Paneque)	QCQP	QCQP-L	B&B (notre)	B&BD (notre)	BEA (notre)
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

Le MILP passe catastrophiquement à l'échelle avec le nombre de tirages, de 2,5 heures à R = 200 à 67,5 heures à R = 500, une explosion de temps d'exécution × 27 pour 2,5× plus de tirages. La reformulation continue (QCQP, QCQP-L) achète déjà un facteur 5–9 en supprimant la taxe big-M. Notre B&B spatial avec branchement sur mesure bat le MILP de ~30× partout ; le B&BD échange une partie de cette avance contre un overhead qui ne rapporte qu'aux grandes échelles. Le BEA est dans une autre ligue : à R = 500 il trouve l'optimum prouvé en 69 secondes contre 242 877 secondes pour le MILP, une accélération de 3 520×. L'histoire devient plus dramatique aux grands R : à 5 000 tirages le BEA résout en 0,05 seconde là où le QCQP-L de Gurobi prend 83 651 secondes (facteur 1,6 × 10⁶) ; à 1 000 000 tirages le BEA termine encore en 77 secondes.

Tiré du dossier

Formulation 4 de l'article : le MILP basé sur la simulation de Paneque et al. (2021), l'état de l'art antérieur. Les produits bilinéaires p_i · ω_inr dans l'objectif et dans les contraintes ζ_nr sont ce qui fait mal : leur linéarisation avec des auxiliaires big-M brise la totale unimodularité du knapsack par client, ce qui explique pourquoi la taille du modèle et le temps d'exécution explosent exponentiellement en R.

Formulations 5 et 6 : notre reformulation en deux étapes. La Form. 5 (QCQP) relâche l'intégrité sur ω et garde le bilinéaire p_i · ω_inr dans la contrainte ζ_nr, exploitant que la relaxation LP du knapsack est déjà entière sous utilités distinctes. La Form. 6 (QCQP-L) introduit ensuite η_inr = p_i · ω_inr comme contrainte bilinéaire explicite et tire toute la non-convexité dans un bloc, la seule chose sur laquelle le B&B spatial doit brancher.

Figure 3 et Formulation 7 de l'article : l'arbre B&B spatial (en haut) et la relaxation LP de McCormick résolue à chaque nœud (en bas). Chaque sous-problème hérite d'une boîte plus serrée [p̂_i^L, p̂_i^U] ; les inégalités de McCormick λ¹ – λ⁴ remplacent la bilinéarité η_inr = p_i ω_inr par l'enveloppe convexe linéaire la plus serrée sur la boîte courante. Nous branchons uniquement sur les J variables de prix (pas sur les JNR η ou ω), ce qui garde l'arbre gérable à mesure que la taille des instances augmente.

Figure 1 de l'article (encart) : la forme en escalier de la fonction revenu en un seul prix pour un seul client simulé. Le revenu saute au prix où le client devient indifférent entre le produit tarifé et le opt-out. Avec N clients et R tirages il y a au plus NR sauts, le BEA exploite cette structure discrète pour trouver l'optimum global en énumérant ces points de rupture en temps polynomial.

Techniques

Branch-and-Bound spatial
Décomposition de Benders
Relaxations par enveloppe de McCormick
Énumération de points de rupture
Modélisation par utilité aléatoire / DCM

Stack

Python
Gurobi 10
Julia (comparaison CoBiT)
Stack de modèles de choix discret

Un problème de ce type ?

Nous serions ravis d'en entendre parler.

contact@optimally.ch