A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size. (English) Zbl 1244.90191
Summary: We consider a two-dimensional cutting stock problem where stock of different sizes is available, and a set of rectangular items has to be obtained through two-staged guillotine cuts. We propose a heuristic algorithm, based on column generation, which requires as its subproblem the solution of a two-dimensional knapsack problem with two-staged guillotines cuts. A further contribution of the paper consists in the definition of a mixed integer linear programming model for the solution of this knapsack problem, as well as a heuristic procedure based on dynamic programming. Computational experiments show the effectiveness of the proposed approach, which obtains very small optimality gaps and outperforms the heuristic algorithm proposed by G. F. Cintra et al. [Eur. J. Oper. Res. 191, No. 1, 61–85 (2008; Zbl 1146.90499)].
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C11 | Mixed integer programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Citations:
Zbl 1146.90499Software:
CPLEXReferences:
| [1] | Alvarez-Valdes, R.; Parajon, A.; Tamarit, J. M., A computational study of lp-based heuristic algorithms for two-dimensional guillotine cutting stock problems, OR Spektrum, 24, 179-192 (2002) · Zbl 1012.90032 |
| [2] | G. Belov, G. Scheithauer, Models with variable strip widths for two-dimensional two-stage cutting, Technical Report MATH-NM-17-2003, Dresden University, 2003.; G. Belov, G. Scheithauer, Models with variable strip widths for two-dimensional two-stage cutting, Technical Report MATH-NM-17-2003, Dresden University, 2003. |
| [3] | Cintra, G. F.; Miyazawa, F. K.; Wakabayashi, Y.; Xavier, E. C., Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation, European Journal of Operational Research, 191, 61-85 (2008) · Zbl 1146.90499 |
| [4] | F. Furini. Decomposition and reformulation of integer linear programming problems, 4OR (2011), doi: 10.1007/s10288-011-0178-4.; F. Furini. Decomposition and reformulation of integer linear programming problems, 4OR (2011), doi: 10.1007/s10288-011-0178-4. · Zbl 1362.90296 |
| [5] | Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem, Operations Research, 9, 849-859 (1961) · Zbl 0096.35501 |
| [6] | Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem - Part II, Operations Research, 11, 863-888 (1963) · Zbl 0124.36307 |
| [7] | Gilmore, P. C.; Gomory, R. E., Multistage cutting stock problems of two and more dimensions, Operations Research, 13, 94-120 (1965) · Zbl 0128.39601 |
| [8] | Lodi, A.; Martello, S.; Monaci, M., Two-dimensional packing problems: a survey, European Journal of Operational Research, 141, 241-252 (2002) · Zbl 1081.90576 |
| [9] | Lodi, A.; Monaci, M., Integer linear programming models for 2-staged two-dimensional knapsack problems, Mathematical Programming, 94, 178-257 (2003) · Zbl 1030.90064 |
| [10] | Malaguti, E., The vertex coloring problem and its generalizations, 4OR, 7, 101-104 (2009) · Zbl 1165.05010 |
| [11] | Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), John Wiley & Sons: John Wiley & Sons Chichester · Zbl 0708.68002 |
| [12] | Riehme, J.; Scheithauer, G.; Terno, J., The solution of two-stage guillotine cutting stock problems having extremely varying order demands, European Journal of Operational Research, 91, 543-552 (1996) · Zbl 0918.90122 |
| [13] | Wäscher, G.; Haussner, H.; Schumann, H., An improved typology of cutting and packing problems, European Journal of Operational Research, 183, 1109-1130 (2007) · Zbl 1278.90347 |
| [14] | COIN-OR linear program solver. An open source code for solving linear programming problems. <http://www.coin-or-org/Clp/index.html>; COIN-OR linear program solver. An open source code for solving linear programming problems. <http://www.coin-or-org/Clp/index.html> |
| [15] | Cutting stock with multiple stock size instances. <http://www.ime.usp.br/yw/BinPackingData/>; Cutting stock with multiple stock size instances. <http://www.ime.usp.br/yw/BinPackingData/> |
| [16] | IBM-CPLEX. <http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/>; IBM-CPLEX. <http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/> |
| [17] | OR-Library. <http://people.brunel.ac.uk/mastjjb/jeb/info.html>; OR-Library. <http://people.brunel.ac.uk/mastjjb/jeb/info.html> |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
