Search Strategies for Rectangle Packing View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Helmut Simonis , Barry O’Sullivan

ABSTRACT

Rectangle (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... »

PAGES

52-66

References to SciGraph publications

  • 2008. New Filtering for the Constraint in the Context of Non-Overlapping Rectangles in INTEGRATION OF AI AND OR TECHNIQUES IN CONSTRAINT PROGRAMMING FOR COMBINATORIAL OPTIMIZATION PROBLEMS
  • 2007. A Generic Geometrical Constraint Kernel in Space and Time for Handling Polymorphic k-Dimensional Objects in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING – CP 2007
  • 2001. Sweep as a Generic Pruning Technique Applied to the Non-overlapping Rectangles Constraint in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING — CP 2001
  • 2001. Non-overlapping Constraints between Convex Polytopes in PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING — CP 2001
  • Book

    TITLE

    Principles and Practice of Constraint Programming

    ISBN

    978-3-540-85957-4
    978-3-540-85958-1

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-85958-1_4

    DOI

    http://dx.doi.org/10.1007/978-3-540-85958-1_4

    DIMENSIONS

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


    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/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

    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-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

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-85958-1_4 schema:about anzsrc-for:08
    2 anzsrc-for:0803
    3 schema:author N3040398263ca483a9e1df866c1734c9e
    4 schema:citation sg:pub.10.1007/3-540-45578-7_26
    5 sg:pub.10.1007/3-540-45578-7_27
    6 sg:pub.10.1007/978-3-540-68155-7_5
    7 sg:pub.10.1007/978-3-540-74970-7_15
    8 https://doi.org/10.1016/0895-7177(93)90068-a
    9 https://doi.org/10.1016/0895-7177(94)90127-9
    10 https://doi.org/10.1016/s1574-6526(06)80014-3
    11 https://doi.org/10.1109/aspdac.2007.357977
    12 https://doi.org/10.1145/1146909.1147188
    13 schema:datePublished 2008
    14 schema:datePublishedReg 2008-01-01
    15 schema:description Rectangle (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.
    16 schema:editor N1070557644974cebb42dd20350a0b452
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf N3e2d75823b8a49bead3b77580478d73a
    21 schema:name Search Strategies for Rectangle Packing
    22 schema:pagination 52-66
    23 schema:productId N3155dda561d1455b819983426a55e765
    24 N378be8f5b600449a8b1f62483e6fd9f5
    25 N5e4f4becec84477dbaf14d04b07f0a13
    26 schema:publisher N226d96ba07d74b588290223b952399a1
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048223011
    28 https://doi.org/10.1007/978-3-540-85958-1_4
    29 schema:sdDatePublished 2019-04-16T06:09
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N4093844d213e4a35ac384de717d18af2
    32 schema:url https://link.springer.com/10.1007%2F978-3-540-85958-1_4
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N1070557644974cebb42dd20350a0b452 rdf:first Ncdca9fab583d4eb088b1f2577cbbe387
    37 rdf:rest rdf:nil
    38 N226d96ba07d74b588290223b952399a1 schema:location Berlin, Heidelberg
    39 schema:name Springer Berlin Heidelberg
    40 rdf:type schema:Organisation
    41 N3040398263ca483a9e1df866c1734c9e rdf:first sg:person.014003267235.39
    42 rdf:rest Ne48c97079c4e4bbcb32ccdba4c25b6e4
    43 N3155dda561d1455b819983426a55e765 schema:name dimensions_id
    44 schema:value pub.1048223011
    45 rdf:type schema:PropertyValue
    46 N378be8f5b600449a8b1f62483e6fd9f5 schema:name doi
    47 schema:value 10.1007/978-3-540-85958-1_4
    48 rdf:type schema:PropertyValue
    49 N3e2d75823b8a49bead3b77580478d73a schema:isbn 978-3-540-85957-4
    50 978-3-540-85958-1
    51 schema:name Principles and Practice of Constraint Programming
    52 rdf:type schema:Book
    53 N4093844d213e4a35ac384de717d18af2 schema:name Springer Nature - SN SciGraph project
    54 rdf:type schema:Organization
    55 N5e4f4becec84477dbaf14d04b07f0a13 schema:name readcube_id
    56 schema:value e5ba67bb94148fa83fd24c9f9b03d1434fb31a1c652e660530d2dbfcba11fdc7
    57 rdf:type schema:PropertyValue
    58 Ncdca9fab583d4eb088b1f2577cbbe387 schema:familyName Stuckey
    59 schema:givenName Peter J.
    60 rdf:type schema:Person
    61 Ne48c97079c4e4bbcb32ccdba4c25b6e4 rdf:first sg:person.013510130207.09
    62 rdf:rest rdf:nil
    63 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    64 schema:name Information and Computing Sciences
    65 rdf:type schema:DefinedTerm
    66 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Computer Software
    68 rdf:type schema:DefinedTerm
    69 sg:person.013510130207.09 schema:affiliation https://www.grid.ac/institutes/grid.7872.a
    70 schema:familyName O’Sullivan
    71 schema:givenName Barry
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013510130207.09
    73 rdf:type schema:Person
    74 sg:person.014003267235.39 schema:affiliation https://www.grid.ac/institutes/grid.7872.a
    75 schema:familyName Simonis
    76 schema:givenName Helmut
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014003267235.39
    78 rdf:type schema:Person
    79 sg:pub.10.1007/3-540-45578-7_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001313624
    80 https://doi.org/10.1007/3-540-45578-7_26
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/3-540-45578-7_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037262849
    83 https://doi.org/10.1007/3-540-45578-7_27
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/978-3-540-68155-7_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044099116
    86 https://doi.org/10.1007/978-3-540-68155-7_5
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/978-3-540-74970-7_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014217943
    89 https://doi.org/10.1007/978-3-540-74970-7_15
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1016/0895-7177(93)90068-a schema:sameAs https://app.dimensions.ai/details/publication/pub.1015146885
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1016/0895-7177(94)90127-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028829495
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1016/s1574-6526(06)80014-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053332799
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1109/aspdac.2007.357977 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095493765
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1145/1146909.1147188 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010163630
    100 rdf:type schema:CreativeWork
    101 https://www.grid.ac/institutes/grid.7872.a schema:alternateName University College Cork
    102 schema:name Cork Constraint Computation Centre Department of Computer Science, University College Cork, Ireland
    103 rdf:type schema:Organization
     




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


    ...