Skip to content
Retour aux résultats

Décomposition de Benders

Introduite par
Jacques F. Benders
Année
1962
Type
algorithm
Famille
Optimization

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

La Décomposition de Benders, introduite par Jacques F. Benders en 1962, est un cadre algorithmique puissant pour résoudre des problèmes de programmation mixte en nombres entiers (MIP) à grande échelle.

Elle décompose le problème en un problème maître (contrôlant les variables complexes) et des sous-problèmes (gérant les variables restantes), en utilisant des plans coupants générés à partir des informations duales des sous-problèmes pour resserrer itérativement le problème maître.

L’intuition derrière la méthode

La méthode reconnaît que certaines variables (dites variables complexes) rendent le problème difficile à résoudre directement, tandis que les variables restantes peuvent être traitées facilement. En fixant les variables complexes et en résolvant le sous-problème résultant pour les variables restantes, l'algorithme obtient des informations duales qui génèrent des plans coupants. Ces coupures renforcent le problème maître, qui sélectionne alors de meilleures valeurs pour les variables complexes. Ce processus itératif se poursuit jusqu'à convergence. L'idée clé est que la décomposition transforme un problème difficile en de nombreux sous-problèmes plus faciles plus un problème maître plus petit.

Histoire

Benders a introduit sa méthode de décomposition en 1962 pour partitionner les problèmes de programmation mixte en nombres entiers. Geoffrion a généralisé l'approche en 1972 pour traiter les problèmes non linéaires, créant le cadre utilisé dans les applications modernes. La méthode a gagné en importance avec les avancées de la puissance de calcul et des solveurs. Les développements récents incluent les coupures combinatoires de Benders, les variantes multi-coupures et l'intégration avec les algorithmes modernes de branchement et coupure, en faisant une technique fondamentale en optimisation avancée.

Quand l’utiliser

Appliquer la Décomposition de Benders aux problèmes de programmation mixte en nombres entiers à grande échelle, en particulier ceux ayant une structure particulière (en escalier, bloc-angulaire) exploitable par décomposition. Elle est particulièrement efficace pour les problèmes où les méthodes de résolution directe sont prohibitivement coûteuses en calcul. L'utiliser pour des problèmes de localisation d'installations, de planification de production et de conception de réseaux. Pour les petits problèmes ou ceux sans structure particulière, les solveurs MIP directs peuvent être plus efficaces.

Limites et points d’attention

  • Nécessite une structure de problème amenable à la décomposition ; peut être inefficace sur des problèmes entièrement généraux
  • La génération de coupures peut créer de nombreuses contraintes, ralentissant potentiellement la résolution du problème maître
  • La convergence peut être lente, nécessitant de nombreuses itérations avec une tolérance serrée
  • Complexité de mise en œuvre supérieure aux méthodes de résolution directe
  • Problèmes possibles de stabilité numérique avec les coefficients des coupures

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Résout efficacement les programmes mixtes en nombres entiers à grande échelle qui sont intraitable par les méthodes standard
  • Exploite naturellement la structure du problème de forme bloc-angulaire ou en escalier
  • Fournit des bornes inférieures et supérieures, permettant des garanties de qualité avant convergence
  • La décomposition permet la résolution parallèle de sous-problèmes indépendants
  • La Décomposition Généralisée de Benders traite les sous-problèmes non linéaires, élargissant son applicabilité

Applications

  • Localisation d'installations : déterminer les emplacements d'entrepôts et l'allocation de produits pour minimiser le coût total
  • Planification de production : ordonnancer la production entre les installations avec des contraintes de capacité et de stock
  • Routage de véhicules : planifier les itinéraires de livraison avec des décisions de composition de flotte
  • Conception de réseaux : sélectionner les installations, les liens et les capacités dans les réseaux de télécommunications ou de transport
  • Systèmes électriques : décisions de dispatch économique et d'engagement des unités avec des contraintes de transmission
  • Optimisation de la chaîne d'approvisionnement : coordonner l'approvisionnement, la production et la distribution à travers les réseaux

Comment ça marche

Comment ça marche

1

Mettre en place le problème maître avec uniquement les variables complexes et des contraintes de substitution. Initialiser les bornes supérieure et inférieure ; borne inférieure issue du problème maître, borne supérieure issue de solutions réalisables.

2

Fixer les variables complexes à leurs valeurs actuelles et résoudre le sous-problème pour les variables restantes. Si le sous-problème est infaisable, générer une coupure de faisabilité ; s'il est réalisable, extraire les informations duales et générer une coupure d'optimalité.

3

Ajouter des coupures au problème maître reflétant les aperçus du sous-problème. Résoudre à nouveau le problème maître et répéter jusqu'à ce que l'écart entre les bornes supérieure et inférieure soit acceptable.

Pièges courants

  • Sélection de mauvais choix pour les variables complexes, résultant en des sous-problèmes difficiles
  • Échec de la mise en œuvre de techniques de stabilisation (région de confiance, méthodes de niveau) pour accélérer la convergence
  • Génération de coupures faibles qui ne renforcent pas suffisamment le problème maître
  • Ignorer le pré-traitement et les démarrages à chaud à partir de solutions réalisables

Questions fréquentes

Quelles sont les variables complexes et comment les identifier ?

Les variables complexes sont celles dont les valeurs, une fois fixées, rendent le problème restant facile à résoudre. Elles sont identifiées en examinant la structure du problème : les variables apparaissant dans des contraintes couplant des sous-problèmes autrement indépendants, ou les variables discrètes dans des problèmes autrement continus, sont des candidats courants.

Quelle est la différence entre les coupures de faisabilité et les coupures d'optimalité ?

Les coupures de faisabilité sont générées lorsqu'un sous-problème est infaisable, éliminant les valeurs infaisables des variables complexes du problème maître. Les coupures d'optimalité incorporent les informations duales des sous-problèmes réalisables pour améliorer les estimations objectives du problème maître.

Comment la Décomposition de Benders garantit-elle la convergence ?

Les coupures de faisabilité et d'optimalité garantissent que la relaxation du problème maître fournit des bornes inférieures valides. Les bornes supérieures proviennent de solutions réalisables du problème complet. Lorsque les bornes convergent dans la tolérance spécifiée, l'optimalité est garantie. La convergence est finie pour les problèmes entiers bornés.

Quand la Décomposition de Benders est-elle préférable à la résolution directe du problème avec un solveur MIP ?

La Décomposition de Benders est préférable lorsque le problème est de grande taille, possède une structure particulière exploitable par décomposition, ou que les solveurs directs dépassent le temps imparti. Pour les petits problèmes ou ceux manquant de structure, les solveurs MIP modernes sont souvent plus rapides et plus simples.

Méthodes associées

Sources

  1. Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238-252.

    Ouvrir la référence DOI
    Copié.
  2. Geoffrion, A. M. (1972). Generalized Benders decomposition. Journal of Optimization Theory and Applications, 10(4), 237-260.

    Ouvrir la référence DOI
    Copié.