Extending Broken Triangles and Enhanced Value-Merging View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2016

AUTHORS

Martin C. Cooper , Achref El Mouelhi , Cyril Terrioux

ABSTRACT

Broken triangles constitute an important concept not only for solving constraint satisfaction problems in polynomial time, but also for variable elimination or domain reduction by merging domain values. Specifically, for a given variable in a binary arc-consistent CSP, if no broken triangle occurs on any pair of values, then this variable can be eliminated while preserving satisfiability. More recently, it has been shown that even when this rule cannot be applied, it could be possible that for a given pair of values no broken triangle occurs. In this case, we can apply a domain-reduction operation which consists in merging these values while preserving satisfiability. In this paper we show that under certain conditions, and even if there are some broken triangles on a pair of values, these values can be merged without changing the satisfiability of the instance. This allows us to define a stronger merging operation and a new tractable class of binary CSP instances. We report experimental trials on benchmark instances. More... »

PAGES

173-188

References to SciGraph publications

  • 1994. Contradicting conventional wisdom in constraint satisfaction in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING
  • 2016-04. Tractability in constraint satisfaction problems: a survey in CONSTRAINTS
  • 2015-10. A hybrid tractable class for non-binary CSPs in CONSTRAINTS
  • 2015. A Microstructure-Based Family of Tractable Classes for CSPs in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING
  • 2014. On Broken Triangles in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING
  • Book

    TITLE

    Principles and Practice of Constraint Programming

    ISBN

    978-3-319-44952-4
    978-3-319-44953-1

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-44953-1_12

    DOI

    http://dx.doi.org/10.1007/978-3-319-44953-1_12

    DIMENSIONS

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


    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": {
              "name": [
                "IRIT, University of Toulouse III"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Cooper", 
            "givenName": "Martin C.", 
            "id": "sg:person.011044367204.67", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011044367204.67"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Aix-Marseille Universit\u00e9, CNRS, ENSAM, Universit\u00e9 de Toulon, LSIS UMR 7296"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mouelhi", 
            "givenName": "Achref El", 
            "id": "sg:person.013774213003.86", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013774213003.86"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Aix-Marseille Universit\u00e9, CNRS, ENSAM, Universit\u00e9 de Toulon, LSIS UMR 7296"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Terrioux", 
            "givenName": "Cyril", 
            "id": "sg:person.014232365062.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014232365062.45"
            ], 
            "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/s10601-015-9198-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006425951", 
              "https://doi.org/10.1007/s10601-015-9198-6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/0952813x.2012.721138", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007097894"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-23219-5_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008447517", 
              "https://doi.org/10.1007/978-3-319-23219-5_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10601-015-9185-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017742435", 
              "https://doi.org/10.1007/s10601-015-9185-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.artint.2010.03.002", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020699779"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2480362.2480382", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024497181"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-58601-6_86", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026133979", 
              "https://doi.org/10.1007/3-540-58601-6_86"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2933575.2933587", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026500634"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jcss.2015.02.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030760395"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.artint.2016.02.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034742371"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0255(74)90008-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042040952"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0255(74)90008-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042040952"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-10428-7_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042377580", 
              "https://doi.org/10.1007/978-3-319-10428-7_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ictai.2014.73", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094203319"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2903220.2903230", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1096186874"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2016", 
        "datePublishedReg": "2016-01-01", 
        "description": "Broken triangles constitute an important concept not only for solving constraint satisfaction problems in polynomial time, but also for variable elimination or domain reduction by merging domain values. Specifically, for a given variable in a binary arc-consistent CSP, if no broken triangle occurs on any pair of values, then this variable can be eliminated while preserving satisfiability. More recently, it has been shown that even when this rule cannot be applied, it could be possible that for a given pair of values no broken triangle occurs. In this case, we can apply a domain-reduction operation which consists in merging these values while preserving satisfiability. In this paper we show that under certain conditions, and even if there are some broken triangles on a pair of values, these values can be merged without changing the satisfiability of the instance. This allows us to define a stronger merging operation and a new tractable class of binary CSP instances. We report experimental trials on benchmark instances.", 
        "editor": [
          {
            "familyName": "Rueher", 
            "givenName": "Michel", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-319-44953-1_12", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-319-44952-4", 
            "978-3-319-44953-1"
          ], 
          "name": "Principles and Practice of Constraint Programming", 
          "type": "Book"
        }, 
        "name": "Extending Broken Triangles and Enhanced Value-Merging", 
        "pagination": "173-188", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-44953-1_12"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "628d067d90238638b4d929ecb06940b368c51b30a55c766af7502cd08396b445"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1020683575"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-319-44953-1_12", 
          "https://app.dimensions.ai/details/publication/pub.1020683575"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T13:27", 
        "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/0000000001_0000000264/records_8664_00000256.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-319-44953-1_12"
      }
    ]
     

    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/978-3-319-44953-1_12'

    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/978-3-319-44953-1_12'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-44953-1_12'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-44953-1_12'


     

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

    132 TRIPLES      23 PREDICATES      42 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-44953-1_12 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N4f5a5c121fa04308973a713a6fe8f485
    4 schema:citation sg:pub.10.1007/3-540-58601-6_86
    5 sg:pub.10.1007/978-3-319-10428-7_5
    6 sg:pub.10.1007/978-3-319-23219-5_6
    7 sg:pub.10.1007/s10601-015-9185-y
    8 sg:pub.10.1007/s10601-015-9198-6
    9 https://doi.org/10.1016/0004-3702(77)90007-8
    10 https://doi.org/10.1016/0020-0255(74)90008-5
    11 https://doi.org/10.1016/j.artint.2010.03.002
    12 https://doi.org/10.1016/j.artint.2016.02.001
    13 https://doi.org/10.1016/j.jcss.2015.02.001
    14 https://doi.org/10.1080/0952813x.2012.721138
    15 https://doi.org/10.1109/ictai.2014.73
    16 https://doi.org/10.1145/2480362.2480382
    17 https://doi.org/10.1145/2903220.2903230
    18 https://doi.org/10.1145/2933575.2933587
    19 schema:datePublished 2016
    20 schema:datePublishedReg 2016-01-01
    21 schema:description Broken triangles constitute an important concept not only for solving constraint satisfaction problems in polynomial time, but also for variable elimination or domain reduction by merging domain values. Specifically, for a given variable in a binary arc-consistent CSP, if no broken triangle occurs on any pair of values, then this variable can be eliminated while preserving satisfiability. More recently, it has been shown that even when this rule cannot be applied, it could be possible that for a given pair of values no broken triangle occurs. In this case, we can apply a domain-reduction operation which consists in merging these values while preserving satisfiability. In this paper we show that under certain conditions, and even if there are some broken triangles on a pair of values, these values can be merged without changing the satisfiability of the instance. This allows us to define a stronger merging operation and a new tractable class of binary CSP instances. We report experimental trials on benchmark instances.
    22 schema:editor N57ed03db9c9c4972822dc271d190667e
    23 schema:genre chapter
    24 schema:inLanguage en
    25 schema:isAccessibleForFree true
    26 schema:isPartOf N2c7e90472cae4ddd9c441e6002c5a0f4
    27 schema:name Extending Broken Triangles and Enhanced Value-Merging
    28 schema:pagination 173-188
    29 schema:productId N3936ed4d95d24c12bfa3ed203346752a
    30 N6875be8277274eafbe6f15f42d2cdffd
    31 Nf04efac956be40ff99a2dd4c42bb2803
    32 schema:publisher N318ffab2575846d6965a70f53c4f7bbc
    33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020683575
    34 https://doi.org/10.1007/978-3-319-44953-1_12
    35 schema:sdDatePublished 2019-04-15T13:27
    36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    37 schema:sdPublisher Nb5b09a42be4b45859a54b77a4866ac24
    38 schema:url http://link.springer.com/10.1007/978-3-319-44953-1_12
    39 sgo:license sg:explorer/license/
    40 sgo:sdDataset chapters
    41 rdf:type schema:Chapter
    42 N1fc49b4d4acc475cbb7dca8bf2a87842 schema:name IRIT, University of Toulouse III
    43 rdf:type schema:Organization
    44 N25b26b54759a42c3997889fe4cbd4b12 rdf:first sg:person.014232365062.45
    45 rdf:rest rdf:nil
    46 N2c7e90472cae4ddd9c441e6002c5a0f4 schema:isbn 978-3-319-44952-4
    47 978-3-319-44953-1
    48 schema:name Principles and Practice of Constraint Programming
    49 rdf:type schema:Book
    50 N318ffab2575846d6965a70f53c4f7bbc schema:location Cham
    51 schema:name Springer International Publishing
    52 rdf:type schema:Organisation
    53 N3936ed4d95d24c12bfa3ed203346752a schema:name dimensions_id
    54 schema:value pub.1020683575
    55 rdf:type schema:PropertyValue
    56 N3fb897a424b6409aaf82ab84814c0913 schema:name Aix-Marseille Université, CNRS, ENSAM, Université de Toulon, LSIS UMR 7296
    57 rdf:type schema:Organization
    58 N4f5a5c121fa04308973a713a6fe8f485 rdf:first sg:person.011044367204.67
    59 rdf:rest Ndc4b78f484b0430b8b0d57fdf0f6f553
    60 N57ed03db9c9c4972822dc271d190667e rdf:first N742a9d5ac45a44958ed448db8789e6f4
    61 rdf:rest rdf:nil
    62 N5cf2d9011d904e39a27b758f071aef2a schema:name Aix-Marseille Université, CNRS, ENSAM, Université de Toulon, LSIS UMR 7296
    63 rdf:type schema:Organization
    64 N6875be8277274eafbe6f15f42d2cdffd schema:name doi
    65 schema:value 10.1007/978-3-319-44953-1_12
    66 rdf:type schema:PropertyValue
    67 N742a9d5ac45a44958ed448db8789e6f4 schema:familyName Rueher
    68 schema:givenName Michel
    69 rdf:type schema:Person
    70 Nb5b09a42be4b45859a54b77a4866ac24 schema:name Springer Nature - SN SciGraph project
    71 rdf:type schema:Organization
    72 Ndc4b78f484b0430b8b0d57fdf0f6f553 rdf:first sg:person.013774213003.86
    73 rdf:rest N25b26b54759a42c3997889fe4cbd4b12
    74 Nf04efac956be40ff99a2dd4c42bb2803 schema:name readcube_id
    75 schema:value 628d067d90238638b4d929ecb06940b368c51b30a55c766af7502cd08396b445
    76 rdf:type schema:PropertyValue
    77 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Information and Computing Sciences
    79 rdf:type schema:DefinedTerm
    80 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Artificial Intelligence and Image Processing
    82 rdf:type schema:DefinedTerm
    83 sg:person.011044367204.67 schema:affiliation N1fc49b4d4acc475cbb7dca8bf2a87842
    84 schema:familyName Cooper
    85 schema:givenName Martin C.
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011044367204.67
    87 rdf:type schema:Person
    88 sg:person.013774213003.86 schema:affiliation N5cf2d9011d904e39a27b758f071aef2a
    89 schema:familyName Mouelhi
    90 schema:givenName Achref El
    91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013774213003.86
    92 rdf:type schema:Person
    93 sg:person.014232365062.45 schema:affiliation N3fb897a424b6409aaf82ab84814c0913
    94 schema:familyName Terrioux
    95 schema:givenName Cyril
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014232365062.45
    97 rdf:type schema:Person
    98 sg:pub.10.1007/3-540-58601-6_86 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026133979
    99 https://doi.org/10.1007/3-540-58601-6_86
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/978-3-319-10428-7_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042377580
    102 https://doi.org/10.1007/978-3-319-10428-7_5
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/978-3-319-23219-5_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008447517
    105 https://doi.org/10.1007/978-3-319-23219-5_6
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/s10601-015-9185-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1017742435
    108 https://doi.org/10.1007/s10601-015-9185-y
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/s10601-015-9198-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006425951
    111 https://doi.org/10.1007/s10601-015-9198-6
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1016/0004-3702(77)90007-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001107257
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1016/0020-0255(74)90008-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042040952
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1016/j.artint.2010.03.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020699779
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1016/j.artint.2016.02.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034742371
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1016/j.jcss.2015.02.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030760395
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1080/0952813x.2012.721138 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007097894
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1109/ictai.2014.73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094203319
    126 rdf:type schema:CreativeWork
    127 https://doi.org/10.1145/2480362.2480382 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024497181
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.1145/2903220.2903230 schema:sameAs https://app.dimensions.ai/details/publication/pub.1096186874
    130 rdf:type schema:CreativeWork
    131 https://doi.org/10.1145/2933575.2933587 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026500634
    132 rdf:type schema:CreativeWork
     




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


    ...