Approximate and exact algorithms for constrained (Un) weighted two-dimensional two-staged cutting stock problems

In this paper we propose two algorithms for solving both unweighted and wei ghted constrained two-dimensional two-staged cutting stock problems. The pr oblem is called two-staged cutting problem because each produced (sub)optim al cutting pattern is realized by using two cut-phases. In the first cut-ph ase, the current stock rectangle is slit down its width (resp. length) into a set of vertical (resp. horizontal) strips and, in the second cut-phase, each of these strips is taken individually and chopped across its length (r esp. width). First, we develop an approximate algorithm for the problem. The original pr oblem is reduced to a series of single bounded knapsack problems and solved by applying a dynamic programming procedure. Second, we propose an exact a lgorithm tailored especially for the constrained two-staged cutting problem . The algorithm starts with an initial (feasible) lower bound computed by a pplying the proposed approximate algorithm. Then, by exploiting dynamic pro gramming properties, we obtain good lower and upper bounds which lead to si gnificant branching cuts. Extensive computational testing on problem instan ces from the literature shows the effectiveness of the proposed approximate and exact approaches.