CID : Disjonction Constructive sur Intervalles - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

CID : Disjonction Constructive sur Intervalles

Résumé

Le ``rognage'' ({\it shaving}) et la disjonction constructive sont deux principes de réfutation utilisés en programmation par contraintes. Le rognage est utilisé pour calculer la propriété de {\it singleton} arc-cohérence sur les CSP en domaines finis et la 3B-cohérence sur les CSP numériques. Il est également au c{\oe}ur de l'algorithme SATZ~\cite{Chuminli97} pour montrer la satisfiabilité d'une formule booléenne. Si l'on considère les domaines comme des contraintes unaires disjonctives, on peut adapter la {\it disjonction constructive}, proposée par Van Hentenryck et al. dans les années 1990, pour produire un opérateur de filtrage du modèle classique (où le problème est vu comme une conjonction de contraintes). Un avantage sur le rognage est que les étapes de (sous-)filtrage exécutées durant la disjonction constructive sont mieux réutilisées. Pour traiter les CSP numériques (systèmes comportant des contraintes sur les réels et résolus par des techniques d'intervalles), cet article présente deux nouveaux opérateurs de filtrage, appelés {\tt CID} et {\tt 3BCID}, basés sur la disjonction constructive, et une nouvelle heuristique de bissection basée sur {\tt CID}. {\tt CID} est exclusivement basé sur la disjonction constructive alors que {\tt 3BCID} est un algorithme hybridant rognage et disjonction constructive. Pendant que l'opérateur de filtrage {\tt CID} établit la CID-cohérence, l'heuristique de bissection basée sur {\tt CID} est capable d'apprendre sans surcoût la prochaine variable à bissecter. Des expérimentations ont été menées sur 20 benchmarks. {\tt CID} and {\tt 3BCID} produisent sur plusieurs benchmarks des gains en performance d'un ou plusieurs ordres de grandeur par rapport à une stratégie standard. {\tt CID} se compare avantageusement par rapport à l'opérateur de {\tt 3B} tout en étant plus simple à implanter. Ces expérimentations suggèrent de fixer dans {\tt 3BCID} le paramètre lié à {\tt CID}, offrant ainsi en quelque sorte à l'utilisateur une variante prometteuse de l'opérateur {\tt 3B}.
Fichier principal
Vignette du fichier
55.pdf (222.17 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00151189 , version 1 (01-06-2007)

Identifiants

  • HAL Id : inria-00151189 , version 1

Citer

Gilles Trombettoni, Gilles Chabert. CID : Disjonction Constructive sur Intervalles. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France. ⟨inria-00151189⟩
83 Consultations
54 Téléchargements

Partager

Gmail Facebook X LinkedIn More