Automatically Exploiting Subproblem Equivalence in Constraint Programming View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Geoffrey Chu , Maria Garcia de la Banda , Peter J. Stuckey

ABSTRACT

Many search problems contain large amounts of redundancy in the search. In this paper we examine how to automatically exploit remaining subproblem equivalence, which arises when two different search paths lead to identical remaining subproblems, that is the problem left on the remaining unfixed variables. Subproblem equivalence is exploited by caching descriptions, or keys, that define the subproblems visited, and failing the search when the key for the current subproblem already exists in the cache. In this paper we show how to automatically and efficiently define keys for arbitrary constraint problems. We show how a constraint programming solver with this capability can solve search problems where subproblem equivalence arises orders of magnitude faster. The system is fully automatic, i.e., the subproblem equivalences are detected and exploited without any effort from the problem modeller. More... »

PAGES

71-86

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-13520-0_10

DOI

http://dx.doi.org/10.1007/978-3-642-13520-0_10

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National ICT Australia, Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Australia", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "National ICT Australia, Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chu", 
        "givenName": "Geoffrey", 
        "id": "sg:person.013732020721.53", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013732020721.53"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Information Technology, Monash University, Australia", 
          "id": "http://www.grid.ac/institutes/grid.1002.3", 
          "name": [
            "Faculty of Information Technology, Monash University, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "de la Banda", 
        "givenName": "Maria Garcia", 
        "id": "sg:person.016350443307.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016350443307.93"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National ICT Australia, Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Australia", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "National ICT Australia, Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Stuckey", 
        "givenName": "Peter J.", 
        "id": "sg:person.012243374043.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012243374043.93"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Many search problems contain large amounts of redundancy in the search. In this paper we examine how to automatically exploit remaining subproblem equivalence, which arises when two different search paths lead to identical remaining subproblems, that is the problem left on the remaining unfixed variables. Subproblem equivalence is exploited by caching descriptions, or keys, that define the subproblems visited, and failing the search when the key for the current subproblem already exists in the cache. In this paper we show how to automatically and efficiently define keys for arbitrary constraint problems. We show how a constraint programming solver with this capability can solve search problems where subproblem equivalence arises orders of magnitude faster. The system is fully automatic, i.e., the subproblem equivalences are detected and exploited without any effort from the problem modeller.", 
    "editor": [
      {
        "familyName": "Lodi", 
        "givenName": "Andrea", 
        "type": "Person"
      }, 
      {
        "familyName": "Milano", 
        "givenName": "Michela", 
        "type": "Person"
      }, 
      {
        "familyName": "Toth", 
        "givenName": "Paolo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-13520-0_10", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-13519-4", 
        "978-3-642-13520-0"
      ], 
      "name": "Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems", 
      "type": "Book"
    }, 
    "keywords": [
      "search problem", 
      "different search paths", 
      "constraint programming solver", 
      "constraint programming", 
      "search path", 
      "programming solver", 
      "constraint problem", 
      "current subproblem", 
      "subproblems", 
      "large amount", 
      "key", 
      "cache", 
      "search", 
      "programming", 
      "redundancy", 
      "modelers", 
      "solver", 
      "capability", 
      "path", 
      "system", 
      "orders of magnitude", 
      "equivalence", 
      "order", 
      "description", 
      "efforts", 
      "amount", 
      "variables", 
      "magnitude", 
      "problem", 
      "paper"
    ], 
    "name": "Automatically Exploiting Subproblem Equivalence in Constraint Programming", 
    "pagination": "71-86", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041823055"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-13520-0_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-13520-0_10", 
      "https://app.dimensions.ai/details/publication/pub.1041823055"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:39", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_165.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-13520-0_10"
  }
]
 

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-642-13520-0_10'

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-642-13520-0_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-13520-0_10'

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-642-13520-0_10'


 

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

