Centre de Recherche en Informatique de Lens

Le séminaire portera sur des méthodes qui exploitent des techniques de la Programmation Par Contraintes (PPC) et de la Programmation Mathématique (PM) pour modéliser et résoudre des systèmes de contraintes.

Dans le cadre de la satisfaction (CSP), je vous présenterai une formulation compacte en programmation linéaire (O(nd) variables 0-1 et O(nd) inégalités linéaires) pour les CSP binaires ; je montrerai comment exploiter cette formulation pour établir un lien entre la consistance d’arc (concept très utilisé en PPC) et la relaxation Lagrangienne (concept très utilisé en PM) et je présenterai une méthode de filtrage combinant ces deux concepts.

Dans le cadre des Max-CSP et WCSP je parlerai de modélisations basées sur les notions de clique et d’inégalité valide. Je vous présenterai plusieurs formulations linéaires à variables 0-1 ; des liens entre la relaxation continue et la consistance d’arc ; une méthode de recherche locale à base de cliques pour le calcul de bornes inférieures et une technique de prétraitement exploitant la Programmation Linéaire.

Des expérimentations seront également présentées.