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.
Table of Contents
1 Introduction
2 Model and formulations
2.1 Cutting Stock Problem
2.2 Bin Packing Problem
2.3 Relationship between CSP and BPP
2.4 Other model formulations
2.4.1 Arc Flow Model
2.4.2 Outlook for further formulations
2.5 Model extensions for the CSP
3 CSP Solving Process
3.1 Column Generation
3.2 Column Generation an illustrative example
3.3 Finding an integer solution
3.4 Bounds for the objective function value
4 Experimental results
4.1 Solver Process
4.2 Test Procedure
5 Conclusion
Research Objectives and Key Topics
The primary objective of this work is to evaluate the performance of the column generation approach for solving the Cutting Stock Problem (CSP) across various problem instances. The thesis investigates how different optimization solvers (Gurobi, CPLEX, and SCIP) handle the column generation process and the generation of integer solutions, analyzing their efficiency and solution quality.
- Mathematical formulation of the Cutting Stock Problem and related models.
- Theoretical exploration of the Column Generation algorithm and its application.
- Analysis of different MIP solver behaviors and strategies.
- Performance evaluation using diverse test instances from established libraries.
- Investigation of the relationship between relaxed solutions and integer results.
Excerpt from the Book
3.1 Column Generation
Often linear programs become too large to consider all variables, and explicitly most of the variables will be non-basic and assume a value of zero in the optimal solution. Column generation is an algorithm to solve mathematical programs by iteratively adding the variables of the model and was initially developed by Ford and Fulkerson in 1958 [37].
The idea is to generate only variables which have the potential to improve the objective function, by finding variables with negative reduced costs [38]. In general, the original problem splits into a master problem and a subproblem. The master problem considers the original problem with only a subset of the variables and a relaxation of them. In the newly created subproblem, variables should be identified for the master problem, and the decision is made whether to include it. The objective function of this subproblem is the reduced cost of the new variable under the original restrictions.
Summary of Chapters
1 Introduction: Provides an overview of the Cutting Stock Problem, its industrial relevance, and outlines the structure of the present work.
2 Model and formulations: Presents mathematical formulations for the CSP, introduces the related Bin Packing Problem, and discusses various extensions of the classic CSP model.
3 CSP Solving Process: Explains the Column Generation technique, demonstrates it through an illustrative example, and discusses strategies for finding integer solutions and establishing bounds.
4 Experimental results: Details the empirical evaluation of three different MIP solvers (Gurobi, CPLEX, SCIP) and analyzes their performance based on computational time and solution quality across 35 test instances.
5 Conclusion: Summarizes the key findings regarding the effectiveness of column generation for the CSP and reflects on the varying performance of the investigated solvers.
Keywords
Cutting Stock Problem, Column Generation, Bin Packing Problem, Combinatorial Optimization, Operations Research, Mathematical Programming, MIP Solvers, Gurobi, CPLEX, SCIP, Integer Solution, Arc Flow Model, Linear Programming, Computational Performance, Heuristics.
Frequently Asked Questions
What is the fundamental focus of this research?
The work focuses on solving the Cutting Stock Problem (CSP) using the column generation approach and evaluating how different mathematical optimization solvers perform in this specific task.
What are the central thematic fields covered?
The central fields are combinatorial optimization, linear and integer programming, specifically addressing cutting and packing problems found in industrial applications.
What is the primary research goal?
The goal is to implement a column generation algorithm for the CSP, test it using three distinct MIP solvers (Gurobi, CPLEX, SCIP), and compare their effectiveness in terms of computational speed and solution quality.
Which scientific method is utilized?
The study employs the column generation algorithm, which iteratively solves a master problem and a subproblem to find optimal cutting patterns for the relaxed problem before determining an integer solution.
What topics are discussed in the main body of the work?
The main body covers mathematical modeling of the CSP, detailed explanations of the column generation process, techniques for finding integer solutions, and a comprehensive performance comparison of solvers using varied test instances.
Which keywords best characterize this research?
Key terms include Cutting Stock Problem, Column Generation, MIP Solvers, Computational Optimization, and Integer Linear Programming.
How do the solvers differ in their approach to the subproblem?
The solvers use different internal configurations and parameter settings. When multiple subproblems offer the same objective function value, solvers may choose different cutting patterns, which can lead to divergent results in subsequent iterations.
What does the empirical data reveal about solver performance?
The analysis shows that performance varies significantly by instance. While Gurobi generally performed well, no single solver consistently outperformed the others in every scenario regarding both time and integer solution quality.
Why is the "Integer Round-Up Property" significant?
It is significant because it provides insights into the gap between the optimal relaxed solution and the actual integer solution, helping to define the bounds of the problem's complexity.
- Arbeit zitieren
- Marvin Caspar (Autor:in), 2020, Column Generation for the Cutting Stock Problem, München, GRIN Verlag, https://www.grin.com/document/1061428
