New Inequalities for 1D Relaxations of the 2D Rectangular Strip Packing Problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

New Inequalities for 1D Relaxations of the 2D Rectangular Strip Packing Problem

  • Conference paper
  • First Online:
Operations Research Proceedings 2014

Part of the book series: Operations Research Proceedings ((ORP))

Abstract

We investigate a heuristic for the two-dimensional rectangular strip packing problem that constructs a feasible two-dimensional packing by placing one-dimensional cutting patterns obtained by solving the horizontal one-dimensional bar relaxation. To represent a solution of the strip packing problem, a solution of a horizontal bar relaxation has to satisfy, among others, the vertical contiguous condition. To strengthen the one-dimensional horizontal bar relaxation with respect to that vertical contiguity new inequalities are formulated. Some computational results are also reported.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 17159
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 21449
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Alvarez-Valdez, R., Parreño, F., Tamarit, J.M.: Reactive grasp for the strip-packing problem. Comput. Oper. Res. 35, 1065–1083 (2008)

    Article  Google Scholar 

  2. Belov, G., Scheithauer, G., Mukhacheva, E.A.: One-dimensional heuristic adapted for two-dimensional rectangular strip packing. J. Oper. Soc. 59, 823–832 (2008)

    Article  Google Scholar 

  3. Bortfeld, A.: A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. Eur. J. Oper. Res. 172, 814–837 (2006)

    Article  Google Scholar 

  4. Friedow, I.: LP-basierte Heuristiken zur Lösung des Streifenpackproblems. Diploma thesis Technical University of Dresden (2012)

    Google Scholar 

  5. Hopper, E.: Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods. Ph.D. thesis University of Wales, Cardiff School of Engineering (2000)

    Google Scholar 

  6. Lim, A., Oon, W., Wei, L., Zhu, W.: A skyline heuristic for the 2D rectangular packing and strip packing problems. Eur. J. Oper. Res. 215, 337–346 (2011)

    Google Scholar 

  7. Lodi, A., Martello, S., Monaci, M.: Two-dimensional packing problems—a survey. Eur. J. Oper. Res. 141, 241–252 (2002)

    Article  Google Scholar 

  8. Scheithauer, G.: LP-based bounds for the container and multi-container loading problem. Int. Trans. Oper. Res. 6, 199–213 (1999)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Numerical Mathematics, Technical University of Dresden, Dresden, Germany

    Isabel Friedow & Guntram Scheithauer

Authors
  1. Isabel Friedow
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guntram Scheithauer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Isabel Friedow or Guntram Scheithauer .

Editor information

Editors and Affiliations

  1. Operations Research, RWTH Aachen University, Aachen, Germany

    Marco Lübbecke

  2. Lehrstuhl II für Mathematik, RWTH Aachen University, Aachen, Germany

    Arie Koster

  3. RWTH Aachen University, Aachen, Nordrhein-Westfalen, Germany

    Peter Letmathe

  4. E.ON Energy Research Center, RWTH Aachen University, Aachen, Nordrhein-Westfalen, Germany

    Reinhard Madlener

  5. Management Science, RWTH Aachen University, Aachen, Nordrhein-Westfalen, Germany

    Britta Peis

  6. Chair of Operations Management, RWTH Aachen University, Aachen, Germany

    Grit Walther

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Friedow, I., Scheithauer, G. (2016). New Inequalities for 1D Relaxations of the 2D Rectangular Strip Packing Problem. In: Lübbecke, M., Koster, A., Letmathe, P., Madlener, R., Peis, B., Walther, G. (eds) Operations Research Proceedings 2014. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-28697-6_22

Download citation

Publish with us

Policies and ethics