Constrained two-dimensional cutting stock problems: A best-first branch-and-bound algorithm

Constrained two-dimensional cutting stock problems: A best-first branch-and-bound algorithm

0.00 Avg rating0 Votes
Article ID: iaor20012357
Country: United Kingdom
Volume: 7
Issue: 3
Start Page Number: 185
End Page Number: 210
Publication Date: May 2000
Journal: International Transactions in Operational Research
Authors: , ,
Keywords: programming: branch and bound
Abstract:

In this paper, we develop a new version of an algorithm for solving exactly some variants of (un)weighted constrained two-dimensional cutting stock problems. Performance of branch-and-bound procedure depends highly on particular implementation of that algorithm. Programs of this kind are often accelerated drastically by employing sophisticated techniques. In the new version of the algorithm, we start by enhancing the initial lower bound to limit initially the space search. This initial lower bound has already been used as a heuristic for solving the constrained and unconstrained cutting stock problems. Also, we try to improve the upper bound at each internal node of the developed tree, by applying some simple and efficient combinations. Finally, we introduce some new symmetric-strategies used for neglecting some unnecessary duplicate patterns. The performance of our algorithm is evaluated on some problem instances of the literature and other hard-randomly generated problem instances.

Reviews

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