Revisiting restricted path consistency View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2017-07

AUTHORS

Kostas Stergiou

ABSTRACT

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. More... »

PAGES

377-402

References to SciGraph publications

  • 2007. Sampling Strategies and Variable Selection in Weighted Degree Heuristics in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP 2007
  • 1996. MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problems in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING — CP96
  • 2011-01. Efficient algorithms for singleton arc consistency in CONSTRAINTS
  • 2005. 2 -Way vs.d -Way Branching for CSP in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2005
  • 2015. Restricted Path Consistency Revisited in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING
  • 1997. From restricted path consistency to max-restricted path consistency in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING-CP97
  • 2003. Improved Algorithms for Max-restricted Path Consistency in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP 2003
  • 2000. Singleton Consistencies in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP 2000
  • 2013. Adaptive Parameterized Consistency in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING
  • 1997. Understanding and improving the MAC algorithm in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING-CP97
  • 2011-10. New algorithms for max restricted path consistency in CONSTRAINTS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10601-016-9255-9

    DOI

    http://dx.doi.org/10.1007/s10601-016-9255-9

    DIMENSIONS

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


    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/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

    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-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

    Subject Predicate Object
    1 sg:pub.10.1007/s10601-016-9255-9 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author Nc83e5293765143f38905a8199553978a
    4 schema:citation sg:pub.10.1007/11564751_27
    5 sg:pub.10.1007/3-540-45349-0_26
    6 sg:pub.10.1007/3-540-61551-2_66
    7 sg:pub.10.1007/978-3-319-23219-5_30
    8 sg:pub.10.1007/978-3-540-45193-8_67
    9 sg:pub.10.1007/978-3-540-74970-7_61
    10 sg:pub.10.1007/978-3-642-40627-0_14
    11 sg:pub.10.1007/bfb0017438
    12 sg:pub.10.1007/bfb0017448
    13 sg:pub.10.1007/s10601-009-9080-5
    14 sg:pub.10.1007/s10601-011-9110-y
    15 https://doi.org/10.1016/0004-3702(77)90007-8
    16 https://doi.org/10.1016/0004-3702(86)90083-4
    17 https://doi.org/10.1016/0004-3702(94)90041-8
    18 https://doi.org/10.1016/j.artint.2007.10.016
    19 https://doi.org/10.1016/j.jalgor.2008.02.009
    20 https://doi.org/10.1109/caia.1995.378792
    21 https://doi.org/10.1613/jair.834
    22 schema:datePublished 2017-07
    23 schema:datePublishedReg 2017-07-01
    24 schema: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.
    25 schema:genre research_article
    26 schema:inLanguage en
    27 schema:isAccessibleForFree false
    28 schema:isPartOf N155fd509edfd47ce8ae7d5210cfe36b5
    29 Nde343c0107a84c0f9e8f23e791f1ddfd
    30 sg:journal.1043977
    31 schema:name Revisiting restricted path consistency
    32 schema:pagination 377-402
    33 schema:productId N1789073db1b14e5ab772c580f0b35156
    34 N742e625b52194b5abb2c36cce4c5e239
    35 Naa7854b5cd724f1b8e18621c220c9a09
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044481121
    37 https://doi.org/10.1007/s10601-016-9255-9
    38 schema:sdDatePublished 2019-04-11T12:36
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher N7090d12c977844b5bbc27c14da8eecf9
    41 schema:url https://link.springer.com/10.1007%2Fs10601-016-9255-9
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset articles
    44 rdf:type schema:ScholarlyArticle
    45 N155fd509edfd47ce8ae7d5210cfe36b5 schema:volumeNumber 22
    46 rdf:type schema:PublicationVolume
    47 N1789073db1b14e5ab772c580f0b35156 schema:name dimensions_id
    48 schema:value pub.1044481121
    49 rdf:type schema:PropertyValue
    50 N7090d12c977844b5bbc27c14da8eecf9 schema:name Springer Nature - SN SciGraph project
    51 rdf:type schema:Organization
    52 N742e625b52194b5abb2c36cce4c5e239 schema:name readcube_id
    53 schema:value d3e1562bb2f2293a3d85b8afff53cab06d45c0f587b83b382f81f34255da866c
    54 rdf:type schema:PropertyValue
    55 Naa7854b5cd724f1b8e18621c220c9a09 schema:name doi
    56 schema:value 10.1007/s10601-016-9255-9
    57 rdf:type schema:PropertyValue
    58 Nc83e5293765143f38905a8199553978a rdf:first sg:person.07407403032.10
    59 rdf:rest rdf:nil
    60 Nde343c0107a84c0f9e8f23e791f1ddfd schema:issueNumber 3
    61 rdf:type schema:PublicationIssue
    62 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Mathematical Sciences
    64 rdf:type schema:DefinedTerm
    65 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Numerical and Computational Mathematics
    67 rdf:type schema:DefinedTerm
    68 sg:journal.1043977 schema:issn 1383-7133
    69 1572-9354
    70 schema:name Constraints
    71 rdf:type schema:Periodical
    72 sg:person.07407403032.10 schema:affiliation https://www.grid.ac/institutes/grid.184212.c
    73 schema:familyName Stergiou
    74 schema:givenName Kostas
    75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07407403032.10
    76 rdf:type schema:Person
    77 sg:pub.10.1007/11564751_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001572643
    78 https://doi.org/10.1007/11564751_27
    79 rdf:type schema:CreativeWork
    80 sg:pub.10.1007/3-540-45349-0_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011850710
    81 https://doi.org/10.1007/3-540-45349-0_26
    82 rdf:type schema:CreativeWork
    83 sg:pub.10.1007/3-540-61551-2_66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023418497
    84 https://doi.org/10.1007/3-540-61551-2_66
    85 rdf:type schema:CreativeWork
    86 sg:pub.10.1007/978-3-319-23219-5_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052693801
    87 https://doi.org/10.1007/978-3-319-23219-5_30
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/978-3-540-45193-8_67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043432110
    90 https://doi.org/10.1007/978-3-540-45193-8_67
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/978-3-540-74970-7_61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007693744
    93 https://doi.org/10.1007/978-3-540-74970-7_61
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/978-3-642-40627-0_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025557301
    96 https://doi.org/10.1007/978-3-642-40627-0_14
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/bfb0017438 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011986368
    99 https://doi.org/10.1007/bfb0017438
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/bfb0017448 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018041561
    102 https://doi.org/10.1007/bfb0017448
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/s10601-009-9080-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022449749
    105 https://doi.org/10.1007/s10601-009-9080-5
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/s10601-011-9110-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1011891630
    108 https://doi.org/10.1007/s10601-011-9110-y
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1016/0004-3702(77)90007-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001107257
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1016/0004-3702(86)90083-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053367648
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1016/0004-3702(94)90041-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034200625
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1016/j.artint.2007.10.016 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053162424
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1016/j.jalgor.2008.02.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012351978
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1109/caia.1995.378792 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094455415
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1613/jair.834 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105579530
    123 rdf:type schema:CreativeWork
    124 https://www.grid.ac/institutes/grid.184212.c schema:alternateName University of Western Macedonia
    125 schema:name Department of Informatics and Telecommunications Engineering, University of Western Macedonia, Kozani, Greece
    126 rdf:type schema:Organization
     




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


    ...