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 N05a0a19a524d438a871a6a14109ee319
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 N5289d915d2d049be9ca183cbd6790dab
11 Na2599829c6f1415a8daf8721dece6034
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 N18866497fcf5424d8ae23bff62dff8c1
16 N40bfe93181134b32ac731c1e9ae0b49a
17 Nc4eac228fe5f41ed91d30ecd91e4b035
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 N83cb8222f2804cada5a77197f95201ed
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 N05a0a19a524d438a871a6a14109ee319 rdf:first sg:person.013774213003.86
28 rdf:rest rdf:nil
29 N18866497fcf5424d8ae23bff62dff8c1 schema:name dimensions_id
30 schema:value pub.1040407334
31 rdf:type schema:PropertyValue
32 N40bfe93181134b32ac731c1e9ae0b49a schema:name doi
33 schema:value 10.1007/s10601-016-9262-x
34 rdf:type schema:PropertyValue
35 N5289d915d2d049be9ca183cbd6790dab schema:volumeNumber 22
36 rdf:type schema:PublicationVolume
37 N83cb8222f2804cada5a77197f95201ed schema:name Springer Nature - SN SciGraph project
38 rdf:type schema:Organization
39 Na2599829c6f1415a8daf8721dece6034 schema:issueNumber 1
40 rdf:type schema:PublicationIssue
41 Nc4eac228fe5f41ed91d30ecd91e4b035 schema:name readcube_id
42 schema:value c07b74fdfdf78571e3062b50480b3b821cce7522c8a47118b0a2787605173160
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)


...