Stéphane Secouard (GREYC, Caen)

Il existe de nombreuses façons de modéliser des problèmes de faisabilité ou d’optimisation. Certaines modélisent le fait que le problème est réalisable (CSP), d’autre que le problème est réalisable malgré l’ajout de contrainte dynamique (QCSP), d’autre enfin donne un coût à chaque façon d’assigner les variables (VCSP), permettant par ce biais de modéliser des problèmes d’optimisation.

  • Nous définirons un nouveau modèle permettant d’exploiter simultanément la richesse de ces modèles : les QVCSP.
  • Nous verrons comment, en observant uniquement les propriétés sur les fonctions de coût, il est possible de donner la complexité associée aux problèmes qu’elles peuvent décrire.
  • Nous ferons une étude systématique du cas où les variables sont booléennes.