Issue RAIRO-Oper. Res. Volume 42, Number 4, October-December 2008 ALIO/EURO V Conference on Combinatorial Optimization Page(s) 435 - 453 DOI 10.1051/ro:2008027 Published online 04 April 2009

RAIRO-Oper. Res. 42 (2008) 435-453
DOI: 10.1051/ro:2008027

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

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

Escola de Engenharia, Universidade do Minho, 4710-057 Braga, Portugal; claudio@dps.uminho.pt

Received October 24, 2005; Accepted January 9, 2008. Published online 4 April 2009

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.

Mathematics Subject Classification. 90C10, 90C57.

Key words: Pattern Minimization Problem, column generation, cutting planes, branch-and-bound, dual feasible functions.


© EDP Sciences, ROADEF, SMAI 2008

What is OpenURL?