Learning to Cut: Reinforcement Learning for Benders Decomposition

Résumé technique : Apprendre à couper : Apprentissage par renforcement pour la décomposition de Benders

Énoncé du problème
La décomposition de Benders (DB) est une approche standard pour résoudre des programmes stochastiques à deux étapes, qui modélisent la prise de décision dans l'incertitude en séparant les décisions de première étape « ici et maintenant » des actions de seconde étape « attendre et voir ». Bien qu'efficace, la DB classique souffre souvent d'une convergence lente. Cette inefficacité découle d'un compromis dans la gestion des coupes : l'ajout de toutes les coupes par scénario (formulation multi-coupes) crée une approximation plus serrée de la fonction de recours mais agrandit considérablement le problème maître, ralentissant les résolutions ultérieures ; inversement, l'agrégation des coupes en une seule coupe (formulation mono-coupe) maintient le problème maître petit mais produit des approximations plus faibles. Les approches heuristiques existantes, telles que la sélection des coupes les plus violées uniquement ou l'utilisation de coupes Pareto-optimales, tentent de gérer cela, mais elles reposent souvent sur des règles déterministes qui peuvent ne pas s'adapter correctement aux structures de problèmes variables ou aux entrées de données.

Méthodologie
Les auteurs proposent l'Apprentissage par renforcement pour la DB (RLBD), un cadre qui modélise la sélection de coupes comme un problème de prise de décision séquentielle au sein d'un processus de décision markovien (MDP) à horizon fini et à facteur d'actualisation.

• Formulation MDP :

  • Espace d'états ($S$) : L'état à chaque itération $t$ capture à la fois les statistiques de convergence globale (indice d'itération, bornes inférieure/supérieure, écart d'optimalité, taux de réduction de l'écart, et temps de résolution du problème maître/sous-problème) et les caractéristiques locales des coupes. Les caractéristiques locales pour chaque coupe candidate incluent les niveaux de violation, les normes des variables duales, les coefficients de coupe, et la fréquence historique des coupes générées par le même scénario.
  • Espace d'actions ($A$) : L'action consiste à sélectionner un sous-ensemble de $K$ coupes candidates parmi les coupes par scénario disponibles à ajouter au problème maître.
  • Fonction de récompense ($r$) : La récompense est une somme pondérée de trois composantes : (1) un terme basé sur l'écart reflétant la réduction logarithmique de l'écart d'optimalité (encourageant la convergence), (2) un terme négatif proportionnel au temps de résolution du problème maître (encourageant l'efficacité), et (3) une pénalité par étape (encourageant des trajectoires plus courtes).
  • Dynamiques de transition : L'environnement passe à l'état suivant en résolvant le problème maître mis à jour avec les coupes sélectionnées, en générant de nouveaux sous-problèmes, et en calculant de nouvelles bornes et statistiques.

• Paramétrisation de la politique et entraînement :

  • La politique de sélection de coupes $\pi_\theta$ est paramétrée par un réseau de neurones feedforward partagé. Le réseau traite un vecteur concaténé d'informations d'état global et de caractéristiques locales de coupe pour chaque coupe candidate, produisant un logit scalaire. Une fonction softmax convertit ces logits en une distribution de probabilité.
  • La politique est entraînée à l'aide de l'algorithme REINFORCE (une méthode de gradient de politique). Au cours des épisodes d'entraînement, l'agent échantillonne une séquence de $K$ coupes sans remise selon la distribution de la politique actuelle. Les paramètres de la politique sont mis à jour par ascent de gradient pour maximiser la récompense cumulée actualisée attendue.
  • Inférence : Pendant les tests, la politique entraînée est appliquée de manière gourmande, sélectionnant les $K$ meilleures coupes ayant les logits les plus élevés pour chaque nouvelle instance de problème.

Contributions clés

1. Politique stochastique de sélection de coupes : Contrairement aux heuristiques déterministes, RLBD emploie une politique stochastique qui attribue des probabilités de sélection basées à la fois sur la progression algorithmique globale et les caractéristiques locales des coupes. Cela permet à l'agent d'exploiter des coupes informatives tout en maintenant la capacité d'explorer des candidats alternatifs qui pourraient devenir critiques plus tard.
2. Capacité de généralisation : Le cadre est conçu pour se généraliser à des problèmes ayant des structures similaires mais des entrées de données variables (par exemple, différentes réalisations de la demande) et des dimensions de variables de décision (par exemple, différents nombres d'installations ou de clients), sans réentraînement.
3. Améliorations des performances : L'approche démontre des améliorations substantielles par rapport aux références existantes, incluant la DB standard et LearnBD (une approche d'apprentissage supervisé utilisant des machines à vecteurs de support).

Résultats expérimentaux
Les auteurs ont évalué RLBD sur un problème de localisation de stations de recharge pour véhicules électriques (VE) stochastique à deux étapes. Les expériences ont impliqué un entraînement sur une instance spécifique et des tests sur des instances avec des tailles de problèmes variables ($8\times12$, $10\times15$, $20\times30$) et des distributions de demande (Normale, asymétrique à gauche, et asymétrique à droite).

• Petites à moyennes instances : Pour les instances avec les configurations $8\times12$ et $10\times15$, RLBD a atteint une réduction du temps de calcul d'environ cinq fois par rapport à la DB standard et LearnBD, tout en maintenant des écarts d'optimalité comparables. Ce gain d'efficacité a été principalement attribué à la sélection adaptative des coupes, qui a résulté en des temps de résolution du problème maître significativement plus courts.
• Grandes instances : Pour les plus grandes instances ($20\times30$) où toutes les méthodes ont échoué à converger dans la limite d'une heure, RLBD a atteint un écart d'optimalité final plus faible (environ 28–29 %) par rapport aux références (environ 35–39 %).
• Sensibilité aux hyperparamètres : L'étude a identifié qu'un poids de récompense de $\alpha=0,01$ (réduction de l'écart) et $\lambda=0,001$ (pénalité par étape), combiné à l'ajout de $K=10$ coupes par itération, a produit la convergence et l'efficacité les plus stables.
• Insights managériaux : L'analyse de la politique apprise a révélé qu'elle tend à privilégier les coupes provenant de scénarios avec une demande totale plus élevée, une exposition aux pénalités et une exposition aux revenus, suggérant que le modèle identifie avec succès les réalisations à forte charge comme critiques pour resserrer la formulation.

Signification et affirmations
L'article affirme que RLBD offre une alternative robuste et adaptative aux stratégies traditionnelles de gestion des coupes. En présentant la sélection de coupes comme un problème d'apprentissage, la méthode surmonte la rigidité des heuristiques déterministes. Les auteurs soulignent que la politique entraînée présente une forte généralisation, gérant efficacement les décalages de distribution et les changements de dimensions de problème sans nécessiter de réentraînement. Les résultats suggèrent que l'intégration de l'apprentissage par renforcement dans la boucle de la DB peut améliorer considérablement l'efficacité computationnelle des programmes stochastiques à deux étapes, en particulier dans les scénarios où la taille du problème maître devient un goulot d'étranglement. Le travail positionne RLBD comme une méthode viable pour améliorer l'évolutivité de l'optimisation stochastique dans des applications réelles telles que la localisation d'installations et la gestion de la chaîne d'approvisionnement.