An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional cutting stock

An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional cutting stock

0.00 Avg rating0 Votes
Article ID: iaor1998921
Country: United Kingdom
Volume: 24
Issue: 8
Start Page Number: 727
End Page Number: 736
Publication Date: Aug 1997
Journal: Computers and Operations Research
Authors:
Keywords: programming: dynamic, cutting stock
Abstract:

Viswanathan and Bagchi have proposed a bottom-up algorithm which combines in the nice tree-search procedure Gilmore and Gomory's algorithm, called at each node of the tree, for solving exactly the constrained two-dimensional cutting problem. This algorithm is one of the best exact algorithms known today. In this paper, we propose an improved version of this algorithm is one of the best exact algorithms known today. In this paper, we propose an improved version of this algorithm by introducing one-dimensional bounded knapsacks in the original algorithm. Then, by exploiting dynamic programming properties, we obtain good lower and upper bounds which lead to significant branching cuts. Finally, the improved version is compared with the standard version of Viswanathan and Bagchi on some small and medium instances.

Reviews

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