Skip to Main content Skip to Navigation
Conference papers

Calcul d'approximations intérieures pour la résolution de Max-NCSP

Résumé : Cet article présente un algorithme de calcul de solutions garanties pour des problèmes numériques MaxCSP. Les auteurs proposent une approche qui offre une exploration complète et garantie de l'espace de recherche et identifie l'ensemble des sous-espaces éventuellement disjoints qui satisfont le plus grand nombre de contraintes numériques du CSP. L'implémentation de cet algorithme fournit une approximation intérieure de ces sous-ensembles pour une taille minimale de pavé donnée. L'approche repose sur des méthodes de propagation classiques sur les intervalles (AC-3) et sur un processus d'extension par l'intérieur en n dimensions. Une hybridation avec des méthodes locales de recherche, étendues aux intervalles, est proposée et testée. Les résultats, portant sur des problèmes jouets montrent l'apport par rapport à un algorithme na¨ıf mais ne mettent pas en lumière l'évidence de la contribution des méthodes de recherche locale.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00085801
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 1:54:39 PM
Last modification on : Friday, November 20, 2020 - 4:56:02 PM
Long-term archiving on: : Monday, April 5, 2010 - 10:03:45 PM

File

Identifiers

  • HAL Id : inria-00085801, version 1

Collections

Citation

Marc Christie, Jean-Marie Normand, Charlotte Truchet. Calcul d'approximations intérieures pour la résolution de Max-NCSP. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France. ⟨inria-00085801⟩

Share

Metrics

Record views

638

Files downloads

574