Harnessing tractability in constraint satisfaction problems

Clément Carbonnel 1
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
Abstract : The Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the past decades due to its practical usefulness and the deep theoretical questions it relates to. However, there is a wide gap between practitioners, who develop solving techniques that are efficient for industrial instances but exponential in the worst case, and theorists who design sophisticated polynomial-time algorithms for restrictions of CSP defined by certain algebraic properties. In this thesis we attempt to bridge this gap by providing polynomial-time algorithms to test for membership in a selection of major tractable classes. Even if the instance does not belong to one of these classes, we investigate the possibility of decomposing efficiently a CSP instance into tractable subproblems through the lens of parameterized complexity. Finally, we propose a general framework to adapt the concept of kernelization, central to parameterized complexity but hitherto rarely used in practice, to the context of constraint reasoning. Preliminary experiments on this last contribution show promising results.
Document type :
Theses
Automatic Control Engineering. Institut National Polytechnique de Toulouse, 2016. English
Liste complète des métadonnées

Cited literature [130 references]  Display  Hide  Download

https://hal.laas.fr/tel-01444799
Contributor : Arlette Evrard <>
Submitted on : Monday, January 30, 2017 - 2:16:00 PM
Last modification on : Thursday, January 11, 2018 - 6:27:07 AM

Identifiers

  • HAL Id : tel-01444799, version 1

Citation

Clément Carbonnel. Harnessing tractability in constraint satisfaction problems. Automatic Control Engineering. Institut National Polytechnique de Toulouse, 2016. English. 〈tel-01444799〉

Share

Metrics

Record views

99

Files downloads

127