A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem

A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem

0.00 Avg rating0 Votes
Article ID: iaor20091160
Country: United Kingdom
Volume: 35
Issue: 4
Start Page Number: 1315
End Page Number: 1328
Publication Date: Apr 2008
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: branch and bound
Abstract:

Many heuristic approaches have been proposed in the literature for the multiple length cutting stock problem, while only few results have been reported for exact solution algorithms. In this paper, we present a new branch-and-price-and-cut algorithm which outperforms other exact approaches proposed so far. Our conclusions are supported on many computational experiments conducted on instances from the literature. In the second part of the paper, we investigate the use of valid dual inequalities within the previous algorithm. We show how column generation can be accelerated in all the nodes of our branching tree using such inequalities. Until now, dual inequalities have been applied only for original linear programming relaxations. Their validity within a branch-and-bound procedure has never been investigated. Our computational experiments show that extending these inequalities to the whole branch-and-bound tree can significantly improve the convergence of our branch-and-price-and-cut algorithm.

Reviews

Required fields are marked *. Your email address will not be published.