Génération de colonnes

La technologie de base dont nous nous servons pour produire des solutions en planification du monde réel est la génération de colonnes. GENCOL (GÉNération de COLonnes) renferme les principes de la méthode de génération de colonnes, développée pour résoudre des problèmes complexes à grande échelle. La génération de colonnes est une stratégie d'optimisation qui permet de tenir compte implicitement d'un grand nombre de variables à l'aide d'une composante mathématique appelée le générateur.

Le générateur de colonnes (ou sous-problème) partage l'information avec ce qui est habituellement appelé le problème maître et, avec ces composantes, élève l'optimisation à l'optimalité. De concert avec d'autres algorithmes d'optimisation robustes, l'optimiseur GENCOL offre des avantages non négligeables sur les plans économiques et humains.

Technologie primée

Produit des recherches de Jacques Desrosiers et de François Soumis, GENCOL et ses chercheurs ont reçu plusieurs prix prestigieux, dont celui de la Société Canadienne de Recherche Opérationnelle (en 1994 et 1996), de l'Operational Research Society of America (en 1986) et de l'European Association of Operational Research (en 1983).

Programmation dynamique

Notre générateur de colonnes a été fondé sur un algorithme du plus court chemin avec des contraintes de ressources. Ce type d'outil mathématique est très puissant et difficile à maîtriser. La maîtrise de la puissance de cet outil est indéniablement l'une des forces des solutions d'AD OPT.

Cplex, ACCPM

Notre composante principale est générique et permet à AD OPT d'utiliser divers moteurs pour produire l'information en double dont le générateur a besoin. Dans plusieurs cas, nous utilisons les moteurs Cplex, mais aussi les heuristiques. Nous travaillons actuellement en collaboration avec le GERAD sur un optimiseur conçu spécialement pour la génération de colonnes.

Branchement par séparation et évaluation progressive

Étant donné que la génération de colonnes ne produit pas de solutions entières, nous avons développé une approche de branchement par séparation et évaluation progressive qui encapsule notre algorithme de génération de colonnes. Cette approche définit une interface à des « méthodes » de branchement qui se font concurrence pour rendre des solutions fractionnaires plus entières. Chaque méthode évalue ce qu'elle peut faire pour un problème relaxé donné, et la plus efficace est utilisée pour modifier le problème. Plusieurs stratégies de recherche sont offertes et nous avons démontré notre grande innovation dans ce domaine.

Moteur unifié de logique opérationnelle

Le moteur unifié de logique opérationnelle, BLUE (Business Logic Unified Engine) est l'un des plus récents développements en recherche opérationnelle. Basé sur un interpréteur efficace de la famille de langages LISP programmé à l'interne, le moteur de règles BLUE joue déjà un rôle important dans l'évaluation des soumissions et des horaires, et même dans la création d'horaires dans Altitude PBS.

Plus qu'un simple moteur de règles, Altitude BLUE nous permet de faire un pas de plus dans l'évolution de nos produits en optimisation, d'un environnement paramétré à un environnement de programmation fonctionnelle. Apprenez-en davantage sur BLUE.