Algorithmique et Optimisation Combinatoire

La quantité de données numériques disponibles offre des opportunités pour améliorer la prise de décision notamment afin d’optimiser le flux et la planification de ressources et de tâches comme ciblé par la recherche opérationnelle mais aussi par exemple, la planification de calculs sur des infrastructures distribuées et hétérogènes.

La quantité de variables et contraintes à prendre en compte ainsi que la rapidité à laquelle les prises de décision doivent être effectuées influencent les types d’approches d’optimisation combinatoire envisageables. Dans certains cas où l’optimalité est exigée mais le facteur temps n’est pas primordial, la programmation par contrainte proposera une solution adéquate. Quand la situation impose des recalculer fréquemment (toutes les heures ou quelques minutes) et que la garantie de l’optimalité n’est pas obligatoire, les stratégies par recherche locale sont des solutions de choix.

Afin d’aider ses partenaires entreprises en ce qui concerne la prise décisions sur des problèmes avec un espace de solution combinatoire, le CETIC développe un moteur d’optimisation par recherche locale (OscaR.cbls), en partenariat avec l’UCLouvain qui implémente le moteur de programmation par contrainte (OscaR.cp). Ces moteurs sont implémentés de manière modulaire afin de rester très flexibles et ainsi de pouvoir s’adapter facilement à de nouvelles variables et contraintes rencontrées dans divers domaines d’application allant du transport et logistique à la santé, l’industrie 4.0 ou l’énergie. OscaR est distribué sous licence open source.

Facilité par l’expertise existante en optimisation combinatoire, le CETIC développe aussi de sérieuses compétences en algorithmique combinatoire. Des heuristiques bien choisies permettent de réduire de manière significative le temps de calculs d’algorithmes complexes pour des problèmes de calculs de parcours devant prendre en compte diverses contraintes liées à la cartographie, l’énergie, le trafic mais aussi dans des domaines d’ingénierie logicielle tels que la génération de jeux de tests, des techniques de vérifications explorées par les méthodes formelles.

La vision recherche et innovation poursuivie par les projets de recherche du CETIC se focalise sur les améliorations au moteur d’optimisation OscaR.cbls ainsi que sur ses applications sur de nouveaux problèmes de routage dans le domaine du transport et de la logistique, la planification pour les contextes de l’industrie manufacturière et de l’énergie. Des solutions sont aussi explorées sur des problèmes d’optimisation de positionnement spatial.