Nouvelles formulations et algorithmes inédits pour le problème de découpe bidimentionnelle

Abstract

Dans ce mémoire, il sera question du problème de découpe à deux dimensions fréquemment rencontré dans l’industrie du papier, du verre et du textile. Ce problème consiste à découper un ensemble de rectangles de dimensions et de valeurs connues à partir d’un patron rectangulaire en cherchant à maximiser la valeur totale des rectangles découpés ou à minimiser la perte obtenue lors de cette coupe. Dans un premier temps, nous formulons le problème comme un modèle général non linéaire maximisant la valeur totale découpée et nous effectuons ensuite certaines transformations afin d’obtenir un modèle de programmation linéaire mixte. Nous présentons également une suite de variantes qui diffèrent du modèle principal au niveau de certaines contraintes. Cela a pour but d’améliorer la résolution du programme relaxé augmentant ainsi l’efficacité de l’approche algorithmique. Afin de résoudre la variante la plus efficace, nous présentons une nouvelle approche basée sur diverses relaxations lagrangiennes de celle-ci pour minimiser la borne supérieure obtenue à l’aide d’une méthode de sous-gradients. Enfin, nous construisons une procédure basée sur une technique arborescente utilisant une borne inférieure associée à une solution réalisable provenant habituellement d’une heuristique qui génère celle-ci à partir de la solution du problème lagrangien. Finalement, des problèmes tests (de petites et moyennes dimensions) tirés de la littérature ou générés aléatoirement démontrent la performance de notre algorithme.