In cutting stock problems, after an optimal (minimal stock usage)cutting plan has been devised, one might want to further reduce theoperational costs by minimizing the number of setups. A setupoperation occurs each time a different cutting pattern begins to beproduced. The related optimization problem is known as the PatternMinimization Problem, and it is particularly hard to solve exactly.In this paper, we present different techniques to strengthen aformulation proposed in the literature. Dual feasible functions areused for the first time to derive valid inequalities from differentconstraints of the model, and from linear combinations of constraints. A new arcflow formulation is also proposed. This formulation is used todefine the branching scheme of our branch-and-price-and-cutalgorithm, and it allows the generation of even stronger cuts bycombining the branching constraints with other constraints of themodel. The computational experiments conducted on instances from theliterature show that our algorithm finds optimalinteger solutions faster than other approaches. A set of computationalresults on random instances is also reported.