Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

Cutting & Packing
(cooperation with Lodestar GmbH)

cutting_example(Raidl, Dusberger)

Cutting and packing problems occur in a multitude of industrial or other real-world applications such as

  • glass, paper and steel cutting,
  • container or pallet loading,
  • VLSI design,
  • and many other applications.

Usually items have to be cut from raw material and waste should be minimized, or the number of bins/containers needed to pack given items has to be minimized. In our research we dealt (until now) with two-dimensional bin packing problems where only guillotineable cutting/packing patterns are allowed.

Another kind of packing problems are the so called Knapsack Problems. Where items with an associated profit have to be packed into one or more knapsacks, and the profit has to be maximized. There are several variants of knapsack problems, such as the classical knapsack problem, multiconstrained knapsack problems, multiple knapsack problems, and many others. In our research we mainly deal with multiconstrained knapsack problems.

Solving cutting and packing problems can be done in various ways, we developed metaheuristics and exact algorithms for dealing with those problems. Especially the combination of evolutionary algorithms with problem specific heuristics, local and global optimization techniques are considered. Please see also our page on metaheuristics and evolutionary computation and the page on hybrid optimization techniques.

Some of our Recent Publications Related to Cutting and Packing


4 results
2018
[4]Solving a Weighted Set Covering Problem for Improving Algorithms for Cutting Stock Problems with Setup Costs by Solution Merging
Benedikt Klocker, Günther R Raidl
Computer Aided Systems Theory – EUROCAST 2017, Part I (Roberto Moreno-Díaz, Franz Pichler, Alexis Quesada-Arencibia, eds.), volume 10671 of LNCS, pages 355-363, 2018, Springer.
[bibtex] [pdf]
2015
[3]A Value-Correction Construction Heuristic for the Two-Dimensional Cutting Stock Problem with Variable Sheet Size
Frederico Dusberger, Günther R. Raidl
Extended Abstracts of the Fifthteenth International Conference on Computer Aided Systems Theory (EUROCAST 2015) (Alexis Quesada-Arencibia, José Carlos Rodriguez, Roberto Moreno-Díaz jr., Roberto Moreno-Díaz, eds.), pages 109–110, 2015.
[bibtex] [pdf]
[2]Solving the 3-Staged 2-Dimensional Cutting Stock Problem by Dynamic Programming and Variable Neighborhood Search
Frederico Dusberger, Günther R. Raidl
The 3rd International Conference on Variable Neighborhood Search (VNS'14), volume 47 of Electronic Notes in Discrete Mathematics, pages 133–140, 2015, Elsevier.
[bibtex] [pdf]
2014
[1]A Variable Neighborhood Search Using Very Large Neighborhood Structures for the 3-Staged 2-Dimensional Cutting Stock Problem
Frederico Dusberger, Günther R. Raidl
Hybrid Metaheuristics, 9th Int. Workshop, HM 2014 (Maria J. Blesa, Christain Blum, Stefan Voß, eds.), volume 8457 of LNCS, pages 85–99, 2014, Springer.
[bibtex] [pdf]
28 results
2019
[28]Metaheuristic Hybrids
Günther R. Raidl, Jakob Puchinger, Christian Blum
Chapter in Handbook of Metaheuristics (Michel Gendreau, Jean Yves Potvin, eds.), pages 385–417, 2019, Springer.
Note: previous technical report version at https://www.ac.tuwien.ac.at/files/pub/raidl-19.pdf
[bibtex]
2013
[27]A Timeslot-Filling Based Heuristic Approach to Construct High-School Timetables
Michael Pimmer, Günther R. Raidl
Chapter in Advances in Metaheuristics (Luca Di Gaspero, Andrea Schaerf, Thomas Stützle, eds.), volume 53 of Operations Research/Computer Science Interfaces Series, pages 143–158, 2013, Springer.
[bibtex] [pdf]
2011
[26]Tackling the Loading Aspect of the Vehicle Routing Problem with Compartments
Sandro Pirkwieser, Günther R. Raidl, Jens Gottlieb
Proceedings of the 9th Metaheuristics International Conference (Luca Di Gaspero, Andrea Schaerf, Thomas Stützle, eds.), pages 679–681, 2011.
[bibtex] [pdf]
[25]A Timeslot-Filling Based Heuristic Approach to Construct High-School Timetables
Michael Pimmer, Günther R. Raidl
Proceedings of the 9th Metaheuristics International Conference (Luca Di Gaspero, Andrea Schaerf, Thomas Stützle, eds.), pages 349–358, 2011.
[bibtex] [pdf]
2010
[24]The Multidimensional Knapsack Problem: Structure and Algorithms
Jakob Puchinger, Günther R. Raidl, Ulrich Pferschy
INFORMS Journal on Computing, volume 22, number 2, pages 250–265, 2010.
Note: previous technical report version at https://www.ac.tuwien.ac.at/files/pub/puchinger-07.pdf
[bibtex]
[23]Metaheuristic Hybrids
Günther R. Raidl, Jakob Puchinger, Christian Blum
Chapter in Handbook of Metaheuristics (Michel Gendreau, Jean Yves Potvin, eds.), volume 146 of International Series in Operations Research & Management Science, pages 469–496, 2010, Springer.
Note: previous technical report version at https://www.ac.tuwien.ac.at/files/pub/raidl-08a.pdf
[bibtex]
2008
[22]Bringing Order into the Neighborhoods: Relaxation Guided Variable Neighborhood Search
Jakob Puchinger, Günther R. Raidl
Journal of Heuristics, volume 14, number 5, pages 457–472, 2008.
[bibtex] [pdf]
[21]Combining Forces to Reconstruct Strip Shredded Text Documents
Matthias Prandtstetter, Günther R. Raidl
Hybrid Metaheuristics 2008 (M. J. Blesa, others, eds.), volume 5296 of LNCS, pages 175–189, 2008, Springer.
[bibtex] [pdf]
2007
[20]Models and Algorithms for Three-Stage Two-Dimensional Bin Packing
Jakob Puchinger, Günther R. Raidl
European Journal of Operational Research, volume 183, number 3, pages 1304–1327, 2007.
Note: previous technical report version at https://www.ac.tuwien.ac.at/files/pub/puchinger-04b.pdf
[bibtex]
[19]The Multidimensional Knapsack Problem: Structure and Algorithms
Jakob Puchinger, Günther R. Raidl, Ulrich Pferschy
2007, Technical report TR 186–1–07–02, Institute of Computer Graphics and Algorithms, Vienna University of Technology.
[bibtex] [pdf]
2006
[18]The Core Concept for the Multidimensional Knapsack Problem
Jakob Puchinger, Günther R. Raidl, Ulrich Pferschy
Evolutionary Computation in Combinatorial Optimization – EvoCOP 2006 (Jens Gottlieb, Günther R. Raidl, eds.), volume 3906 of LNCS, pages 195–208, 2006, Springer.
[bibtex] [pdf]
[17]Bringing Order into the Neighborhoods: Relaxation Guided Variable Neighborhood Search
Jakob Puchinger, Günther R. Raidl
2006, Technical report TR 186–1–06–02, Institute of Computer Graphics and Algorithms, Vienna University of Technology.
[bibtex] [pdf]
2005
[16]Empirical Analysis of Locality, Heritability and Heuristic Bias in Evolutionary Algorithms: A Case Study for the Multidimensional Knapsack Problem
Günther R. Raidl, Jens Gottlieb
Evolutionary Computation Journal, volume 13, number 4, pages 441–475, 2005.
[bibtex] [pdf]
[15]Relaxation Guided Variable Neighborhood Search
Jakob Puchinger, Günther R. Raidl
Proceedings of the 18th Mini Euro Conference on Variable Neighborhood Search (Pierre Hansen, Nenad Mladenović, José A. Moreno Pérez, Belén Melián Batista, J. Marcos Moreno-Vega, eds.), 2005.
[bibtex] [pdf]
2004
[14]An Evolutionary Algorithm for Column Generation in Integer Programming: an Effective Approach for 2D Bin Packing
Jakob Puchinger, Günther R. Raidl
Parallel Problem Solving from Nature – PPSN VIII (X. Yao et. al, ed.), volume 3242 of LNCS, pages 642–651, 2004, Springer.
[bibtex] [pdf]
[13]Solving a Real-World Glass Cutting Problem
Jakob Puchinger, Günther R. Raidl, Gabriele Koller
Evolutionary Computation in Combinatorial Optimization – EvoCOP 2004 (Jens Gottlieb, Günther R. Raidl, eds.), volume 3004 of LNCS, pages 162–173, 2004, Springer.
[bibtex] [pdf]
[12]Empirical Analysis of Locality, Heritability and Heuristic Bias in Evolutionary Algorithms: A Case Study for the Multidimensional Knapsack Problem
Günther R. Raidl, Jens Gottlieb
2004, Technical report TR 186–1–04–05, Institute of Computer Graphics and Algorithms, Vienna University of Technology.
[bibtex] [pdf]
[11]Models and Algorithms for Three-Stage Two-Dimensional Bin Packing
Jakob Puchinger, Günther R. Raidl
2004, Technical report TR 186–1–04–04, Institute of Computer Graphics and Algorithms, Vienna University of Technology.
[bibtex] [pdf]
2002
[10]Letting Ants Labeling Point Features
M. Schreyer, G. R. Raidl
Proceedings of the 2002 IEEE Congress on Evolutionary Computation (D. Fogel, others, eds.), pages 1564–1569, 2002, IEEE Press.
[bibtex] [pdf]
2000
[9]The Effects of Locality on the Dynamics of Decoder-Based Evolutionary Search
Jens Gottlieb, Günther R. Raidl
Proceedings of the 2000 Genetic and Evolutionary Computation Conference (D. Whitley, others, eds.), pages 283–290, 2000, Morgan Kaufmann.
[bibtex] [pdf]
1999
[8]The Multiple Container Packing Problem: A Genetic Algorithm Approach with Weighted Codings
Günther R. Raidl
ACM SIGAPP Applied Computing Review, volume 7, number 2, pages 22–31, 1999, ACM Press.
[bibtex] [pdf]
[7]On the Importance of Phenotypic Duplicate Elimination in Decoder-Based Evolutionary Algorithms
Günther R. Raidl, Jens Gottlieb
Late Breaking Papers at the 1999 Genetic and Evolutionary Computation Conference (Scott Brave, Annie S. Wu, eds.), pages 204–211, 1999.
[bibtex] [pdf]
[6]An Evolutionary Approach to Point-Feature Label Placement
Günther R. Raidl
Proceedings of the 1999 Genetic and Evolutionary Computation Conference (Wolfgang Banzhaf, others, eds.), pages 807, 1999, Morgan Kaufmann.
Note: short paper
[bibtex] [pdf]
[5]Weight-Codings in a Genetic Algorithm for the Multiconstraint Knapsack Problem
Günther R. Raidl
Proceedings of the 1999 IEEE Congress on Evolutionary Computation (Peter J. Angeline, others, eds.), pages 596–603, 1999, IEEE Press.
[bibtex] [pdf]
[4]A Weight-Coded Genetic Algorithm for the Multiple Container Packing Problem
Günther R. Raidl
Proceedings of the 1999 ACM Symposium on Applied Computing (Janice Carroll, others, eds.), pages 291–296, 1999, ACM Press.
[bibtex] [pdf]
1998
[3]A Genetic Algorithm for Labeling Point Features
Günther R. Raidl
Proceedings of the International Conference on Imaging Science, Systems and Technology (H. R. Arabnia, P.-C. Chung, J. B. Farison, G. R. Raidl, M. Sarfraz, Z. Zhang, eds.), pages 189–196, 1998, CSREA Press.
[bibtex] [pdf]
[2]An Improved Genetic Algorithm for the Multiconstrained 0–1 Knapsack Problem
Günther R. Raidl
Proceedings of the 5th IEEE International Conference on Evolutionary Computation (D. Fogel, others, eds.), pages 207–211, 1998, IEEE Press.
[bibtex] [pdf]
[1]Genetic Algorithms for the Multiple Container Packing Problem
Günther R. Raidl, Gabriele Kodydek
Proceedings of the 5th International Conference on Parallel Problem Solving from Nature – PPSN V (Agoston E. Eiben, others, eds.), volume 1498 of LNCS, pages 875–884, 1998, Springer.
[bibtex] [pdf]

News

  • Best Paper Award at SOFSEM 2025

    Best Paper Award at SOFSEM 2025

    2025-01-23
    Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, and Martin Nöllenburg received the Best Paper Award for their paper …Read More »
  • Markus Wallinger receives Award of Excellence for his PhD Thesis

    Markus Wallinger receives Award of Excellence for his PhD Thesis

    2024-12-05
    Our former group member Markus Wallinger won the Award of Excellence by the Federal Ministry for Education, Science and Research. …Read More »
  • Thomas Depian receives State Prize for his Master’s Thesis

    Thomas Depian receives State Prize for his Master’s Thesis

    2024-11-21
    Our group member Thomas Depian won the Appreciation Award given by the Federal Ministry for Education, Science and Research. This …Read More »
  • Best Paper Award at GECCO 2024 for M. Bresich, G. Raidl, and S. Limmer

    Best Paper Award at GECCO 2024 for M. Bresich, G. Raidl, and S. Limmer

    2024-07-24
    Maria Bresich, Günther Raidl, and Steffen Limmer received the best paper award at the 2024 Genetic and Evolutionary Computation Conference …Read More »
  • Welcome to our Feodor Lynen Fellow Dr. Frank Sommer

    Welcome to our Feodor Lynen Fellow Dr. Frank Sommer

    2024-06-14
    On June 1, 2024, Dr. Frank Sommer has joined the Algorithms and Complexity group with a prestigious Feodor Lynen postdoc …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023 and 2024.
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.