A branch-and-price-and-cut algorithm for the pattern minimization problem

Cláudio Alves; J. M. Valério de Carvalho

RAIRO - Operations Research - Recherche Opérationnelle (2008)

  • Volume: 42, Issue: 4, page 435-453
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Alves, Cláudio, and Valério de Carvalho, J. M.. "A branch-and-price-and-cut algorithm for the pattern minimization problem." RAIRO - Operations Research - Recherche Opérationnelle 42.4 (2008): 435-453. <http://eudml.org/doc/245880>.

@article{Alves2008,
abstract = {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.},
author = {Alves, Cláudio, Valério de Carvalho, J. M.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {pattern minimization problem; column generation; cutting planes; branch-and-bound; dual feasible functions; Pattern Minimization Problem},
language = {eng},
number = {4},
pages = {435-453},
publisher = {EDP-Sciences},
title = {A branch-and-price-and-cut algorithm for the pattern minimization problem},
url = {http://eudml.org/doc/245880},
volume = {42},
year = {2008},
}

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
PB - EDP-Sciences
VL - 42
IS - 4
SP - 435
EP - 453
AB - 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.
LA - eng
KW - pattern minimization problem; column generation; cutting planes; branch-and-bound; dual feasible functions; Pattern Minimization Problem
UR - http://eudml.org/doc/245880
ER -

References

top
  1. [1] C. Alves, Cutting and packing: problems, models and exact algorithms. Ph.D. Thesis, Universidade do Minho (2005). 
  2. [2] J.M. Allwood and C.N. Goulimis. Reducing the number of patterns in one-dimensional cutting stock problems. Technical report, Electrical Engineering Department, Imperial College, London (1988). 
  3. [3] G. Belov. Problems, models and algorithms in one- and two- dimensional cutting. Ph.D. Thesis, Dresden University (2003). 
  4. [4] C.-L.S. Chen, S.M. Hart, and W.M. Tham. A simulated annealing heuristic for the one-dimensional cutting stock problem. Eur. J. Oper. Res. 93 (1996) 522–535. Zbl0912.90236
  5. [5] S. Fekete and J. Schepers. New classes of fast lower bounds for bin packing problems. Math. Program. 91 (2001) 11–31. Zbl1051.90020MR1865259
  6. [6] H. Foerster and G. Waescher. Pattern reduction in one-dimensional cutting stock problems. Int. J. Prod. Res. 38 (2000) 1657–1676. Zbl0944.90546
  7. [7] T. Gau and G. Waescher. CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem. Eur. J. Oper. Res. 84 (1995) 572–579. Zbl0918.90117
  8. [8] P.C. Gilmore and R.E. Gomory. A linear programming approach to the cutting stock problem. Oper. Res. 9 (1961) 849–859. Zbl0096.35501MR137589
  9. [9] C. Goulimis, Optimal solutions for the cutting stock problem. Eur. J. Oper. Res. 44 (1990) 197–208. Zbl0684.90082
  10. [10] R.W. Haessler, A heuristic programming solution to a nonlinear cutting stock problem. Manage. Sci. 17 (1971) 793–802. Zbl0219.90021
  11. [11] R.W. Haessler. Controlling cutting pattern changes in one-dimensional trim problems. Oper. Res. 23 (1975) 483–493. Zbl0301.90030
  12. [12] R.E. Johnston, Rounding algorithms for cutting stock problems. Asia-Pac. Oper. Res. J. 3 (1986) 166–171. Zbl0616.90044
  13. [13] R.E. Johnston. Cutting patterns and cutter schedules. Asia-Pac. Oper. Res. J. 4 (1987) 3–14. 
  14. [14] S. Martello and P. Toth, Knapsack Problems. Wiley, New York (1990). Zbl0708.68002MR1086874
  15. [15] G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization. Wiley, New York (1988). Zbl0652.90067MR948455
  16. [16] J. Teghem, M. Pirlot, and C. Antoniadis, 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. Zbl0864.65037MR1364977
  17. [17] S. Umetani, M. Yagiura, and T. Ibaraki, One-dimensional cutting stock problem to minimize the number of different patterns. Eur. J. Oper. Res. 146 (2003) 388–402. Zbl1012.90045MR1935288
  18. [18] F. Vanderbeck. Exact algorithm for minimising the number of setups in the one-dimensional cutting stock problem. Oper. Res. 48 (2000) 915–926. Zbl1106.90373MR1801681

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.