Article ID: | iaor1999210 |
Country: | Netherlands |
Volume: | 91 |
Issue: | 3 |
Start Page Number: | 553 |
End Page Number: | 564 |
Publication Date: | Jun 1996 |
Journal: | European Journal of Operational Research |
Authors: | Zissimopoulos V., Hifi M. |
Keywords: | programming: dynamic |
Gilmore and Gomory's algorithm is one of the better actually known exact algorithms for solving unconstrained guillotine two-dimensional cutting problems. Herz's algorithm is more effective, but only for the unweighted case. We propose a new exact algorithm adequate for both weighted and unweighted cases, which is more powerful than both algorithms. The algorithm uses dynamic programming procedures and one-dimensional knapsack problem to obtain efficient lower and upper bounds and important optimality criteria which permit a significant branching cut in a recursive tree-search procedure. Recursivity, computational power, adequateness to parallel implementations, and generalization for solving constrained two-dimensional cutting problems, are some important features of the new algorithm.