Ontology type: schema:ScholarlyArticle
2017-01
AUTHORS ABSTRACTThe 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... »
PAGES97-98
http://scigraph.springernature.com/pub.10.1007/s10601-016-9262-x
DOIhttp://dx.doi.org/10.1007/s10601-016-9262-x
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1040407334
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
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 |