Solving Constraint Satisfaction Problems Containing Vectors of Unknown Size View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2017

AUTHORS

Erez Bilgory , Eyal Bin , Avi Ziv

ABSTRACT

Constraint satisfaction problems (CSPs) are used to solve real-life problems with inherent structures that contain vectors for repeating sets of variables and constraints. Often, the structure of the problem is a part of the problem, since the number of elements in the vector is not known in advance. We propose a method to solve such problems, even when there is no maximal length provided. Our method is based on constructing a vector size CSP from the problem description, and solving it to get the number of elements in the vector. We then use the vector size to construct and solve a CSP that has a specific number of elements. Experimental results show that this method enables fast solving of problems that cannot be solved or even constructed by existing methods. More... »

PAGES

55-70

References to SciGraph publications

  • 2012. Dynamic Test Data Generation for Data Intensive Applications in HARDWARE AND SOFTWARE: VERIFICATION AND TESTING
  • 2003. Greater Efficiency for Conditional Constraint Satisfaction in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP 2003
  • 1999. A Fixpoint Definition of Dynamic Constraint Satisfaction in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP’99
  • 2003. Constraint Reasoning over Strings in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP 2003
  • 2017. MiniZinc with Strings in LOGIC-BASED PROGRAM SYNTHESIS AND TRANSFORMATION
  • 2015. Constraint Solving on Bounded String Variables in INTEGRATION OF AI AND OR TECHNIQUES IN CONSTRAINT PROGRAMMING
  • 1995. Asynchronous weak-commitment search for solving distributed constraint satisfaction problems in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING — CP '95
  • Book

    TITLE

    Principles and Practice of Constraint Programming

    ISBN

    978-3-319-66157-5
    978-3-319-66158-2

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-66158-2_4

    DOI

    http://dx.doi.org/10.1007/978-3-319-66158-2_4

    DIMENSIONS

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


    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": {
              "name": [
                "IBM Research"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bilgory", 
            "givenName": "Erez", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "IBM Research"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bin", 
            "givenName": "Eyal", 
            "id": "sg:person.012172725707.55", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012172725707.55"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "IBM Research"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ziv", 
            "givenName": "Avi", 
            "id": "sg:person.07506141212.88", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07506141212.88"
            ], 
            "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/3-540-60299-2_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022547214", 
              "https://doi.org/10.1007/3-540-60299-2_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45193-8_44", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026556331", 
              "https://doi.org/10.1007/978-3-540-45193-8_44"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45193-8_44", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026556331", 
              "https://doi.org/10.1007/978-3-540-45193-8_44"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-18008-3_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037569377", 
              "https://doi.org/10.1007/978-3-319-18008-3_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45193-8_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043258167", 
              "https://doi.org/10.1007/978-3-540-45193-8_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45193-8_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043258167", 
              "https://doi.org/10.1007/978-3-540-45193-8_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-48085-3_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049879906", 
              "https://doi.org/10.1007/978-3-540-48085-3_30"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-48085-3_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049879906", 
              "https://doi.org/10.1007/978-3-540-48085-3_30"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-34188-5_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053130484", 
              "https://doi.org/10.1007/978-3-642-34188-5_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0890060498124101", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1054081232"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s0890060498124101", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1054081232"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1147/sj.413.0386", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063184710"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-63139-4_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1090873063", 
              "https://doi.org/10.1007/978-3-319-63139-4_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/date.2012.6176425", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093555671"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sp.2010.38", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095176583"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1613/jair.1335", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1105579301"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2017", 
        "datePublishedReg": "2017-01-01", 
        "description": "Constraint satisfaction problems (CSPs) are used to solve real-life problems with inherent structures that contain vectors for repeating sets of variables and constraints. Often, the structure of the problem is a part of the problem, since the number of elements in the vector is not known in advance. We propose a method to solve such problems, even when there is no maximal length provided. Our method is based on constructing a vector size CSP from the problem description, and solving it to get the number of elements in the vector. We then use the vector size to construct and solve a CSP that has a specific number of elements. Experimental results show that this method enables fast solving of problems that cannot be solved or even constructed by existing methods.", 
        "editor": [
          {
            "familyName": "Beck", 
            "givenName": "J. Christopher", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-319-66158-2_4", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-319-66157-5", 
            "978-3-319-66158-2"
          ], 
          "name": "Principles and Practice of Constraint Programming", 
          "type": "Book"
        }, 
        "name": "Solving Constraint Satisfaction Problems Containing Vectors of Unknown Size", 
        "pagination": "55-70", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-66158-2_4"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "f566dc1c42a99afed708e3d1ae4cc1257eccd5bc0d1e30e1dcaa0bdaa375e7f2"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1091295122"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-319-66158-2_4", 
          "https://app.dimensions.ai/details/publication/pub.1091295122"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T13:10", 
        "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_8663_00000601.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-319-66158-2_4"
      }
    ]
     

    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-66158-2_4'

    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-66158-2_4'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-66158-2_4'

    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-66158-2_4'


     

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

    127 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-66158-2_4 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author N4c70b3e7366c4efbbff75a9a592a5752
    4 schema:citation sg:pub.10.1007/3-540-60299-2_6
    5 sg:pub.10.1007/978-3-319-18008-3_26
    6 sg:pub.10.1007/978-3-319-63139-4_4
    7 sg:pub.10.1007/978-3-540-45193-8_26
    8 sg:pub.10.1007/978-3-540-45193-8_44
    9 sg:pub.10.1007/978-3-540-48085-3_30
    10 sg:pub.10.1007/978-3-642-34188-5_19
    11 https://doi.org/10.1016/0004-3702(77)90007-8
    12 https://doi.org/10.1017/s0890060498124101
    13 https://doi.org/10.1109/date.2012.6176425
    14 https://doi.org/10.1109/sp.2010.38
    15 https://doi.org/10.1147/sj.413.0386
    16 https://doi.org/10.1613/jair.1335
    17 schema:datePublished 2017
    18 schema:datePublishedReg 2017-01-01
    19 schema:description Constraint satisfaction problems (CSPs) are used to solve real-life problems with inherent structures that contain vectors for repeating sets of variables and constraints. Often, the structure of the problem is a part of the problem, since the number of elements in the vector is not known in advance. We propose a method to solve such problems, even when there is no maximal length provided. Our method is based on constructing a vector size CSP from the problem description, and solving it to get the number of elements in the vector. We then use the vector size to construct and solve a CSP that has a specific number of elements. Experimental results show that this method enables fast solving of problems that cannot be solved or even constructed by existing methods.
    20 schema:editor N3ef5f0398fc641ed80edca145cc20287
    21 schema:genre chapter
    22 schema:inLanguage en
    23 schema:isAccessibleForFree false
    24 schema:isPartOf Naacc36b9f9ca4359a65809be0512118d
    25 schema:name Solving Constraint Satisfaction Problems Containing Vectors of Unknown Size
    26 schema:pagination 55-70
    27 schema:productId N7c27eaf2cdd94616aec0ca65e42d6e32
    28 Nac4d5df22de84b12b89921ca15c60bfb
    29 Ne2796b0cce344d0486b5f3629fea2ffe
    30 schema:publisher Na64d11f6b7324eccb9f7a20f8e1feaac
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091295122
    32 https://doi.org/10.1007/978-3-319-66158-2_4
    33 schema:sdDatePublished 2019-04-15T13:10
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher N9779a6a9abbb433f804a8457e76d611e
    36 schema:url http://link.springer.com/10.1007/978-3-319-66158-2_4
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset chapters
    39 rdf:type schema:Chapter
    40 N125a96763e044ba7b35ae87151b1b92d schema:familyName Beck
    41 schema:givenName J. Christopher
    42 rdf:type schema:Person
    43 N19d8dfc13d3b49f2956ce9238390bcf2 schema:name IBM Research
    44 rdf:type schema:Organization
    45 N1f81a402dd6d43d1bf86076ec71ba42d schema:affiliation N19d8dfc13d3b49f2956ce9238390bcf2
    46 schema:familyName Bilgory
    47 schema:givenName Erez
    48 rdf:type schema:Person
    49 N3ef5f0398fc641ed80edca145cc20287 rdf:first N125a96763e044ba7b35ae87151b1b92d
    50 rdf:rest rdf:nil
    51 N4c70b3e7366c4efbbff75a9a592a5752 rdf:first N1f81a402dd6d43d1bf86076ec71ba42d
    52 rdf:rest Nde851f70a01a4cc0af34c8a0475b94a2
    53 N7c27eaf2cdd94616aec0ca65e42d6e32 schema:name readcube_id
    54 schema:value f566dc1c42a99afed708e3d1ae4cc1257eccd5bc0d1e30e1dcaa0bdaa375e7f2
    55 rdf:type schema:PropertyValue
    56 N9779a6a9abbb433f804a8457e76d611e schema:name Springer Nature - SN SciGraph project
    57 rdf:type schema:Organization
    58 N9a5c099e5e1243e1a83fde62fb1f0e61 schema:name IBM Research
    59 rdf:type schema:Organization
    60 Na64d11f6b7324eccb9f7a20f8e1feaac schema:location Cham
    61 schema:name Springer International Publishing
    62 rdf:type schema:Organisation
    63 Naacc36b9f9ca4359a65809be0512118d schema:isbn 978-3-319-66157-5
    64 978-3-319-66158-2
    65 schema:name Principles and Practice of Constraint Programming
    66 rdf:type schema:Book
    67 Nac4d5df22de84b12b89921ca15c60bfb schema:name doi
    68 schema:value 10.1007/978-3-319-66158-2_4
    69 rdf:type schema:PropertyValue
    70 Nca9d22884e6b424ca09a37261188dcc1 rdf:first sg:person.07506141212.88
    71 rdf:rest rdf:nil
    72 Nde2bb1bf38ea43979723bff0aa9ae095 schema:name IBM Research
    73 rdf:type schema:Organization
    74 Nde851f70a01a4cc0af34c8a0475b94a2 rdf:first sg:person.012172725707.55
    75 rdf:rest Nca9d22884e6b424ca09a37261188dcc1
    76 Ne2796b0cce344d0486b5f3629fea2ffe schema:name dimensions_id
    77 schema:value pub.1091295122
    78 rdf:type schema:PropertyValue
    79 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    80 schema:name Mathematical Sciences
    81 rdf:type schema:DefinedTerm
    82 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    83 schema:name Numerical and Computational Mathematics
    84 rdf:type schema:DefinedTerm
    85 sg:person.012172725707.55 schema:affiliation N9a5c099e5e1243e1a83fde62fb1f0e61
    86 schema:familyName Bin
    87 schema:givenName Eyal
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012172725707.55
    89 rdf:type schema:Person
    90 sg:person.07506141212.88 schema:affiliation Nde2bb1bf38ea43979723bff0aa9ae095
    91 schema:familyName Ziv
    92 schema:givenName Avi
    93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07506141212.88
    94 rdf:type schema:Person
    95 sg:pub.10.1007/3-540-60299-2_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022547214
    96 https://doi.org/10.1007/3-540-60299-2_6
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/978-3-319-18008-3_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037569377
    99 https://doi.org/10.1007/978-3-319-18008-3_26
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/978-3-319-63139-4_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090873063
    102 https://doi.org/10.1007/978-3-319-63139-4_4
    103 rdf:type schema:CreativeWork
    104 sg:pub.10.1007/978-3-540-45193-8_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043258167
    105 https://doi.org/10.1007/978-3-540-45193-8_26
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/978-3-540-45193-8_44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026556331
    108 https://doi.org/10.1007/978-3-540-45193-8_44
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/978-3-540-48085-3_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049879906
    111 https://doi.org/10.1007/978-3-540-48085-3_30
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/978-3-642-34188-5_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053130484
    114 https://doi.org/10.1007/978-3-642-34188-5_19
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1016/0004-3702(77)90007-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001107257
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1017/s0890060498124101 schema:sameAs https://app.dimensions.ai/details/publication/pub.1054081232
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1109/date.2012.6176425 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093555671
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1109/sp.2010.38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095176583
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1147/sj.413.0386 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063184710
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1613/jair.1335 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105579301
    127 rdf:type schema:CreativeWork
     




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


    ...