Cutting & Packing
(cooperation with Lodestar GmbH)
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 28 results
| 2019 | |
| [28] | Metaheuristic Hybrids 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 |
| 2013 | |
| [27] | A Timeslot-Filling Based Heuristic Approach to Construct High-School Timetables 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. |
| 2011 | |
| [26] | Tackling the Loading Aspect of the Vehicle Routing Problem with Compartments Proceedings of the 9th Metaheuristics International Conference (Luca Di Gaspero, Andrea Schaerf, Thomas Stützle, eds.), pages 679–681, 2011. |
| [25] | A Timeslot-Filling Based Heuristic Approach to Construct High-School Timetables Proceedings of the 9th Metaheuristics International Conference (Luca Di Gaspero, Andrea Schaerf, Thomas Stützle, eds.), pages 349–358, 2011. |
| 2010 | |
| [24] | The Multidimensional Knapsack Problem: Structure and Algorithms 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 |
| [23] | Metaheuristic Hybrids 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 |
| 2008 | |
| [22] | Bringing Order into the Neighborhoods: Relaxation Guided Variable Neighborhood Search Journal of Heuristics, volume 14, number 5, pages 457–472, 2008. |
| [21] | Combining Forces to Reconstruct Strip Shredded Text Documents Hybrid Metaheuristics 2008 (M. J. Blesa, others, eds.), volume 5296 of LNCS, pages 175–189, 2008, Springer. |
| 2007 | |
| [20] | Models and Algorithms for Three-Stage Two-Dimensional Bin Packing 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 |
| [19] | The Multidimensional Knapsack Problem: Structure and Algorithms 2007, Technical report TR 186–1–07–02, Institute of Computer Graphics and Algorithms, Vienna University of Technology. |
| 2006 | |
| [18] | The Core Concept for the Multidimensional Knapsack Problem Evolutionary Computation in Combinatorial Optimization – EvoCOP 2006 (Jens Gottlieb, Günther R. Raidl, eds.), volume 3906 of LNCS, pages 195–208, 2006, Springer. |
| [17] | Bringing Order into the Neighborhoods: Relaxation Guided Variable Neighborhood Search 2006, Technical report TR 186–1–06–02, Institute of Computer Graphics and Algorithms, Vienna University of Technology. |
| 2005 | |
| [16] | Empirical Analysis of Locality, Heritability and Heuristic Bias in Evolutionary Algorithms: A Case Study for the Multidimensional Knapsack Problem Evolutionary Computation Journal, volume 13, number 4, pages 441–475, 2005. |
| [15] | Relaxation Guided Variable Neighborhood Search 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. |
| 2004 | |
| [14] | An Evolutionary Algorithm for Column Generation in Integer Programming: an Effective Approach for 2D Bin Packing Parallel Problem Solving from Nature – PPSN VIII (X. Yao et. al, ed.), volume 3242 of LNCS, pages 642–651, 2004, Springer. |
| [13] | Solving a Real-World Glass Cutting Problem Evolutionary Computation in Combinatorial Optimization – EvoCOP 2004 (Jens Gottlieb, Günther R. Raidl, eds.), volume 3004 of LNCS, pages 162–173, 2004, Springer. |
| [12] | Empirical Analysis of Locality, Heritability and Heuristic Bias in Evolutionary Algorithms: A Case Study for the Multidimensional Knapsack Problem 2004, Technical report TR 186–1–04–05, Institute of Computer Graphics and Algorithms, Vienna University of Technology. |
| [11] | Models and Algorithms for Three-Stage Two-Dimensional Bin Packing 2004, Technical report TR 186–1–04–04, Institute of Computer Graphics and Algorithms, Vienna University of Technology. |
| 2002 | |
| [10] | Letting Ants Labeling Point Features Proceedings of the 2002 IEEE Congress on Evolutionary Computation (D. Fogel, others, eds.), pages 1564–1569, 2002, IEEE Press. |
| 2000 | |
| [9] | The Effects of Locality on the Dynamics of Decoder-Based Evolutionary Search Proceedings of the 2000 Genetic and Evolutionary Computation Conference (D. Whitley, others, eds.), pages 283–290, 2000, Morgan Kaufmann. |
| 1999 | |
| [8] | The Multiple Container Packing Problem: A Genetic Algorithm Approach with Weighted Codings ACM SIGAPP Applied Computing Review, volume 7, number 2, pages 22–31, 1999, ACM Press. |
| [7] | On the Importance of Phenotypic Duplicate Elimination in Decoder-Based Evolutionary Algorithms Late Breaking Papers at the 1999 Genetic and Evolutionary Computation Conference (Scott Brave, Annie S. Wu, eds.), pages 204–211, 1999. |
| [6] | An Evolutionary Approach to Point-Feature Label Placement Proceedings of the 1999 Genetic and Evolutionary Computation Conference (Wolfgang Banzhaf, others, eds.), pages 807, 1999, Morgan Kaufmann. Note: short paper |
| [5] | Weight-Codings in a Genetic Algorithm for the Multiconstraint Knapsack Problem Proceedings of the 1999 IEEE Congress on Evolutionary Computation (Peter J. Angeline, others, eds.), pages 596–603, 1999, IEEE Press. |
| [4] | A Weight-Coded Genetic Algorithm for the Multiple Container Packing Problem Proceedings of the 1999 ACM Symposium on Applied Computing (Janice Carroll, others, eds.), pages 291–296, 1999, ACM Press. |
| 1998 | |
| [3] | A Genetic Algorithm for Labeling Point Features 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. |
| [2] | An Improved Genetic Algorithm for the Multiconstrained 0–1 Knapsack Problem Proceedings of the 5th IEEE International Conference on Evolutionary Computation (D. Fogel, others, eds.), pages 207–211, 1998, IEEE Press. |
| [1] | Genetic Algorithms for the Multiple Container Packing Problem 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. |
