The Community Structure of Constraint Satisfaction Problems and Its Correlation with Search Time

OnderzoeksoutputAcademicpeer review

1 Citaat (Scopus)
112 Downloads (Pure)

Samenvatting

Constraint satisfaction problems are, in general, NP-complete problems, meaning that the computational complexity increases exponentially with the size of the problem in the worst case, under the assumption that P does not equal NP. The structure of a problem heavily influences its computational complexity, however, and problems with a restricted structure constitute one of the general classes of tractable problems. This paper explores the community structure of constraint satisfaction problems, a type of structure already found to be important for SAT problems that is inherent to certain real-world domains. The community structure of the instances of the MiniZinc Challenge of 2019 was identified, and its correlation with the search times of four state-of-the-art solvers as well as with the tree-width of the instances was analysed. The results reveal the strong community structure of many of the instances, although the strength of the community structure seems to only marginally affect the search times. On the other hand, a strong correlation between the community structure and the tree-width is observed, where stronger community structure suggests better decomposability. Taking community structure into account more explicitly during the search process may, therefore, allow constraints solvers to solve problems with strong community structure more efficiently.
Originele taal-2English
Titel2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI)
UitgeverijIEEE
Pagina's153-160
Aantal pagina's8
ISBN van geprinte versie978-1-7281-8536-1
DOI's
StatusPublished - 11-nov.-2020
Evenement2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI) - Baltimore, MD, USA
Duur: 9-nov.-202011-nov.-2020

Conference

Conference2020 IEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI)
Periode09/11/202011/11/2020

Vingerafdruk

Duik in de onderzoeksthema's van 'The Community Structure of Constraint Satisfaction Problems and Its Correlation with Search Time'. Samen vormen ze een unieke vingerafdruk.

Citeer dit