La Programmation Linéaire
De nombreux problèmes d’optimisation de ressources peuvent se résumer à la maximisation d’une fonction linéaire sous contraintes linéaires.
Max Z = ∑i Xi
Xi ≥ 0
Pour tout j, ∑j AijXi ≤Bj
La Programmation Linéaire est une approche aujourd’hui très éprouvée pour résoudre des problèmes d’optimisation linéaire de grande taille (plusieurs centaines de milliers ou millions d’inconnues). Elle trouve ses premiers fondements dans les travaux du mathématicien Fourier, mais doit son avènement à George Dantzig qui met au point la méthode du Simplexe dans les années 1940.
Depuis lors, et stimulée par l’apparition de plates-formes de calcul de plus en plus puissantes, cette approche fait l’objet d’une activité de recherche très dynamique dont bénéficient aujourd’hui les solveurs commerciaux de renommée mondiale (ILOG-CPLEX, FICO-XPRESS-MP, GUROBI), mais aussi et de plus en plus des produits libres tels que COIN ou GLPK.
Beaucoup d’applications industrielles de la Programmation Linéaire existent aujourd’hui dans les domaines pétrolier, agro-alimentaire, l’industrie lourde et manufacturière, mais aussi dans les services, le transport et le domaine finance/assurance.
Pour résoudre des problèmes d’optimisation de ressources nécessitant l’utilisation de variables entières (variables exprimant des choix ou des nombres entiers), il a fallu mettre au point une approche mixte, mêlant le simplexe et une méthode de recherche arborescente dite méthode de Séparation et Evaluation ou Branch and Bound. Cette méthode est couramment complétée par des fonctions de réduction de domaine s’inspirant des techniques de Programmation par Contraintes ou de génération automatique de coupes. Ces améliorations permettent de réduire le domaine de recherche et de considérablement améliorer les performances des algorithmes. Toutes ces extensions sont présentes aujourd’hui dans les produits leaders du marché des solveurs linéaires.
La stabilité et la performance des algorithmes disponibles aujourd’hui conduit les équipes qui conçoivent des applications à base de Programmation Linéaire à traiter des problèmes de taille telle qu’il faut mettre en place des techniques de décomposition, de façon à rendre leur résolution compatible avec la mémoire disponible sur les ordinateurs, et à préserver des temps de calcul acceptables pour les utilisateurs. On peut citer en particulier la Génération de Colonnes, permettant de ne pas traiter l’ensemble des variables d’un problème linéaire de façon explicite, et donc d’aborder des problèmes dont la taille devient potentiellement quasi infinie.
La Programmation Linéaire et ses extensions sont des technologies utilisées par EURODECISION depuis la création de la société, qui fait aujourd’hui figure de centre d’expertise dans le domaine. Elle a donné lieu au développement et au déploiement de nombreux projets chez nos clients, et joue un rôle-clé dans la conception de notre plate-forme de développement, et de la plupart de nos composants métiers. Notre plate-forme de développement LP-Toolkit/LP-Colgen permet de développer rapidement nos solutions à base de Programmation Mathématique et de les interfacer indifféremment avec tous les meilleurs solveurs existants, notamment :
- CPLEX (ILOG/IBM)
- XPRESS-MP (FICO)
- GUROBI
- COIN
- GLPK
- LP-SOLVE
Notre équipe assure en permanence une veille technologique sur les différents solveurs du marché et maintient ainsi une connaissance précise de leurs performances relatives.
