problème de découpe (Bin Packing 2D)

Bonjour a tous,je travaille sur un problème de découpe ( bin packing 2D)
je dois découper à partir de plaques de taille connue, des plaques plus petites de taille différentes et connues. l'objectif est d'utiliser le minimum de plaques tout en minimisant les déchets.
je me suis proposé de résoudre ce problème à partir d'un programme linéaire en nombres entier, mais j'ai buté au niveau de l'énumération des plans de coupe possibles. pour énumérer les plans de coupe je suis passé par le calcul de surface de toute les pièces a découper ainsi celle de la plaque la plus grande.
j'ai rangé les surfaces des plaques a découper dans un ordre décroissant
je pose alors l'équation suivant: Ax <= S avec x entier
A: première surface a découper
S: surface de la grande plaque
je détermine ainsi combien de fois on peut avoir la surface A dans S
je calcule la chute= S-Ax
si la surface de la chute est supérieure a la surface de l'une des autres pièces a découper j'insère la plaque dont la surface est inférieure a la chute dans la première équation avec x supposé connu; la seconde équation me donne Ax + Bx'<= S
j'ai procédé ainsi fixant une plaque que je combine avec les autres. la méthode est assez fastidieuse lorsqu'on se retrouve avec un grand nombre de pièces a découper. le problème qui s'est posé est que parmi les plan de coupe que j'ai obtenu certaines d'entre elles n'étaient pas réalisables du fait que j'ai pas prit en compte la manière dont les plaques doivent être disposées. Ainsi je me suis tourné vers vous, si vous pourriez m'éclairer dans ce sens. merci!

Bonjour,

Je me suis frotté au BP2D mais j'ai utilisé des méta-heuristiques pour générer les solutions potentielles, mes cours de RO étant un peu loin.

Voici trois papiers qui pourraient t'aider (je ne sais pas s'ils sont dispos. gratuitement), n'ayant pas accès à des ressources payantes, c'est un collègue qui me les avait passé.

* An improved typologie of cutting and packing problems, de Wäscher, Haubner et Schumann. Il comporte une bonne biblio. (mais il date de 2004).
* A hybrid heuristic to reduce the number of different patterns in cutting stock problems, de Yanasse et Limeira
* One-dimensional cutting stock problem to minimize the number of different patterns, de Umetani, Yagiura et Ibaraki.

Après, plonge dans Google Scolar et Citeseer.
Pour le 1er, certains liens permettent de downloader le papier (la seconde colonne est un lien de la forme "[pdf] a partir de <url>").

Pour rester sur la PL, renseigne-toi sur la technique de la génération de colonnes qui est très utilisé pour la PL appliqué au BP ("Column Generation" en VO).