Ontology type: schema:ScholarlyArticle
2011-11-16
AUTHORSGeoffrey Chu, Maria Garcia de la Banda, Peter J. Stuckey
ABSTRACTMany 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... »
PAGES1-38
http://scigraph.springernature.com/pub.10.1007/s10601-011-9112-9
DOIhttp://dx.doi.org/10.1007/s10601-011-9112-9
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1033563204
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
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