2017-07
AUTHORS ABSTRACTRestricted path consistency (RPC) is a strong local consistency for binary constraints that was proposed 20 years ago and was identified as a promising alternative to arc consistency (AC) in an early experimental study of local consistencies for binary constraints. However, in contrast to other strong local consistencies such as singleton arc consistency (SAC) and max restricted path consistency (maxRPC), it has been neglected since then. In this paper we revisit RPC. First we propose RPC3, a new RPC algorithm that is very easy to implement and can be efficiently applied throughout search. Then we perform a wide experimental study of RPC3 and a light version that achieves an approximation of RPC, comparing them to state-of-the-art AC and maxRPC algorithms. Experimental results obtained under various solver settings, regarding the branching scheme, the variable ordering heuristic, and restarts, clearly show that light RPC is by far more efficient than both AC and maxRPC when applied throughout search. We also examine the experimental behaviour of an algorithm for a simple extension of RCP called 2-RPC, showing that it is competitive with RPC3, and better than both AC and maxRPC. Overall, our results strongly suggest that it is time to reconsider the established perception that MAC is the best general purpose method for solving binary CSPs. More... »
PAGES377-402
http://scigraph.springernature.com/pub.10.1007/s10601-016-9255-9
DOIhttp://dx.doi.org/10.1007/s10601-016-9255-9
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1044481121
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/0103",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Numerical and Computational Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "University of Western Macedonia",
"id": "https://www.grid.ac/institutes/grid.184212.c",
"name": [
"Department of Informatics and Telecommunications Engineering, University of Western Macedonia, Kozani, Greece"
],
"type": "Organization"
},
"familyName": "Stergiou",
"givenName": "Kostas",
"id": "sg:person.07407403032.10",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07407403032.10"
],
"type": "Person"
}
],
"citation": [
{
"id": "https://doi.org/10.1016/0004-3702(77)90007-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001107257"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11564751_27",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001572643",
"https://doi.org/10.1007/11564751_27"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-74970-7_61",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007693744",
"https://doi.org/10.1007/978-3-540-74970-7_61"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-74970-7_61",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007693744",
"https://doi.org/10.1007/978-3-540-74970-7_61"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45349-0_26",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011850710",
"https://doi.org/10.1007/3-540-45349-0_26"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10601-011-9110-y",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011891630",
"https://doi.org/10.1007/s10601-011-9110-y"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0017438",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011986368",
"https://doi.org/10.1007/bfb0017438"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.jalgor.2008.02.009",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012351978"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0017448",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018041561",
"https://doi.org/10.1007/bfb0017448"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10601-009-9080-5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1022449749",
"https://doi.org/10.1007/s10601-009-9080-5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-61551-2_66",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1023418497",
"https://doi.org/10.1007/3-540-61551-2_66"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-40627-0_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1025557301",
"https://doi.org/10.1007/978-3-642-40627-0_14"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0004-3702(94)90041-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034200625"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0004-3702(94)90041-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1034200625"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45193-8_67",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043432110",
"https://doi.org/10.1007/978-3-540-45193-8_67"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-23219-5_30",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052693801",
"https://doi.org/10.1007/978-3-319-23219-5_30"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.artint.2007.10.016",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053162424"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0004-3702(86)90083-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053367648"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0004-3702(86)90083-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053367648"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/caia.1995.378792",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1094455415"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1613/jair.834",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1105579530"
],
"type": "CreativeWork"
}
],
"datePublished": "2017-07",
"datePublishedReg": "2017-07-01",
"description": "Restricted path consistency (RPC) is a strong local consistency for binary constraints that was proposed 20 years ago and was identified as a promising alternative to arc consistency (AC) in an early experimental study of local consistencies for binary constraints. However, in contrast to other strong local consistencies such as singleton arc consistency (SAC) and max restricted path consistency (maxRPC), it has been neglected since then. In this paper we revisit RPC. First we propose RPC3, a new RPC algorithm that is very easy to implement and can be efficiently applied throughout search. Then we perform a wide experimental study of RPC3 and a light version that achieves an approximation of RPC, comparing them to state-of-the-art AC and maxRPC algorithms. Experimental results obtained under various solver settings, regarding the branching scheme, the variable ordering heuristic, and restarts, clearly show that light RPC is by far more efficient than both AC and maxRPC when applied throughout search. We also examine the experimental behaviour of an algorithm for a simple extension of RCP called 2-RPC, showing that it is competitive with RPC3, and better than both AC and maxRPC. Overall, our results strongly suggest that it is time to reconsider the established perception that MAC is the best general purpose method for solving binary CSPs.",
"genre": "research_article",
"id": "sg:pub.10.1007/s10601-016-9255-9",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1043977",
"issn": [
"1383-7133",
"1572-9354"
],
"name": "Constraints",
"type": "Periodical"
},
{
"issueNumber": "3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "22"
}
],
"name": "Revisiting restricted path consistency",
"pagination": "377-402",
"productId": [
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"d3e1562bb2f2293a3d85b8afff53cab06d45c0f587b83b382f81f34255da866c"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10601-016-9255-9"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1044481121"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10601-016-9255-9",
"https://app.dimensions.ai/details/publication/pub.1044481121"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T12:36",
"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_70028_00000002.jsonl",
"type": "ScholarlyArticle",
"url": "https://link.springer.com/10.1007%2Fs10601-016-9255-9"
}
]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-9255-9'
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-9255-9'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10601-016-9255-9'
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-9255-9'
This table displays all metadata directly associated to this object as RDF triples.
126 TRIPLES
21 PREDICATES
45 URIs
19 LITERALS
7 BLANK NODES