Laboratoire Quosséça

Vous êtes ici

Contactez-nous

Téléphone
(514) 340-4711 poste 4142

Télécopieur
(514) 340-5139

Local
M-3409

Courriel
gilles.pesant@polymtl.ca

Thèmes de recherche

Inférence

Comme bien d'autres méthodes computationnelles pour la résolution de problèmes combinatoires, la programmation par contraintes exprime le problème à l'aide d'un modèle mathématique. Contrairement à elles cependant, le langage de modélisation présente des primitives de haut niveau qui mettent au grand jour une part importante de la structure combinatoire du problème. On sacrifie ici une syntaxe simple qui favorise la conception de solveurs monolithiques optimisés, mais en contrepartie on gagne une sémantique riche qui peut être, et a été, exploitée pour l'inférence et l'exploration de l'espace de recherche des solutions. L'atout principal et distinctif de la programmation par contraintes continue d'être cet accès direct à la structure du problème.

Cette structure est principalement exprimée par les contraintes individuelles dans le modèle. Chacune peut représenter des aspects importants du problème tels que l'identification d'un cycle hamiltonien dans un graphe, le placement d'items dans des boîtes ou l'ordonnancement de tâches consommant une ressource cumulative. En programmation par contraintes il est courant que quelques contraintes seulement suffisent pour modéliser un problème combinatoire complexe. Chaque famille de contraintes encapsule des algorithmes de filtrage spécialisés qui agissent sur le domaine des variables en retirant des valeurs incohérentes, réduisant ainsi l'espace de recherche.

Les publications pertinentes sont identifiées par #filtering

Exploration de l'espace de recherche

L'espace de recherche est exploré par décomposition de problème, bâtissant un arbre de recherche dont les branches issues d'un noeud correspondent aux décisions qui partitionnent l'espace courant. Ces décisions pourraient être des contraintes générales qu'on ajoute au modèle pour ce sous-arbre mais typiquement elles fixent une variable à une valeur dans son domaine dans la branche de gauche et retirent cette valeur du domaine dans la branche de droite. Les heuristiques de branchement guident comment l'arbre de recherche sera développé.

La conception d'une heuristique de branchement générique et robuste est un sujet de recherche important. Les heuristiques basées sur le dénombrement ("Counting-Based Search" ou CBS) privilégient les décisions de branchement qui préservent la plupart des solutions en déterminant la proportion des solutions à chaque contrainte qui s'accordent avec une décision donnée. Tandis que la majorité des heuristiques de branchement génériques en programmation par contraintes s'appuient sur de l'information locale aux variables individuelles, CBS exploite de l'information plus globale au niveau des contraintes. Cette approche est aussi valide pour la résolution de problèmes d'optimisation combinatoire: nous évaluerons alors la proportion de solutions quasi-optimales.

Les publications pertinentes sont identifiées par #CBS

Le problème de coordination entre agents autonomes dans un environnement de chaîne d'approvisionnement peut être exprimé comme une exploration adaptative distribuée d'un arbre de recherche.

Les publications pertinentes sont identifiées par #distrib

Contraintes molles

En pratique, bien des problèmes sont sur-contraints. En programmation par contraintes nous recherchons des solutions réalisables. Conséquemment nous ne pouvons pas l'appliquer directement à de tels problèmes parce que nous ne trouverions pas de solution. Le fait de permettre à nos modèles de qualifier les contraintes de dures ou molles, ces dernières pouvant possiblement être violées, rétablit la réalisabilité mais nous souhaitons quand même une exploitation proactive de ces contraintes molles afin de réduire l'espace de recherche. Nous avons proposé des algorithmes de filtrage paramétrisés par le niveau de violation permis pour une contrainte.

Les publications pertinentes sont identifiées par #soft

Méthodes hybrides

Un nombre grandissant d'applications de la programmation par contraintes procèdent en l'hybridant avec d'autres approches. Au fil des ans, nous avons étudié des hybridations avec des approches complémentaires telles que la recherche locale, la génération de colonnes, la programmation en nombres entiers et la décomposition de Benders.

Les publications pertinentes sont identifiées par #hybrid

Horaires de travail

La planification d'horaires de travail est un domaine d'application classique de la programmation par contraintes et nous avons travaillé sur divers aspects tels que la confection d'horaires cycliques ou personnalisés sur un horizon de planification allant de quelques semaines à quelques mois, la construction de quarts de travail et l'équilibre de la charge de travail parmi les employés.

Les publications pertinentes sont identifiées par #rostering

Soins de santé

Nous avons appliqué la programmation par contraintes à des problèmes de gestion des soins de santé, incluant la confection des horaires de médecins et de personnel infirmier, la planification de l'utilisation des salles d'opération et l'équilibre de la charge de travail du personnel infirmier.

Les publications pertinentes sont identifiées par #health

Foresterie

L'exploitation forestière est un secteur très important de l'économie canadienne. Nous avons travaillé à la planification des chemins forestiers, des trajets de camions de transport du bois et des opérations des moulins à scie.

Les publications pertinentes sont identifiées par #forestry

Test des systèmes logiciels/matériels

Les systèmes logiciels et embarqués sont de plus en plus complexes alors que les délais de mise en marché raccourcissent. La vérification de ces systèmes est une tâche laborieuse. Nous avons travaillé à la génération de cas de test pour les logiciels ainsi que sur la vérification des métriques de performance pour des systèmes multiprocesseurs sur puce (MPSoC).

Les publications pertinentes sont identifiées par #verif