Tractable classes for CSPs of arbitrary arity: from theory to practice View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2017-01

AUTHORS

Achref El Mouelhi

ABSTRACT

The research of this thesis focuses on the analysis of polynomial classes and their practical exploitation for solving constraint satisfaction problems (CSPs) with finite domains. In particular, I worked on bridging the gap between theoretical works and practical results in constraint solvers. Specifically, the goal of this thesis is to find explanation for the effectiveness of solvers, and also to show that studied tractable classes are not artificial since several real-problems among the ones used in the CSP 2008 Competition belong to them. Our work is organized into three main parts. In the first part, we proposed several types of microstructures for CSPs of arbitrary arity which are based on some knwon binary encoding of non-binary CSPs like, dual encoding, hidden-variable transformation and mixed (or double) encoding. These theoretical tools are designed to facilitate the study of tractable classes, sets of CSP instances which can be solved in polytime, when the constraints are non-binary. After that, we propose a new tractable classes of CSPs whose the highlighting should allow on the one hand to explain the effectiveness of solvers of the state of the art namely FC, MAC, RFL and on the second hand to provide the opportunities for easy integration in these solvers. These would include the definition of new tractable classes without using of an ad hoc algorithms as in the traditional case. These new tractable classes are related to the number of maximal cliques in the microstructure of binary or non-binary CSP. In the last part, we focus on the presence of instances belonging to polynomial classes in classical benchmarks used by the CP community. We study in particular the Broken-Triangle Property (BTP) and its extension DBTP to CSP of arbitrary arity. Next, we prove that BTP can also be used to reduce the size of the search space by merging pairs of values on which no broken triangle exists. Finally, we introduce a formal framework, called transformation, and we develop the concept of hidden tractable class that we exploit from an experimental point of view. More... »

PAGES

97-98

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10601-016-9262-x

DOI

http://dx.doi.org/10.1007/s10601-016-9262-x

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1040407334


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Laboratoire des Sciences de l'Information et des Syst\u00e8mes", 
          "id": "https://www.grid.ac/institutes/grid.462878.7", 
          "name": [
            "Aix Marseille University, Universit\u00e9 de Toulon, CNRS, ENSAM, LSIS, Marseille, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "El Mouelhi", 
        "givenName": "Achref", 
        "id": "sg:person.013774213003.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013774213003.86"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2017-01", 
    "datePublishedReg": "2017-01-01", 
    "description": "The research of this thesis focuses on the analysis of polynomial classes and their practical exploitation for solving constraint satisfaction problems (CSPs) with finite domains. In particular, I worked on bridging the gap between theoretical works and practical results in constraint solvers. Specifically, the goal of this thesis is to find explanation for the effectiveness of solvers, and also to show that studied tractable classes are not artificial since several real-problems among the ones used in the CSP 2008 Competition belong to them. Our work is organized into three main parts. In the first part, we proposed several types of microstructures for CSPs of arbitrary arity which are based on some knwon binary encoding of non-binary CSPs like, dual encoding, hidden-variable transformation and mixed (or double) encoding. These theoretical tools are designed to facilitate the study of tractable classes, sets of CSP instances which can be solved in polytime, when the constraints are non-binary. After that, we propose a new tractable classes of CSPs whose the highlighting should allow on the one hand to explain the effectiveness of solvers of the state of the art namely FC, MAC, RFL and on the second hand to provide the opportunities for easy integration in these solvers. These would include the definition of new tractable classes without using of an ad hoc algorithms as in the traditional case. These new tractable classes are related to the number of maximal cliques in the microstructure of binary or non-binary CSP. In the last part, we focus on the presence of instances belonging to polynomial classes in classical benchmarks used by the CP community. We study in particular the Broken-Triangle Property (BTP) and its extension DBTP to CSP of arbitrary arity. Next, we prove that BTP can also be used to reduce the size of the search space by merging pairs of values on which no broken triangle exists. Finally, we introduce a formal framework, called transformation, and we develop the concept of hidden tractable class that we exploit from an experimental point of view.", 
    "genre": "non_research_article", 
    "id": "sg:pub.10.1007/s10601-016-9262-x", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1043977", 
        "issn": [
          "1383-7133", 
          "1572-9354"
        ], 
        "name": "Constraints", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "22"
      }
    ], 
    "name": "Tractable classes for CSPs of arbitrary arity: from theory to practice", 
    "pagination": "97-98", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "c07b74fdfdf78571e3062b50480b3b821cce7522c8a47118b0a2787605173160"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10601-016-9262-x"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040407334"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10601-016-9262-x", 
      "https://app.dimensions.ai/details/publication/pub.1040407334"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T12:41", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70053_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10601-016-9262-x"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10601-016-9262-x'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10601-016-9262-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10601-016-9262-x'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10601-016-9262-x'


 

