Skip to Main content Skip to Navigation
Conference papers

Une Stratégie de Résolution Orientée par la Topologie des CSPs Numériques

Heikel Batnini 1 Michel Rueher 1 Claude Michel 1
1 COPRIN - Constraints solving, optimization and robust interval analysis
CRISAM - Inria Sophia Antipolis - Méditerranée , ENPC - École des Ponts ParisTech
Résumé : Les méthodes classiques de résolution de CSPs numériques sont basées sur un algorithme combinant une technique de bissection et un filtrage par consistance locale. En général, le filtrage est basé sur la Hull-consistance ou la Box-consistance. Les algorithmes de filtrage correspondants identifient souvent des trous dans les domaines, c'est-à-dire des intervalles sur lesquels certaines contraintes ne sont pas satisfaites. Ces trous sont cependant utilisés uniquement pour déterminer le plus petit intervalle englobant les solutions. Ce papier présente une stratégie de recherche, nommée TopSearch (Topological Search), qui exploite les trous identifiés par ces filtrages. TopSearch utilise ces informations pour sélectionner la direction de coupe ainsi que pour définir le point de coupe dans le domaine sélectionné. Si aucun trou n'est identifié une bissection standard est mise en oeuvre. Les premiers résultats expérimentaux montrent que cette heuristique de recherche dont le sur-coût est minime, peut améliorer de manière très significative les performances de la bissection classique.
Complete list of metadata

https://hal.inria.fr/inria-00000087
Contributor : Christine Solnon <>
Submitted on : Thursday, May 26, 2005 - 2:22:49 PM
Last modification on : Thursday, April 5, 2018 - 10:55:37 AM
Long-term archiving on: : Thursday, April 1, 2010 - 9:34:34 PM

Files

Identifiers

  • HAL Id : inria-00000087, version 1

Collections

Citation

Heikel Batnini, Michel Rueher, Claude Michel. Une Stratégie de Résolution Orientée par la Topologie des CSPs Numériques. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, pp.211-218. ⟨inria-00000087⟩

Share

Metrics

Record views

166

Files downloads

111