Une heuristique de tarification avec <0,2 % d'écart d'optimalité et jusqu'à 37 millions × d'accélération sur l'état de l'art

Variables du CPP capacité et contrainte de file de priorité. Les clients sont traités dans un ordre exogène (file de tickets, heure d'arrivée, priorité de segment, selon les besoins de l'application). Le nouveau binaire y_inr indique si l'alternative i est encore disponible quand le client n arrive en scénario r ; la famille de contraintes (f_inr, g_inr dans l'article) dit que y_inr bascule à 0 dès que les sélections cumulées de l'alternative i atteignent sa capacité c_i. Retirer la file de priorité et la remplacer par une inégalité de capacité globale permettrait au solveur de réordonner les clients de manière endogène, irréaliste et sous-estimant la volatilité du revenu.

Ce que coûte la capacité. Maintenant que ω est vraiment binaire, la bilinéarité p_i ω_inr doit être linéarisée avec des auxiliaires big-M (le MILP originel de Paneque et al.). La reformulation QCQP-L qui alimentait notre travail non capacité ne s'applique plus : la relaxation LP n'est pas entière, donc nous ne pouvons pas relâcher ω. Traduction : toute la chaîne algorithmique pricing1 (B&B spatial, B&BD, enveloppes de McCormick) s'effondre, et la seule approche exacte restante est le MILP, qui expire empiriquement à R ≥ 50.

Complexité du BEA capacité. Nous avons étendu le BEA en remplaçant sa mise à jour incrémentale par une passe d'allocation par file de priorité aux feuilles de l'arbre d'énumération. Ce correctif préserve la correction mais ajoute un facteur NRJ par niveau de récursion (nous devons considérer les J alternatives à chaque point de rupture, pas seulement une). Asymptotiquement : toujours polynomial en N et R, toujours exponentiel en J, mais la constante devant est significativement pire que la borne O(J!(NR)^J log NR) du cas non capacité.

Breakpoint Heuristic Algorithm : ascension par coordonnées sur le vecteur de prix, où chaque pas résout un BEA à un prix (la dimension où le BEA est bon marché, seulement NR points de rupture à évaluer, pas d'arbre de permutation). À l'itération t nous figeons tous les prix sauf j(t), énumérons les au plus NR + 2 prix candidats pour cette coordonnée sous l'état actuel de la file, évaluons l'objectif capacité complet à chaque candidat et choisissons le meilleur. Nous cyclons sur les dimensions jusqu'à ce que J passes consécutives de coordonnées ne produisent aucune amélioration.

Complexité effective du BHA. K est le nombre de cycles externes (empiriquement 5–20 sur les benchmarks), J le nombre de passes de coordonnées par cycle, NR le nombre de points de rupture par coordonnée, et NRJ le coût d'une évaluation de l'objectif par file de priorité. Le terme exponentiel en J qui écrase le BEA-cap exact a disparu, remplacé par un coût quadratique en (NR), ce qui explique pourquoi le BHA monte en charge là où la méthode exacte ne peut pas. Le prix : aucun certificat d'optimalité.

Enveloppe Iterated Local Search. Au lieu de muter la solution incumbente après chaque terminaison du BHA (ILS de manuel), nous élargissons le pas et relançons la recherche en ligne. C'est l'opérateur de perturbation : quand la recherche locale épuise le voisinage à petits pas, sauter à un plus grossier, ré-explorer, accepter sur amélioration. Continuer jusqu'à ce que δ dépasse Δ_max. Empiriquement cela ferme l'écart résiduel sur les benchmarks, ILS atteint tout optimum connu là où le BHA laisse ~0,04 % sur la table.

Méthode exacte guidée par l'heuristique. Nous injectons la solution du BHA dans notre Branch-and-Benders Decomposition spatial (non capacité) comme forte borne inférieure initiale, et nous en dérivons de nouvelles inégalités valides pour la formulation QCQP-L autour. Effet combiné sur le temps du B&BD pour atteindre 10 % d'écart d'optimalité : jusqu'à 54 % d'accélération à J = 4 (le régime où les méthodes exactes restent faisables). L'heuristique et la méthode exacte s'aident désormais mutuellement.