The Cutting Stock Problem (CSP) appears when a material has to be cut into smaller pieces and occurs in many branches of industry. On the one hand, the CSP belongs to the earliest studied problems through methods of Operational Research and on the other to the most intensively studied problems in combinatorial optimization.
In the one-dimensional Cutting Stock Problem (1DCSP), there are typically identical pieces of a single standard length, called rolls, that need to be cut into smaller pieces lengthwise. Examples, where the cutting process is performed in one single dimension, can be found in the steel industry and the paper industry . The two-dimensional CSP (2DCSP) is classified into cutting of regular and irregular shapes and is often found in clothing and shoe-leather industries. A real-world application of a three-dimensional CSP (3DCSP) lies in the production of mattresses, where rubber blocks are cut into different types of orthogonal rectangular prisms.
Methods of finding an optimal solution exist for the 1DCSP. Often in large problem instances, the required time for finding an optimal solution proliferates, and heuristics may turn out to be the more sensible option in this case. Nowadays, there are countless different ways to find acceptable solutions in a fast manner of time, among others, the column generation approach, which is the central component of the present work.
This work is organized as follows. In Chapter 2, a brief overview of different formulations for the CSP is given. Furthermore, some known extensions of the classic CSP are presented, e.g., raw material, that consists of various sizes at the same time.
CSP has many relatives, the closest is the Bin Packing Problem (BPP), where items are packed into bins as efficiently as possible. The third chapter shows the column generation technique for solving the CSP and provides the connection between a solution for the relaxed problem and an integer solution. In Chapter 4, different test instances of the CSP are compared using a column generation implementation solved in three different MIP solvers. The conclusion is provided in Chapter 5.
Inhaltsverzeichnis (Table of Contents)
- Introduction
- Model and formulations
- Cutting Stock Problem
- Bin Packing Problem
- Relationship between CSP and BPP
- Other model formulations
- Arc Flow Model
- Outlook for further formulations
- Model extensions for the CSP
- CSP Solving Process
- Column Generation
- Column Generation an illustrative example
- Finding an integer solution
- Bounds for the objective function value
- Experimental results
- Solver Process
- Test Procedure
- Conclusion
Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)
This work provides a comprehensive overview of the Cutting Stock Problem (CSP) and its relationship to the Bin Packing Problem (BPP), exploring different model formulations and solution approaches, particularly focusing on the column generation technique.
- Different model formulations for the CSP
- Relationship between CSP and BPP
- Column generation technique for solving the CSP
- Integer solution finding methods for the CSP
- Experimental results comparing different CSP solvers
Zusammenfassung der Kapitel (Chapter Summaries)
- Introduction: This chapter introduces the Cutting Stock Problem (CSP) and its applications in various industries. It discusses the historical context of the CSP and its relevance in combinatorial optimization. The chapter highlights the one-dimensional (1DCSP) and two-dimensional (2DCSP) variations of the CSP and provides real-world examples. It concludes by outlining the structure of the work.
- Model and formulations: This chapter focuses on defining the CSP and BPP problems through mathematical formulations. It introduces the notation used throughout the work and presents different formulations for the CSP, including the classic model and the Complete-Cut Model. The chapter emphasizes the relationship between CSP and BPP.
- CSP Solving Process: This chapter explores the column generation technique as a method for solving the CSP. It provides an illustrative example of column generation and explains how to find an integer solution. The chapter also discusses the concept of bounds for the objective function value.
Schlüsselwörter (Keywords)
Cutting Stock Problem, Bin Packing Problem, column generation, combinatorial optimization, integer programming, linear programming, model formulations, solution techniques, experimental results, MIP solvers.
- Citar trabajo
- Marvin Caspar (Autor), 2020, Column Generation for the Cutting Stock Problem, Múnich, GRIN Verlag, https://www.grin.com/document/1061428
