CID : Disjonction Constructive sur Intervalles

Gilles Trombettoni 1 Gilles Chabert 1
1 COPRIN - Constraints solving, optimization and robust interval analysis
CRISAM - Inria Sophia Antipolis - Méditerranée , ENPC - École des Ponts ParisTech
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}.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07
Liste complète des métadonnées


https://hal.inria.fr/inria-00151189
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 17:10:34
Dernière modification le : mercredi 15 avril 2015 - 16:08:30
Document(s) archivé(s) le : jeudi 8 avril 2010 - 18:43:37

Fichier

55.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00151189, version 1

Collections

Citation

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, 2007, JFPC07. <inria-00151189>

Partager

Métriques

Consultations de
la notice

125

Téléchargements du document

85