Cette introduction à la P.P.C. a été rédigée avec G. Rochart du Bouygues e-lab.

Les exemples sont issus de TDs "Programmation par contraintes et problèmes combinatoires" donnés en Février 2009 aux Etudiants du Département Informatique de Polytechnique avec David Savourey.

La programmation par contrainte (P.P.C.) est une technique mathématique qui permet la résolution de problèmes combinatoires. La PPC est :

• Complète : on énumère toutes les solutions (satisfaction) ou on cherche la meilleure (optimisation).
• Globale : on sait ce qui a été fait.
• Extensible : on peut ajouter de nouvelles contraintes.

La P.P.C n'est SURTOUT PAS :

• Une méthode magique
  • A priori, elle n'est pas meilleure que d’autres technologies (Programmation linéaire, programmation dynamique, Recherches Locales, etc...).
  • Tout dépend du type de problème !
    
    
• Une méthode « press button », du moins pour l’instant :-)
  • Nécessité de comprendre la technique.
  • Nécessité de s’investir dans la recherche.
    

Voici quelque exemple d'applications de la P.P.C. au Bouygues e-lab :

• Les plans de tables pour les conférences du groupe.
• La planification des Corps d’Etat Secondaires sur les chantiers de construction.
• La planification de personnel.
• La planification de campagnes marketing.
• Et des projets exploitants la technique
  • Planification de la publicités
  • Planification de « call-centers »
    

Voici le plan de cette présentation sur la programmation par contraintes

• Les notions de base :
  • Les C.S.P.
  • La Recherche / Propagation
    
    
• Quelques notions avancées :
• Les Contraintes Globales
• Le Continu
• Les Explications
  
  
• Quelques exemples pour utiliser la P.P.C. :
  • Les N-Reines
  • Send More Money
  • Le Sudoku
  • Le Kakuro
  • Picross

Cette page a été co-réalisée avec Guillaume Rochart, docteur en mathématiques dans mon équipe de recherche au Bouygues e-lab.10/03/2009.