Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm |
| |
Authors: | V-D Cung M Hifi B Le Cun |
| |
Affiliation: | Universitéde Versailles-Saint Quentin en Yvelines, 78035 Versailles Cedex, France;Universitéde Versailles-Saint Quentin en Yvelines, 78035 Versailles Cedex, France and CERMSEM, Maison des Sciences Economiques, Universitéde Paris 1, 75013 Paris, France;Universitéde Versailles-Saint Quentin en Yvelines, 78035 Versailles Cedex, France |
| |
Abstract: | In this paper, we develop a new version of the algorithm proposed in Hifi (Computers and Operations Research 24/8 (1997) 727–736) 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 in Fayard et al. 1998 (Journal of the Operational Research Society, 49, 1270–1277), 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 effcient 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. |
| |
Keywords: | Combinatorial optimization Cutting stock Dynamic programming Heuristics Knapsacks Optimization |
本文献已被 ScienceDirect 等数据库收录! |
|