Exact algorithms for Large-Scale unconstrained two and three staged cutting problems

Mhand Hifi*, CERMSEM et PRiSM

Résumé. Dans ce papier, nous proposons deux nouveaux algorithmes exacts pour la résolution de deux problèmes de découpe avec des contraintes de niveau : le problème de découpe à deux niveaux et le problème de découpe à trois niveaux. Le problème à deux niveaux est résolu par l'adaptation d'une procédure due à Gilmore et Gomory [10] en s'appuyant sur la programmation dynamique. Le problème à trois niveaux est résolu par l'application d'une méthode hybride combinant une méthode de séparation et d'évaluation et la programmation dynamique. La performance de chaque algorithme proposé 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. Nous montrons aussi que le deuxième algorithme (le cas de la découpe à trois niveaux) est "facilement" parallélisable.
Mots clés : Optimisation combinatoire, problèmes de découpe, programmation dynamique, problème de knapsack, optimalité.

Abstract. In this paper we propose two exact algorithms for solving both two-staged and three-staged unconstrained (un) weighted cutting problems. The two-staged problem is solved by applying a dynamic programming procedure originally developed by Gilmore and Gomory [10]. The three-staged problem is solved by using a top-down approach combined with a dynamic programming procedure. The performance of the exact algorithms are evaluated on some problem instances of the literature and other hard randomly-generated problem instances (a total of 53 problem instances). A parallel implementation is an important feature of the algorithm used for solving the three-staged version.
Keywords : Combinatorial optimization, cutting problems, dynamic programming, knapsack problem, optimality.

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