117 TRIPLES      23 PREDICATES      56 URIs      49 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-13520-0_10 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N3f44355c3ffc450c907fdee3674c69cb
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description Many search problems contain large amounts of redundancy in the search. In this paper we examine how to automatically exploit remaining subproblem equivalence, which arises when two different search paths lead to identical remaining subproblems, that is the problem left on the remaining unfixed variables. Subproblem equivalence is exploited by caching descriptions, or keys, that define the subproblems visited, and failing the search when the key for the current subproblem already exists in the cache. In this paper we show how to automatically and efficiently define keys for arbitrary constraint problems. We show how a constraint programming solver with this capability can solve search problems where subproblem equivalence arises orders of magnitude faster. The system is fully automatic, i.e., the subproblem equivalences are detected and exploited without any effort from the problem modeller.
7 schema:editor Nbd19faa6dd244c8f9606762c8a80f0e5
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N5208ed884f8148519700edf028f19471
12 schema:keywords amount
13 cache
14 capability
15 constraint problem
16 constraint programming
17 constraint programming solver
18 current subproblem
19 description
20 different search paths
21 efforts
22 equivalence
23 key
24 large amount
25 magnitude
26 modelers
27 order
28 orders of magnitude
29 paper
30 path
31 problem
32 programming
33 programming solver
34 redundancy
35 search
36 search path
37 search problem
38 solver
39 subproblems
40 system
41 variables
42 schema:name Automatically Exploiting Subproblem Equivalence in Constraint Programming
43 schema:pagination 71-86
44 schema:productId N3aeee481d52a4e94a42612b7d47f4e20
45 N93edffcd6ab1402ba170500f91152522
46 schema:publisher Nb0e787b9a4934857821278ca519ab2fc
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041823055
48 https://doi.org/10.1007/978-3-642-13520-0_10
49 schema:sdDatePublished 2022-05-10T10:39
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N7843a92e91d8419c82b59713f4f231b1
52 schema:url https://doi.org/10.1007/978-3-642-13520-0_10
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N082519140da841b4a689938b4fefd8df schema:familyName Lodi
57 schema:givenName Andrea
58 rdf:type schema:Person
59 N3aeee481d52a4e94a42612b7d47f4e20 schema:name doi
60 schema:value 10.1007/978-3-642-13520-0_10
61 rdf:type schema:PropertyValue
62 N3f44355c3ffc450c907fdee3674c69cb rdf:first sg:person.013732020721.53
63 rdf:rest Nbd9b0cd3524e482da0799246e977f880
64 N5208ed884f8148519700edf028f19471 schema:isbn 978-3-642-13519-4
65 978-3-642-13520-0
66 schema:name Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
67 rdf:type schema:Book
68 N5b17ebfa56cd494f87445f80847ef38a rdf:first sg:person.012243374043.93
69 rdf:rest rdf:nil
70 N706a30573424438a963f9dc0c91f8b88 schema:familyName Milano
71 schema:givenName Michela
72 rdf:type schema:Person
73 N72206dc819784261967c5f8019ddc46a schema:familyName Toth
74 schema:givenName Paolo
75 rdf:type schema:Person
76 N7843a92e91d8419c82b59713f4f231b1 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 N93edffcd6ab1402ba170500f91152522 schema:name dimensions_id
79 schema:value pub.1041823055
80 rdf:type schema:PropertyValue
81 Nb0e787b9a4934857821278ca519ab2fc schema:name Springer Nature
82 rdf:type schema:Organisation
83 Nbd19faa6dd244c8f9606762c8a80f0e5 rdf:first N082519140da841b4a689938b4fefd8df
84 rdf:rest Nd9406ce5ac7a4a6380b7d98dac3537ba
85 Nbd9b0cd3524e482da0799246e977f880 rdf:first sg:person.016350443307.93
86 rdf:rest N5b17ebfa56cd494f87445f80847ef38a
87 Nd9406ce5ac7a4a6380b7d98dac3537ba rdf:first N706a30573424438a963f9dc0c91f8b88
88 rdf:rest Nd977048af4c3417887bab04b47ca872c
89 Nd977048af4c3417887bab04b47ca872c rdf:first N72206dc819784261967c5f8019ddc46a
90 rdf:rest rdf:nil
91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
92 schema:name Information and Computing Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
95 schema:name Artificial Intelligence and Image Processing
96 rdf:type schema:DefinedTerm
97 sg:person.012243374043.93 schema:affiliation grid-institutes:None
98 schema:familyName Stuckey
99 schema:givenName Peter J.
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012243374043.93
101 rdf:type schema:Person
102 sg:person.013732020721.53 schema:affiliation grid-institutes:None
103 schema:familyName Chu
104 schema:givenName Geoffrey
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013732020721.53
106 rdf:type schema:Person
107 sg:person.016350443307.93 schema:affiliation grid-institutes:grid.1002.3
108 schema:familyName de la Banda
109 schema:givenName Maria Garcia
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016350443307.93
111 rdf:type schema:Person
112 grid-institutes:None schema:alternateName National ICT Australia, Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Australia
113 schema:name National ICT Australia, Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Australia
114 rdf:type schema:Organization
115 grid-institutes:grid.1002.3 schema:alternateName Faculty of Information Technology, Monash University, Australia
116 schema:name Faculty of Information Technology, Monash University, Australia
117 rdf:type schema:Organization
 




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


...