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 N7bc2c95823c141429993117b68f0f6d2
    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 Nab242cbe885d4db49157e163387d6ea6
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf N6f4a605d1bf04488b1ce1b067a935812
    21 schema:name Search Strategies for Rectangle Packing
    22 schema:pagination 52-66
    23 schema:productId Nb0cf585f66c14f71b4bfccf6cea67c3b
    24 Nb8006c8e66cc47b5841ada5ec894f674
    25 Nf516695853db4c0c9465c05259ab8a10
    26 schema:publisher Nc031ea487fd94605a2b0b838e9a59e25
    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 Ne2e3c978ade84c6a88fc957292025951
    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 N6f4a605d1bf04488b1ce1b067a935812 schema:isbn 978-3-540-85957-4
    37 978-3-540-85958-1
    38 schema:name Principles and Practice of Constraint Programming
    39 rdf:type schema:Book
    40 N7bc2c95823c141429993117b68f0f6d2 rdf:first sg:person.014003267235.39
    41 rdf:rest Nbb201aabdef34e9baaee8794965cb24c
    42 Nab242cbe885d4db49157e163387d6ea6 rdf:first Nfaf0616763e345a38f5a7a684fc93072
    43 rdf:rest rdf:nil
    44 Nb0cf585f66c14f71b4bfccf6cea67c3b schema:name dimensions_id
    45 schema:value pub.1048223011
    46 rdf:type schema:PropertyValue
    47 Nb8006c8e66cc47b5841ada5ec894f674 schema:name doi
    48 schema:value 10.1007/978-3-540-85958-1_4
    49 rdf:type schema:PropertyValue
    50 Nbb201aabdef34e9baaee8794965cb24c rdf:first sg:person.013510130207.09
    51 rdf:rest rdf:nil
    52 Nc031ea487fd94605a2b0b838e9a59e25 schema:location Berlin, Heidelberg
    53 schema:name Springer Berlin Heidelberg
    54 rdf:type schema:Organisation
    55 Ne2e3c978ade84c6a88fc957292025951 schema:name Springer Nature - SN SciGraph project
    56 rdf:type schema:Organization
    57 Nf516695853db4c0c9465c05259ab8a10 schema:name readcube_id
    58 schema:value e5ba67bb94148fa83fd24c9f9b03d1434fb31a1c652e660530d2dbfcba11fdc7
    59 rdf:type schema:PropertyValue
    60 Nfaf0616763e345a38f5a7a684fc93072 schema:familyName Stuckey
    61 schema:givenName Peter J.
    62 rdf:type schema:Person
    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)


    ...