IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v258y2017i2d10.1007_s10479-016-2112-9.html
   My bibliography  Save this article

Symmetry breaking for generalized disjunctive programming formulation of the strip packing problem

Author

Listed:
  • Francisco Trespalacios

    (Carnegie Mellon University)

  • Ignacio E. Grossmann

    (Carnegie Mellon University)

Abstract

In this work we present a new generalized disjunctive programming (GDP) formulation for the strip packing problem. The new formulation helps to break some of the symmetry that arises in this problem. The new formulation is further improved for the case in which the heights and lengths of the rectangles are integer numbers. The GDP model can be formulated and solved as a mixed-integer linear programming (MILP) model, using different GDP-to-MILP reformulations. The results show that the MILP reformulations of the new GDP model (and its improvement for rectangles with integer heights and widths) can be solved faster than the previously proposed GDP formulation.

Suggested Citation

  • Francisco Trespalacios & Ignacio E. Grossmann, 2017. "Symmetry breaking for generalized disjunctive programming formulation of the strip packing problem," Annals of Operations Research, Springer, vol. 258(2), pages 747-759, November.
    • Handle: RePEc:spr:annopr:v:258:y:2017:i:2:d:10.1007_s10479-016-2112-9
    DOI: 10.1007/s10479-016-2112-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-016-2112-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-016-2112-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Wascher, Gerhard & Hau[ss]ner, Heike & Schumann, Holger, 2007. "An improved typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1109-1130, December.
    2. Andrea Lodi & Silvano Martello & Daniele Vigo, 1999. "Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 345-357, November.
    3. Lodi, Andrea & Martello, Silvano & Monaci, Michele, 2002. "Two-dimensional packing problems: A survey," European Journal of Operational Research, Elsevier, vol. 141(2), pages 241-252, September.
    4. Castro, Pedro M. & Oliveira, José F., 2011. "Scheduling inspired models for two-dimensional packing problems," European Journal of Operational Research, Elsevier, vol. 215(1), pages 45-56, November.
    5. Silvano Martello & Michele Monaci & Daniele Vigo, 2003. "An Exact Approach to the Strip-Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 310-319, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
    2. Leung, Stephen C.H. & Zhang, Defu & Sim, Kwang Mong, 2011. "A two-stage intelligent search algorithm for the two-dimensional strip packing problem," European Journal of Operational Research, Elsevier, vol. 215(1), pages 57-69, November.
    3. Önder Aşık & Ender Özcan, 2009. "Bidirectional best-fit heuristic for orthogonal rectangular strip packing," Annals of Operations Research, Springer, vol. 172(1), pages 405-427, November.
    4. Defu Zhang & Lijun Wei & Stephen C. H. Leung & Qingshan Chen, 2013. "A Binary Search Heuristic Algorithm Based on Randomized Local Search for the Rectangular Strip-Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 332-345, May.
    5. Gardeyn, Jeroen & Wauters, Tony, 2022. "A goal-driven ruin and recreate heuristic for the 2D variable-sized bin packing problem with guillotine constraints," European Journal of Operational Research, Elsevier, vol. 301(2), pages 432-444.
    6. Ortmann, Frank G. & Ntene, Nthabiseng & van Vuuren, Jan H., 2010. "New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems," European Journal of Operational Research, Elsevier, vol. 203(2), pages 306-315, June.
    7. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2021. "Queue-constrained packing: A vehicle ferry case study," European Journal of Operational Research, Elsevier, vol. 289(2), pages 727-741.
    8. Andreas Bortfeldt & Sabine Jungmann, 2012. "A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint," Annals of Operations Research, Springer, vol. 196(1), pages 53-71, July.
    9. Kenmochi, Mitsutoshi & Imamichi, Takashi & Nonobe, Koji & Yagiura, Mutsunori & Nagamochi, Hiroshi, 2009. "Exact algorithms for the two-dimensional strip packing problem with and without rotations," European Journal of Operational Research, Elsevier, vol. 198(1), pages 73-83, October.
    10. Clautiaux, Francois & Carlier, Jacques & Moukrim, Aziz, 2007. "A new exact method for the two-dimensional orthogonal packing problem," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1196-1211, December.
    11. Nestor M Cid-Garcia & Yasmin A Rios-Solis, 2020. "Positions and covering: A two-stage methodology to obtain optimal solutions for the 2d-bin packing problem," PLOS ONE, Public Library of Science, vol. 15(4), pages 1-22, April.
    12. Polyakovsky, Sergey & M'Hallah, Rym, 2009. "An agent-based approach to the two-dimensional guillotine bin packing problem," European Journal of Operational Research, Elsevier, vol. 192(3), pages 767-781, February.
    13. Kaizhi Chen & Jiahao Zhuang & Shangping Zhong & Song Zheng, 2020. "Optimization Method for Guillotine Packing of Rectangular Items within an Irregular and Defective Slate," Mathematics, MDPI, vol. 8(11), pages 1-16, November.
    14. Eduardo Segredo & Carlos Segura & Coromoto León, 2014. "Memetic algorithms and hyperheuristics applied to a multiobjectivised two-dimensional packing problem," Journal of Global Optimization, Springer, vol. 58(4), pages 769-794, April.
    15. Bennell, Julia A. & Soon Lee, Lai & Potts, Chris N., 2013. "A genetic algorithm for two-dimensional bin packing with due dates," International Journal of Production Economics, Elsevier, vol. 145(2), pages 547-560.
    16. Wei, Lijun & Oon, Wee-Chong & Zhu, Wenbin & Lim, Andrew, 2013. "A goal-driven approach to the 2D bin packing and variable-sized bin packing problems," European Journal of Operational Research, Elsevier, vol. 224(1), pages 110-121.
    17. Toledo, Franklina M.B. & Carravilla, Maria Antónia & Ribeiro, Cristina & Oliveira, José F. & Gomes, A. Miguel, 2013. "The Dotted-Board Model: A new MIP model for nesting irregular shapes," International Journal of Production Economics, Elsevier, vol. 145(2), pages 478-487.
    18. Defu Zhang & Yuxin Che & Furong Ye & Yain-Whar Si & Stephen C. H. Leung, 2016. "A hybrid algorithm based on variable neighbourhood for the strip packing problem," Journal of Combinatorial Optimization, Springer, vol. 32(2), pages 513-530, August.
    19. Jean-François Côté & Mohamed Haouari & Manuel Iori, 2021. "Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 963-978, July.
    20. Li, Xueping & Zhang, Kaike, 2018. "Single batch processing machine scheduling with two-dimensional bin packing constraints," International Journal of Production Economics, Elsevier, vol. 196(C), pages 113-121.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:258:y:2017:i:2:d:10.1007_s10479-016-2112-9. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.