La PPC est surtout connue pour la résolution de problèmes discrets. Cependant, elle peut se révéler efficace pour résoudre aussi des problèmes continus (dont les domaines sont des intervalles continus représentés par deux flottants). Cette modélisation peut être utile notamment pour les problèmes non linéaires. La PPC utilisé avec des domaines continus permet de résoudre des problèmes MINLP (à la fois discret sur une partie et non linéaire sur le reste). Dans ce cas la PPC se base sur l’arithmétique d’intervalles.

Il n’est évidement pas concevable de considérer toutes les valeurs de chaque domaine continu de chaque variable une à une. Un domaine continu est considérer comme un intervalle entre deux flottants. Un flottant z est représenté par deux entiers x et y tels que z = x * 10^y avec x > 0 et x < 10 (x et y ont une précision fixée). Dès lors, comment faire une recherche efficace car prendre les valeurs une à une devient impossible ? On va utilisé une recherche dichotomique :

Tant qu’il existe une domaine x plus grand que €,
On essaie d’affecter x à [ inf( x ), inf( x ) + ( sup( x ) – inf( x ) ) / 2 ]
Si ca échoue, on essaie [ inf( x ) + ( sup( x ) – inf( x ) ) / 2, sup( x ) ]

Il devient alors possible de résoudre des problèmes hybrides en utilisant deux branchements (un entier et un continu). On commence par l’un des domaines et quand on n’a plus de choix à prendre on passe au second.

Le filtrage en continu utilise des notions d'arithmétiques que nous ne détaillerons pas plus ici.

 

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.