Génération de colonnes (Dantzig-Wolfe)
- Introduite par
- George B. Dantzig and Philip Wolfe
- Année
- 1960
- Type
- algorithm
- Famille
- Optimization
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
La génération de colonnes, développée par George B. Dantzig et Philip Wolfe en 1960, est une technique d'optimisation puissante pour résoudre des problèmes de programmation linéaire à grande échelle avec une structure particulière.
Également connue sous le nom de décomposition de Dantzig-Wolfe, elle décompose le problème en un problème maître (restreint à un sous-ensemble de variables/colonnes) et un sous-problème de tarification (identifiant de nouvelles variables), améliorant itérativement la solution en introduisant uniquement les colonnes pertinentes.
L’intuition derrière la méthode
La méthode reconnaît que de nombreux problèmes d'optimisation de grande taille ont une structure particulière : de nombreuses variables mais peu de contraintes réellement importantes, ou des sous-problèmes naturellement décomposables. Au lieu de résoudre le problème complet avec toutes les variables possibles, la génération de colonnes ne maintient qu'un petit sous-ensemble de colonnes (variables) prometteuses. Le problème de tarification, résolu à l'aide des coûts réduits et de la structure du problème, identifie de nouvelles colonnes qui améliorent la solution maître. En ajoutant itérativement les colonnes les plus prometteuses, l'algorithme construit une solution efficacement, évitant ainsi la charge computationnelle liée à la manipulation de toutes les colonnes simultanément.
Histoire
Dantzig et Wolfe ont introduit le principe de décomposition pour les programmes linéaires en 1960, établissant les fondements théoriques. Gilmore et Gomory (1961) l'ont appliqué au problème de la découpe, démontrant sa puissance pratique. La méthode a gagné en importance pour les problèmes de tournées de véhicules et de planification dans les années 1980-90. L'intégration avec la méthode de séparation et évaluation, créant des algorithmes branch-and-price, a élargi son applicabilité à la programmation entière. Les applications modernes incluent la planification d'équipage de compagnies aériennes, le routage de navires et l'optimisation logistique à grande échelle.
Quand l’utiliser
Appliquer la génération de colonnes lors de la résolution de programmes linéaires à grande échelle avec une structure particulière, en particulier lorsque le nombre de variables est énorme mais qu'un petit sous-ensemble domine la solution optimale. Elle est idéale pour les problèmes de découpe, de tournées de véhicules, de planification d'équipage et de rangement dans des boîtes. L'utiliser lorsque la structure du problème permet une résolution efficace du sous-problème de tarification. Pour les problèmes sans structure exploitable ou de taille modérée, les solveurs PL standard sont plus pratiques.
Limites et points d’attention
- Nécessite une structure de problème permettant une solution efficace du sous-problème de tarification
- La convergence peut être lente, surtout près de l'optimalité (effet de queue)
- La solution du sous-problème de tarification doit être fiable et efficace, sinon les gains d'efficacité sont perdus
- Complexité de mise en œuvre supérieure aux méthodes PL standard
- Problèmes de stabilité numérique avec de grandes valeurs duales et des coûts réduits
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 des problèmes à grande échelle ingérables par les méthodes standard en raison de l'explosion des colonnes
- Exploite la structure du problème pour générer uniquement les colonnes pertinentes
- Fournit des bornes sur la qualité de la solution pendant l'itération
- Naturellement adaptée aux problèmes avec une sous-structure particulière (sous-problèmes identiques, symétrie)
- Intégrable avec la méthode de séparation et évaluation pour les programmes entiers (branch-and-price)
Applications
- Problème de découpe : minimiser le gaspillage lors de la coupe de matériaux aux dimensions requises
- Tournées de véhicules : optimiser les itinéraires de livraison et de transport avec des fenaces temporelles et des contraintes de capacité
- Planification d'équipage : affecter les membres d'équipage aux vols ou aux quarts en minimisant le coût total
- Rangement dans des boîtes (Bin packing) : emballer efficacement des objets dans des conteneurs pour minimiser le gaspillage et le nombre de conteneurs
- Établissement de plannings (Rostering) : planifier les travailleurs sur différents quarts en respectant les contraintes de disponibilité et de préférences
- Planification aérienne : planification des vols, affectation des équipages et coordination de la maintenance des aéronefs
Comment ça marche
Comment ça marche
Commencer avec un problème maître restreint contenant uniquement un sous-ensemble de colonnes nécessaires à une solution réalisable initiale.
Résoudre le dual du problème maître restreint actuel à l'aide du tableau simplex. Identifier les coûts réduits et mettre en place le sous-problème de tarification pour trouver les variables ayant un coût réduit négatif (pour la minimisation).
Résoudre le sous-problème de tarification en utilisant sa structure particulière. Si une nouvelle colonne avec un coût réduit négatif est trouvée, l'ajouter au problème maître et recommencer. Si aucune colonne améliorant la solution n'existe, la solution actuelle est optimale.
Pièges courants
- Sélection d'un algorithme de sous-problème de tarification inefficace, annulant les gains d'efficacité de la génération de colonnes
- Ne pas reconnaître une structure de problème susceptible de décomposition, entraînant de mauvaises performances
- Détection de convergence inadéquate ou tolérance trop stricte, entraînant des itérations inutiles
- Ne pas mettre en œuvre de techniques de stabilisation pour traiter l'effet de queue
Questions fréquentes
Qu'est-ce que le problème de tarification en génération de colonnes et comment est-il lié aux coûts réduits ?
Le problème de tarification identifie de nouvelles variables (colonnes) avec un coût réduit négatif qui améliorent la solution maître. Les valeurs de coût réduit proviennent du dual du problème maître restreint et guident la recherche dans le sous-problème de tarification.
Pourquoi la génération de colonnes est-elle meilleure que la résolution du problème complet avec toutes les colonnes ?
Dans de nombreux problèmes, le nombre de colonnes potentielles est exponentiel ou infini, ce qui rend impossible leur énumération complète. La génération de colonnes génère uniquement les colonnes nécessaires à la demande, réduisant considérablement la charge computationnelle.
Quel est l'effet de queue et comment peut-il être atténué ?
L'effet de queue se produit lorsque la génération de colonnes progresse lentement près de l'optimalité, générant de nombreuses colonnes avec une amélioration minimale. Les techniques de stabilisation (lissage dual, méthodes de région de confiance, stratégies de coupure) en réduisent l'impact.
Comment le branch-and-price étend-il la génération de colonnes à la programmation entière ?
Branch-and-price combines column generation with branch-and-bound: at each node, column generation solves the LP relaxation, and branching decisions further restrict the problem when LP solutions are fractional.
Méthodes associées
Sources
Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.
Ouvrir la référence DOICopié.Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859.
Ouvrir la référence DOICopié.