Paper Info
Title
A branch-and-price-and-cut algorithm for the pattern minimization problem
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 de. ne 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.
Year
DOI
Venue
2008
10.1051/ro:2008027
RAIRO-OPERATIONS RESEARCH
Keywords
Field
DocType
Pattern Minimization Problem,column generation,cutting planes,branch-and-bound,dual feasible functions
Mathematical optimization,Branch and bound,Cutting-plane method,Column generation,Linear model,Branch and price,Algorithm,Integer programming,Cutting stock problem,Optimization problem,Mathematics
Journal
Volume
Issue
ISSN
42
4
0399-0559
Citations 
PageRank 
References 
6
0.56
4
Authors
2
Name
Order
Citations
PageRank
Cláudio Alves118416.29
J. M. Valério de Carvalho2654.53