This table displays all metadata directly associated to this object as RDF triples.

61 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10601-016-9262-x schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N80659a55616b4cd5a295e1059b98c953
4 schema:datePublished 2017-01
5 schema:datePublishedReg 2017-01-01
6 schema:description The research of this thesis focuses on the analysis of polynomial classes and their practical exploitation for solving constraint satisfaction problems (CSPs) with finite domains. In particular, I worked on bridging the gap between theoretical works and practical results in constraint solvers. Specifically, the goal of this thesis is to find explanation for the effectiveness of solvers, and also to show that studied tractable classes are not artificial since several real-problems among the ones used in the CSP 2008 Competition belong to them. Our work is organized into three main parts. In the first part, we proposed several types of microstructures for CSPs of arbitrary arity which are based on some knwon binary encoding of non-binary CSPs like, dual encoding, hidden-variable transformation and mixed (or double) encoding. These theoretical tools are designed to facilitate the study of tractable classes, sets of CSP instances which can be solved in polytime, when the constraints are non-binary. After that, we propose a new tractable classes of CSPs whose the highlighting should allow on the one hand to explain the effectiveness of solvers of the state of the art namely FC, MAC, RFL and on the second hand to provide the opportunities for easy integration in these solvers. These would include the definition of new tractable classes without using of an ad hoc algorithms as in the traditional case. These new tractable classes are related to the number of maximal cliques in the microstructure of binary or non-binary CSP. In the last part, we focus on the presence of instances belonging to polynomial classes in classical benchmarks used by the CP community. We study in particular the Broken-Triangle Property (BTP) and its extension DBTP to CSP of arbitrary arity. Next, we prove that BTP can also be used to reduce the size of the search space by merging pairs of values on which no broken triangle exists. Finally, we introduce a formal framework, called transformation, and we develop the concept of hidden tractable class that we exploit from an experimental point of view.
7 schema:genre non_research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N4e16067504aa4223bc956f9bf9b6c54e
11 N6a85a45996cd44028764e12a57201fb0
12 sg:journal.1043977
13 schema:name Tractable classes for CSPs of arbitrary arity: from theory to practice
14 schema:pagination 97-98
15 schema:productId N0b802859d59f463ca88f7a30bcaa765c
16 N6fffdb609d204cb8a54e6d45229b81bc
17 Nc94e063ef54a42348964ea3d9cc24588
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040407334
19 https://doi.org/10.1007/s10601-016-9262-x
20 schema:sdDatePublished 2019-04-11T12:41
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N734100634e2a480a82a83b534135e1f1
23 schema:url https://link.springer.com/10.1007%2Fs10601-016-9262-x
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N0b802859d59f463ca88f7a30bcaa765c schema:name readcube_id
28 schema:value c07b74fdfdf78571e3062b50480b3b821cce7522c8a47118b0a2787605173160
29 rdf:type schema:PropertyValue
30 N4e16067504aa4223bc956f9bf9b6c54e schema:volumeNumber 22
31 rdf:type schema:PublicationVolume
32 N6a85a45996cd44028764e12a57201fb0 schema:issueNumber 1
33 rdf:type schema:PublicationIssue
34 N6fffdb609d204cb8a54e6d45229b81bc schema:name dimensions_id
35 schema:value pub.1040407334
36 rdf:type schema:PropertyValue
37 N734100634e2a480a82a83b534135e1f1 schema:name Springer Nature - SN SciGraph project
38 rdf:type schema:Organization
39 N80659a55616b4cd5a295e1059b98c953 rdf:first sg:person.013774213003.86
40 rdf:rest rdf:nil
41 Nc94e063ef54a42348964ea3d9cc24588 schema:name doi
42 schema:value 10.1007/s10601-016-9262-x
43 rdf:type schema:PropertyValue
44 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
45 schema:name Information and Computing Sciences
46 rdf:type schema:DefinedTerm
47 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
48 schema:name Artificial Intelligence and Image Processing
49 rdf:type schema:DefinedTerm
50 sg:journal.1043977 schema:issn 1383-7133
51 1572-9354
52 schema:name Constraints
53 rdf:type schema:Periodical
54 sg:person.013774213003.86 schema:affiliation https://www.grid.ac/institutes/grid.462878.7
55 schema:familyName El Mouelhi
56 schema:givenName Achref
57 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013774213003.86
58 rdf:type schema:Person
59 https://www.grid.ac/institutes/grid.462878.7 schema:alternateName Laboratoire des Sciences de l'Information et des Systèmes
60 schema:name Aix Marseille University, Université de Toulon, CNRS, ENSAM, LSIS, Marseille, France
61 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...