NDLI: Combining restarts, nogoods and bag-connected decompositions for solving CSPs

Please wait, while we are loading the content...

Combining restarts, nogoods and bag-connected decompositions for solving CSPs

Content Provider	Springer Nature Link
Author	Jégou, Philippe Terrioux, Cyril
Copyright Year	2016
Abstract	From a theoretical viewpoint, the (tree-)decomposition methods offer a good approach for solving Constraint Satisfaction Problems (CSPs) when their (tree)-width is small. In this case, they have often shown their practical interest. So, the literature (coming from Mathematics, OR or AI) has concentrated its efforts on the minimization of a single parameter, namely the tree-width. Nevertheless, experimental studies have shown that this parameter is not always the most relevant to consider when solving CSPs. So, in this paper, we highlight two fundamental problems related to the use of tree-decomposition and for which we offer two particularly appropriate solutions. First, we experimentally show that the decomposition algorithms of the state of the art produce clusters (a tree-decomposition is a rooted tree of clusters) having several connected components. We highlight the fact that such clusters create a real disadvantage which affects significantly the efficiency of solving methods. To avoid this problem, we consider here a new graph decomposition called Bag-Connected Tree-Decomposition, which considers only tree-decompositions such that each cluster is connected. We analyze such decompositions from an algorithmic point of view, especially in order to propose a first polynomial time algorithm to compute them. Moreover, even if we consider a very well suited decomposition, it is well known that sometimes, a bad choice for the root cluster may significantly degrade the performance of the solving. We highlight an explanation of this degradation and we propose a solution based on restart techniques. Then, we present a new version of the BTD algorithm (for Backtracking with Tree-Decomposition Jégou and Terrioux, Artificial Intelligence, 146 43–75 28) integrating restart techniques. From a theoretical viewpoint, we prove that reduced nld-nogoods can be safely recorded during the search and that their size is smaller than ones recorded by MAC+RST+NG (Lecoutre et al., JSAT, 1(3–4) 147–167 34). We also show how structural (no)goods may be exploited when the search restarts from a new root cluster. Finally, from a practical viewpoint, we show experimentally the benefits of using independently bag-connected tree-decompositions and restart techniques for solving CSPs by decomposition methods. Above all, we experimentally highlight the advantages brought by exploiting jointly these improvements in order to respond to two major problems generally encountered when solving CSPs by decomposition methods.
Starting Page	191
Ending Page	229
Page Count	39
File Format	PDF
ISSN	13837133
Journal	Constraints
Volume Number	22
Issue Number	2
e-ISSN	15729354
Language	English
Publisher	Springer US
Publisher Date	2016-08-02
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Constraint satisfaction problems Tree-decomposition Bag-connected tree-decomposition Restart Artificial Intelligence (incl. Robotics) Optimization Computing Methodologies Operation Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Artificial Intelligence Computational Theory and Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Combining Restarts, Nogoods and Bag-Connected Decompositions for Solving CSPs

A commentary on “Hybrid search for minimal perturbation in Dynamic CSPs”

Hybrid search for minimal perturbation in Dynamic CSPs

Interleaving solving and elicitation of constraint satisfaction problems based on expected cost

A hybrid tractable class for non-binary CSPs

Solving Mixed and Conditional Constraint Satisfaction Problems

Strong consistencies for weighted constraint satisfaction problems

Periodic Constraint Satisfaction Problems: Tractable Subclasses

Symmetry Definitions for Constraint Satisfaction Problems

Combining restarts, nogoods and bag-connected decompositions for solving CSPs

Similar Documents

Combining Restarts, Nogoods and Bag-Connected Decompositions for Solving CSPs

A commentary on “Hybrid search for minimal perturbation in Dynamic CSPs”

Hybrid search for minimal perturbation in Dynamic CSPs

Interleaving solving and elicitation of constraint satisfaction problems based on expected cost

A hybrid tractable class for non-binary CSPs

Solving Mixed and Conditional Constraint Satisfaction Problems

Strong consistencies for weighted constraint satisfaction problems

Periodic Constraint Satisfaction Problems: Tractable Subclasses

Symmetry Definitions for Constraint Satisfaction Problems

Combining restarts, nogoods and bag-connected decompositions for solving CSPs