Génération de colonnes

Génération de colonnes

La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille[1]. Elle repose sur la décomposition de Dantzig-Wolfe (en), qui consiste à décomposer l'ensemble des contraintes en deux sous-ensembles.

L'idée centrale est que les programmes linéaires de grande taille ont trop de variables (ou colonnes) pour qu'on puisse les représenter toutes de manière explicite. A l'optimum, la plupart des variables sont hors base et, très souvent, la plupart d'entre elles sont nulles, c'est-à-dire que seul un (petit) sous-ensemble de variables doit être pris en compte pour résoudre le problème.

Une méthode utilisant la génération de colonnes initialise le programme linéaire avec un sous-ensemble de colonnes de petite taille. Le mécanisme de la génération de colonnes consiste alors à générer, au sein d'un algorithme à plusieurs étapes, les variables qui sont susceptibles d'améliorer la solution courante, c'est-à-dire celles qui ont des coûts réduits négatifs.

L'efficacité de la méthode est très dépendante du mécanisme utilisé pour générer des colonnes. En effet, le sous-problème à résoudre est souvent NP-difficile.

Les méthodes utilisant la génération de colonnes ont souvent des problèmes de convergence dus au fait que le problème dual est très peu contraint au début de la méthode. En pratique, ces problèmes vont amener la méthode à effectuer un grand nombre d'itérations qui ne permettent plus d'améliorer la solution courante.

Problèmes traités efficacement par la génération de colonnes

Notes et références

  1. ↑ (en) Guy Desaulniers, Jacques Desrosiers et Marius M. Solomon, Column Generation, Springer-Verlag New York Inc, 19 mai 2005, 358 p. (ISBN 0387254854) 
  2. ↑ (en) Roberto Baldacci et Aristide Mingozzi, « A unified exact method for solving different classes of vehicle routing problems », dans Mathematical Programming (en), vol. 120, no 2, septembre 2009, p. 347-380 (ISSN 0025-5610) [lien DOI] 

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Génération de colonnes de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Generation de colonnes — Génération de colonnes La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille. Elle repose sur la décomposition de Dantzig et Wolfe, qui consiste à décomposer l ensemble des contraintes en… …   Wikipédia en Français

  • Génération De Colonnes — La génération de colonnes est une méthode pour résoudre efficacement les programmes linéaires de grande taille. Elle repose sur la décomposition de Dantzig et Wolfe, qui consiste à décomposer l ensemble des contraintes en deux sous ensembles. L… …   Wikipédia en Français

  • Generation — Génération Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Génération — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Génération », sur le Wiktionnaire (dictionnaire universel) Le mot génération désigne l action d… …   Wikipédia en Français

  • Vieille génération — Génération Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Crise générationnelle — Génération Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Optimisation linéaire — En optimisation, qui est une branche des mathématiques, un problème d optimisation linéaire est un problème d optimisation dans lequel on minimise une fonction linéaire sur un polyèdre convexe. La fonction coût et les contraintes peuvent donc… …   Wikipédia en Français

  • Branch and price — est une méthode d optimisation combinatoire pour résoudre des problèmes d optimisation linéaire en nombres entiers. Cette méthode combine l algorithme du branch and bound classique avec une génération de colonnes à chaque nœud de l arbre.… …   Wikipédia en Français

  • PLNE — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… …   Wikipédia en Français

  • Programmation lineaire — Programmation linéaire En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”