Exploiting subproblem dominance in constraint programming View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2011-11-16

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 subproblem dominance, which arises when different partial assignments lead to subproblems that dominate (or are dominated by) other subproblems. Subproblem dominance is exploited by caching subproblems that have already been explored by the search, using keys that characterise the subproblems, and failing the search when the current subproblem is dominated by a subproblem already in the cache. In this paper we show how we can automatically and efficiently define keys for arbitrary constraint problems using constraint projection. We show how, for search problems where subproblem dominance arises, a constraint programming solver with this capability can solve these problems orders of magnitude faster than solvers without caching. The system is fully automatic, i.e., subproblem dominance is detected and exploited without any effort from the problem modeller. More... »

PAGES

1-38

References to SciGraph publications

  • 2009. Minimizing the Maximum Number of Open Stacks by Customer Search in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2009
  • 2005. Conditional Symmetry Breaking in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2005
  • 2001-11-19. Symmetry Breaking in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING — CP 2001
  • 2007-01-01. MiniZinc: Towards a Standard CP Modelling Language in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP 2007
  • 2009-01-13. Propagation via lazy clause generation in CONSTRAINTS
  • 2007. Minimum Cardinality Matrix Decomposition into Consecutive-Ones Matrices: CP and IP Approaches in INTEGRATION OF AI AND OR TECHNIQUES IN CONSTRAINT PROGRAMMING FOR COMBINATORIAL OPTIMIZATION PROBLEMS
  • 2005. Caching Search States in Permutation Problems in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2005
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10601-011-9112-9

    DOI

    http://dx.doi.org/10.1007/s10601-011-9112-9

    DIMENSIONS

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


    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, Melbourne, Australia", 
              "id": "http://www.grid.ac/institutes/grid.1008.9", 
              "name": [
                "National ICT Australia, Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, 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, Clayton, VIC, Australia", 
              "id": "http://www.grid.ac/institutes/grid.1002.3", 
              "name": [
                "Faculty of Information Technology, Monash University, Clayton, VIC, 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, Melbourne, Australia", 
              "id": "http://www.grid.ac/institutes/grid.1008.9", 
              "name": [
                "National ICT Australia, Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, 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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-04244-7_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015606224", 
              "https://doi.org/10.1007/978-3-642-04244-7_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11564751_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024106920", 
              "https://doi.org/10.1007/11564751_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10601-008-9064-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023375712", 
              "https://doi.org/10.1007/s10601-008-9064-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-72397-4_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036995026", 
              "https://doi.org/10.1007/978-3-540-72397-4_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45578-7_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016356066", 
              "https://doi.org/10.1007/3-540-45578-7_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74970-7_38", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007007409", 
              "https://doi.org/10.1007/978-3-540-74970-7_38"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11564751_47", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034029350", 
              "https://doi.org/10.1007/11564751_47"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2011-11-16", 
        "datePublishedReg": "2011-11-16", 
        "description": "Many search problems contain large amounts of redundancy in the search. In this paper we examine how to automatically exploit subproblem dominance, which arises when different partial assignments lead to subproblems that dominate (or are dominated by) other subproblems. Subproblem dominance is exploited by caching subproblems that have already been explored by the search, using keys that characterise the subproblems, and failing the search when the current subproblem is dominated by a subproblem already in the cache. In this paper we show how we can automatically and efficiently define keys for arbitrary constraint problems using constraint projection. We show how, for search problems where subproblem dominance arises, a constraint programming solver with this capability can solve these problems orders of magnitude faster than solvers without caching. The system is fully automatic, i.e., subproblem dominance is detected and exploited without any effort from the problem modeller.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10601-011-9112-9", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1043977", 
            "issn": [
              "1383-7133", 
              "1572-9354"
            ], 
            "name": "Constraints", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "17"
          }
        ], 
        "keywords": [
          "search problem", 
          "constraint programming solver", 
          "constraint programming", 
          "programming solver", 
          "constraint problem", 
          "current subproblem", 
          "constraint projection", 
          "subproblems", 
          "problem orders", 
          "large amount", 
          "solver", 
          "search", 
          "partial assignment", 
          "key", 
          "cache", 
          "programming", 
          "redundancy", 
          "modelers", 
          "capability", 
          "system", 
          "assignment", 
          "order", 
          "efforts", 
          "projections", 
          "amount", 
          "magnitude", 
          "dominance", 
          "problem", 
          "paper"
        ], 
        "name": "Exploiting subproblem dominance in constraint programming", 
        "pagination": "1-38", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1033563204"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10601-011-9112-9"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10601-011-9112-9", 
          "https://app.dimensions.ai/details/publication/pub.1033563204"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:27", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_538.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10601-011-9112-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-011-9112-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-011-9112-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10601-011-9112-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-011-9112-9'


     

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

    132 TRIPLES      22 PREDICATES      61 URIs      46 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10601-011-9112-9 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Ncdf8e772ae024e1f90501b6c69bee7a2
    4 schema:citation sg:pub.10.1007/11564751_21
    5 sg:pub.10.1007/11564751_47
    6 sg:pub.10.1007/3-540-45578-7_7
    7 sg:pub.10.1007/978-3-540-72397-4_1
    8 sg:pub.10.1007/978-3-540-74970-7_38
    9 sg:pub.10.1007/978-3-642-04244-7_21
    10 sg:pub.10.1007/s10601-008-9064-x
    11 schema:datePublished 2011-11-16
    12 schema:datePublishedReg 2011-11-16
    13 schema:description Many search problems contain large amounts of redundancy in the search. In this paper we examine how to automatically exploit subproblem dominance, which arises when different partial assignments lead to subproblems that dominate (or are dominated by) other subproblems. Subproblem dominance is exploited by caching subproblems that have already been explored by the search, using keys that characterise the subproblems, and failing the search when the current subproblem is dominated by a subproblem already in the cache. In this paper we show how we can automatically and efficiently define keys for arbitrary constraint problems using constraint projection. We show how, for search problems where subproblem dominance arises, a constraint programming solver with this capability can solve these problems orders of magnitude faster than solvers without caching. The system is fully automatic, i.e., subproblem dominance is detected and exploited without any effort from the problem modeller.
    14 schema:genre article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree false
    17 schema:isPartOf N11c8d145b1c1496789a4676aaec78866
    18 Nfb0526bb685745d2b0c986995236c3e0
    19 sg:journal.1043977
    20 schema:keywords amount
    21 assignment
    22 cache
    23 capability
    24 constraint problem
    25 constraint programming
    26 constraint programming solver
    27 constraint projection
    28 current subproblem
    29 dominance
    30 efforts
    31 key
    32 large amount
    33 magnitude
    34 modelers
    35 order
    36 paper
    37 partial assignment
    38 problem
    39 problem orders
    40 programming
    41 programming solver
    42 projections
    43 redundancy
    44 search
    45 search problem
    46 solver
    47 subproblems
    48 system
    49 schema:name Exploiting subproblem dominance in constraint programming
    50 schema:pagination 1-38
    51 schema:productId Nacb95713be4746eeb1684c14e1242801
    52 Nec565de77b0d41f1b7c77f77173c37fc
    53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033563204
    54 https://doi.org/10.1007/s10601-011-9112-9
    55 schema:sdDatePublished 2022-05-20T07:27
    56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    57 schema:sdPublisher N135548d4b4dc40c5b48e7024c137cd36
    58 schema:url https://doi.org/10.1007/s10601-011-9112-9
    59 sgo:license sg:explorer/license/
    60 sgo:sdDataset articles
    61 rdf:type schema:ScholarlyArticle
    62 N11c8d145b1c1496789a4676aaec78866 schema:volumeNumber 17
    63 rdf:type schema:PublicationVolume
    64 N135548d4b4dc40c5b48e7024c137cd36 schema:name Springer Nature - SN SciGraph project
    65 rdf:type schema:Organization
    66 N341d67d6e3ad497292d02f0c33d980c2 rdf:first sg:person.012243374043.93
    67 rdf:rest rdf:nil
    68 N54a11fcfae3a48e8822d6b98d72fa92a rdf:first sg:person.016350443307.93
    69 rdf:rest N341d67d6e3ad497292d02f0c33d980c2
    70 Nacb95713be4746eeb1684c14e1242801 schema:name doi
    71 schema:value 10.1007/s10601-011-9112-9
    72 rdf:type schema:PropertyValue
    73 Ncdf8e772ae024e1f90501b6c69bee7a2 rdf:first sg:person.013732020721.53
    74 rdf:rest N54a11fcfae3a48e8822d6b98d72fa92a
    75 Nec565de77b0d41f1b7c77f77173c37fc schema:name dimensions_id
    76 schema:value pub.1033563204
    77 rdf:type schema:PropertyValue
    78 Nfb0526bb685745d2b0c986995236c3e0 schema:issueNumber 1
    79 rdf:type schema:PublicationIssue
    80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Information and Computing Sciences
    82 rdf:type schema:DefinedTerm
    83 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    84 schema:name Artificial Intelligence and Image Processing
    85 rdf:type schema:DefinedTerm
    86 sg:journal.1043977 schema:issn 1383-7133
    87 1572-9354
    88 schema:name Constraints
    89 schema:publisher Springer Nature
    90 rdf:type schema:Periodical
    91 sg:person.012243374043.93 schema:affiliation grid-institutes:grid.1008.9
    92 schema:familyName Stuckey
    93 schema:givenName Peter J.
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012243374043.93
    95 rdf:type schema:Person
    96 sg:person.013732020721.53 schema:affiliation grid-institutes:grid.1008.9
    97 schema:familyName Chu
    98 schema:givenName Geoffrey
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013732020721.53
    100 rdf:type schema:Person
    101 sg:person.016350443307.93 schema:affiliation grid-institutes:grid.1002.3
    102 schema:familyName de la Banda
    103 schema:givenName Maria Garcia
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016350443307.93
    105 rdf:type schema:Person
    106 sg:pub.10.1007/11564751_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024106920
    107 https://doi.org/10.1007/11564751_21
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/11564751_47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034029350
    110 https://doi.org/10.1007/11564751_47
    111 rdf:type schema:CreativeWork
    112 sg:pub.10.1007/3-540-45578-7_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016356066
    113 https://doi.org/10.1007/3-540-45578-7_7
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/978-3-540-72397-4_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036995026
    116 https://doi.org/10.1007/978-3-540-72397-4_1
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/978-3-540-74970-7_38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007007409
    119 https://doi.org/10.1007/978-3-540-74970-7_38
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/978-3-642-04244-7_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015606224
    122 https://doi.org/10.1007/978-3-642-04244-7_21
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/s10601-008-9064-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1023375712
    125 https://doi.org/10.1007/s10601-008-9064-x
    126 rdf:type schema:CreativeWork
    127 grid-institutes:grid.1002.3 schema:alternateName Faculty of Information Technology, Monash University, Clayton, VIC, Australia
    128 schema:name Faculty of Information Technology, Monash University, Clayton, VIC, Australia
    129 rdf:type schema:Organization
    130 grid-institutes:grid.1008.9 schema:alternateName National ICT Australia, Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Melbourne, Australia
    131 schema:name National ICT Australia, Victoria Laboratory, Department of Computer Science and Software Engineering, University of Melbourne, Melbourne, Australia
    132 rdf:type schema:Organization
     




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


    ...