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

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?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.