Exact algorithms for large-scale unconstrained two and three staged cutting problems

In this paper we propose two exact algorithms for solving both two-staged a nd three staged unconstrained (un)weighted cutting problems. The two-staged problem is solved by applying a dynamic programming procedure originally d eveloped by Gilmore and Gomory [Gilmore and Gomory, Operations Research, vo l. 13, pp. 94-119, 1965]. The three-staged problem is solved by using a top -down approach combined with a dynamic programming procedure. The performan ce of the exact algorithms are evaluated on some problem instances of the l iterature and other hard randomly-generated problem instances (a total of 5 3 problem instances). A parallel implementation is an important feature of the algorithm used for solving the three-staged version.