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

Mhand Hifi, CERMSEM
Catherine Roucairol*, PRiSM

Résumé. Dans ce papier, nous proposons deux nouveaux algorithmes pour la résolution du problème de découpe à deux niveaux et avec des contraintes sur les pièces. En premier, nous proposons une méthode approchée. Nous réduisons le problème initial sous forme d'une série de problèmes de knapsacks unidimensionnels bornés. La résolution du problèmes s'appuie principalement sur l'application des techniques de la programmation dynamique.
Par la suite, nous proposons une méthode exacte pour le problème. L'approche s'appuie sur une méthode hybride combinant une méthode de séparation et d'évaluation (en profondeur), et les résultats obtenus par l'application d'une recherche locale (en s'appuyant sur les techniques de la programmation dynamique).
La performance des deux algorithmes est évaluée sur un ensemble d'instances de la littérature ainsi que d'autres instances de grandes taille, générées aléatoirement.
Mots clés : Optimisation combinatoire, problèmes de découpe, programmation dynamique, knapsack unidimensionnel, optimalité.

Abstract. In this paper we propose two algorithms for solving both unweighted and weighted constrained two-dimensional two-staged cutting stock problems. The problem is called two-staged cutting problem because each produced (sub) optimal cutting pattern is realized by using two cut-phases. In the first cut-phase, 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 (resp. width).
First, we develop an approximate algorithm for the problem. The original problem is reduced to a series of single bounded knapsack problems and solved by applying a dynamic programming procedure. Second, we propose an exact algorithm tailored especially for the constrained two-staged cutting problem. The algorithm starts with an initial (feasible) lower bound computed by applying the proposed approximate algorithm. Then, by exploiting dynamic programming properties, we obtain good lower and upper bounds which lead to significant branching cuts. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approximate and exact approaches.
Keywords : Combinatorial optimization, cutting problems, dynamic programming, single knapsack problem, optimality.

*PRiSM, URA 1525 du CNRS, Université de Versailles-Saint-Quentin en Yvelines, 45 Avenue des Etats-Unis, 78035 Versailles Cedex, France