| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [22 references]
https://hal.inria.fr/inria-00085801
Contributor : Laurent Henocque Connect in order to contact the contributor
Submitted on : Friday, July 14, 2006 - 1:54:39 PM
Last modification on : Wednesday, April 27, 2022 - 4:11:23 AM
Long-term archiving on: : Monday, April 5, 2010 - 10:03:45 PM
Contributor : Laurent Henocque Connect in order to contact the contributor
Submitted on : Friday, July 14, 2006 - 1:54:39 PM
Last modification on : Wednesday, April 27, 2022 - 4:11:23 AM
Long-term archiving on: : Monday, April 5, 2010 - 10:03:45 PM