Skip to Main content Skip to Navigation
Conference papers

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}.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00151189
Contributor : Sylvain Soliman <>
Submitted on : Friday, June 1, 2007 - 5:10:34 PM
Last modification on : Monday, July 16, 2018 - 3:42:06 PM
Long-term archiving on: : Thursday, April 8, 2010 - 6:43:37 PM

File

55.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00151189⟩

Share

Metrics

Record views

204

Files downloads

137