In cutting stock problems, after an optimal (minimal stock usage) cutting plan has been devised, one might want to further reduce the operational costs by minimizing the number of setups. A setup operation occurs each time a different cutting pattern begins to be produced. The related optimization problem is known as the Pattern Minimization Problem, and it is particularly hard to solve exactly. In this paper, we present different techniques to strengthen a formulation proposed in the literature. Dual feasible functions are used for the first time to derive valid inequalities from different constraints of the model, and from linear combinations of constraints. A new arc flow formulation is also proposed. This formulation is used to define the branching scheme of our branch-and-price-and-cut algorithm, and it allows the generation of even stronger cuts by combining the branching constraints with other constraints of the model. The computational experiments conducted on instances from the literature show that our algorithm finds optimal integer solutions faster than other approaches. A set of computational results on random instances is also reported.
Mots-clés : pattern minimization problem, column generation, cutting planes, branch-and-bound, dual feasible functions
@article{RO_2008__42_4_435_0, author = {Alves, Cl\'audio and Val\'erio de Carvalho, J. M.}, title = {A branch-and-price-and-cut algorithm for the pattern minimization problem}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {435--453}, publisher = {EDP-Sciences}, volume = {42}, number = {4}, year = {2008}, doi = {10.1051/ro:2008027}, mrnumber = {2469105}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro:2008027/} }
TY - JOUR AU - Alves, Cláudio AU - Valério de Carvalho, J. M. TI - A branch-and-price-and-cut algorithm for the pattern minimization problem JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2008 SP - 435 EP - 453 VL - 42 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2008027/ DO - 10.1051/ro:2008027 LA - en ID - RO_2008__42_4_435_0 ER -
%0 Journal Article %A Alves, Cláudio %A Valério de Carvalho, J. M. %T A branch-and-price-and-cut algorithm for the pattern minimization problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2008 %P 435-453 %V 42 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2008027/ %R 10.1051/ro:2008027 %G en %F RO_2008__42_4_435_0
Alves, Cláudio; Valério de Carvalho, J. M. A branch-and-price-and-cut algorithm for the pattern minimization problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 4, pp. 435-453. doi : 10.1051/ro:2008027. http://www.numdam.org/articles/10.1051/ro:2008027/
[1] Cutting and packing: problems, models and exact algorithms. Ph.D. Thesis, Universidade do Minho (2005).
,[2] Reducing the number of patterns in one-dimensional cutting stock problems. Technical report, Electrical Engineering Department, Imperial College, London (1988).
and .[3] Problems, models and algorithms in one- and two- dimensional cutting. Ph.D. Thesis, Dresden University (2003).
.[4] A simulated annealing heuristic for the one-dimensional cutting stock problem. Eur. J. Oper. Res. 93 (1996) 522-535. | Zbl
, , and .[5] New classes of fast lower bounds for bin packing problems. Math. Program. 91 (2001) 11-31. | MR | Zbl
and .[6] Pattern reduction in one-dimensional cutting stock problems. Int. J. Prod. Res. 38 (2000) 1657-1676. | Zbl
and .[7] CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem. Eur. J. Oper. Res. 84 (1995) 572-579. | Zbl
and .[8] A linear programming approach to the cutting stock problem. Oper. Res. 9 (1961) 849-859. | MR | Zbl
and .[9] Optimal solutions for the cutting stock problem. Eur. J. Oper. Res. 44 (1990) 197-208. | Zbl
,[10] A heuristic programming solution to a nonlinear cutting stock problem. Manage. Sci. 17 (1971) 793-802. | Zbl
,[11] Controlling cutting pattern changes in one-dimensional trim problems. Oper. Res. 23 (1975) 483-493. | Zbl
.[12] Rounding algorithms for cutting stock problems. Asia-Pac. Oper. Res. J. 3 (1986) 166-171. | Zbl
,[13] Cutting patterns and cutter schedules. Asia-Pac. Oper. Res. J. 4 (1987) 3-14.
.[14] Knapsack Problems. Wiley, New York (1990). | MR | Zbl
and ,[15] Integer and Combinatorial Optimization. Wiley, New York (1988). | MR | Zbl
and ,[16] Embedding of linear programming in a simulated annealing algorithm for solving a mixed integer production planning problem. J. Comput. Appl. Math. 64 (1995) 91-102. | MR | Zbl
, , and ,[17] One-dimensional cutting stock problem to minimize the number of different patterns. Eur. J. Oper. Res. 146 (2003) 388-402. | MR | Zbl
, , and ,[18] Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem. Oper. Res. 48 (2000) 915-926. | MR | Zbl
.Cité par Sources :