Ontology type: schema:Chapter Open Access: True
2008
AUTHORSHelmut Simonis , Barry O’Sullivan
ABSTRACTRectangle (square) packing problems involve packing all squares with sizes 1 ×1 to n ×n into the minimum area enclosing rectangle (respectively, square). Rectangle packing is a variant of an important problem in a variety of real-world settings. For example, in electronic design automation, the packing of blocks into a circuit layout is essentially a rectangle packing problem. Rectangle packing problems are also motivated by applications in scheduling. In this paper we demonstrate that an “off-the-shelf” constraint programming system, SICStus Prolog, outperforms recently developed ad-hoc approaches by over three orders of magnitude. We adopt the standard CP model for these problems, and study a variety of search strategies and improvements to solve large rectangle packing problems. As well as being over three orders of magnitude faster than the current state-of-the-art, we close eight open problems: two rectangle packing problems and six square packing problems. Our approach has other advantages over the state-of-the-art, such as being trivially modifiable to exploit multi-core computing platforms to parallelise search, although we use only a single-core in our experiments. We argue that rectangle packing is a domain where constraint programming significantly outperforms hand-crafted ad-hoc systems developed for this problem. This provides the CP community with a convincing success story. More... »
PAGES52-66
Principles and Practice of Constraint Programming
ISBN
978-3-540-85957-4
978-3-540-85958-1
http://scigraph.springernature.com/pub.10.1007/978-3-540-85958-1_4
DOIhttp://dx.doi.org/10.1007/978-3-540-85958-1_4
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1048223011
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/0803",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computer Software",
"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": {
"alternateName": "University College Cork",
"id": "https://www.grid.ac/institutes/grid.7872.a",
"name": [
"Cork Constraint Computation Centre Department of Computer Science, University College Cork, Ireland"
],
"type": "Organization"
},
"familyName": "Simonis",
"givenName": "Helmut",
"id": "sg:person.014003267235.39",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014003267235.39"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University College Cork",
"id": "https://www.grid.ac/institutes/grid.7872.a",
"name": [
"Cork Constraint Computation Centre Department of Computer Science, University College Cork, Ireland"
],
"type": "Organization"
},
"familyName": "O\u2019Sullivan",
"givenName": "Barry",
"id": "sg:person.013510130207.09",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013510130207.09"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/3-540-45578-7_26",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001313624",
"https://doi.org/10.1007/3-540-45578-7_26"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/1146909.1147188",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1010163630"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-74970-7_15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014217943",
"https://doi.org/10.1007/978-3-540-74970-7_15"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-74970-7_15",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1014217943",
"https://doi.org/10.1007/978-3-540-74970-7_15"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0895-7177(93)90068-a",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015146885"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0895-7177(94)90127-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1028829495"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-45578-7_27",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037262849",
"https://doi.org/10.1007/3-540-45578-7_27"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-68155-7_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044099116",
"https://doi.org/10.1007/978-3-540-68155-7_5"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-68155-7_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044099116",
"https://doi.org/10.1007/978-3-540-68155-7_5"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s1574-6526(06)80014-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053332799"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/aspdac.2007.357977",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095493765"
],
"type": "CreativeWork"
}
],
"datePublished": "2008",
"datePublishedReg": "2008-01-01",
"description": "Rectangle (square) packing problems involve packing all squares with sizes 1 \u00d71 to n \u00d7n into the minimum area enclosing rectangle (respectively, square). Rectangle packing is a variant of an important problem in a variety of real-world settings. For example, in electronic design automation, the packing of blocks into a circuit layout is essentially a rectangle packing problem. Rectangle packing problems are also motivated by applications in scheduling. In this paper we demonstrate that an \u201coff-the-shelf\u201d constraint programming system, SICStus Prolog, outperforms recently developed ad-hoc approaches by over three orders of magnitude. We adopt the standard CP model for these problems, and study a variety of search strategies and improvements to solve large rectangle packing problems. As well as being over three orders of magnitude faster than the current state-of-the-art, we close eight open problems: two rectangle packing problems and six square packing problems. Our approach has other advantages over the state-of-the-art, such as being trivially modifiable to exploit multi-core computing platforms to parallelise search, although we use only a single-core in our experiments. We argue that rectangle packing is a domain where constraint programming significantly outperforms hand-crafted ad-hoc systems developed for this problem. This provides the CP community with a convincing success story.",
"editor": [
{
"familyName": "Stuckey",
"givenName": "Peter J.",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-85958-1_4",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-540-85957-4",
"978-3-540-85958-1"
],
"name": "Principles and Practice of Constraint Programming",
"type": "Book"
},
"name": "Search Strategies for Rectangle Packing",
"pagination": "52-66",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-85958-1_4"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"e5ba67bb94148fa83fd24c9f9b03d1434fb31a1c652e660530d2dbfcba11fdc7"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1048223011"
]
}
],
"publisher": {
"location": "Berlin, Heidelberg",
"name": "Springer Berlin Heidelberg",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-85958-1_4",
"https://app.dimensions.ai/details/publication/pub.1048223011"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-16T06:09",
"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/0000000350_0000000350/records_77561_00000000.jsonl",
"type": "Chapter",
"url": "https://link.springer.com/10.1007%2F978-3-540-85958-1_4"
}
]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/978-3-540-85958-1_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-540-85958-1_4'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-85958-1_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-540-85958-1_4'
This table displays all metadata directly associated to this object as RDF triples.
103 TRIPLES
23 PREDICATES
36 URIs
20 LITERALS
8 BLANK NODES