Algorithme de découpe

Bonjour,

Je cherche à calculer le meilleur rendement pour découper des formes dans un rectangle. En clair : J'ai un rectangle de taille X fois Y. Et j'ai des pièces de taille différentes (on va dire que toutes les pièces sont rectangulaires ce sera plus simple). Comment loger le maximum de pièce dans le rectangle principal ? Un algorithme de découpe en fait.

Mes idées :
- Représenter la pièce principale en zone (plus la zone est petite plus je serais précis). Ensuite calculer toutes les possibilités. Je pourrais aussi pondérer les différents placement pour éviter de passer toutes les possibilités.

Si vous avez des pistes elles sont les bienvenues.

Merci d'avance

Bonjour,

Je ne comprends pas vraiment ton idée de "Représenter la pièce principale en zone", tu peux détailler?

Sinon je pensais à de la programmation dynamique, dans le cas où chaque pièce est disponible est infinité de fois (sinon tu peux rajouter un paramètre...):
T[a][b] représente le nombre max de pièces que l'on peut mettre dans un rectangle a x b.
(cf pièce jointe) Pour trouver T[a][b], on peut placer une pièce 1 sur un bord puis, si 2 est de dimension c x d, calculer T[c][d] en prenant en compte le fait qu'on puisse utiliser des pièces à cheval entre 2 et l'endroit vide.
L'idéal serait de ne pas avoir "de pièces à cheval"...
Après il serait peut être plus simple de faire une simple récurrence...

Ce n'est pas très précis, mais j'espère que ça peut t'aider

Citation:

---

Et j'ai des pièces de taille différentes

---

Combien ?
Si le nombre est petit, on peut peut-être calculer "toutes les solutions'".

Citation:

---

Envoyé par Shivan

Bonjour,

Je cherche à calculer le meilleur rendement pour découper des formes dans un rectangle. En clair : J'ai un rectangle de taille X fois Y. Et j'ai des pièces de taille différentes (on va dire que toutes les pièces sont rectangulaires ce sera plus simple). Comment loger le maximum de pièce dans le rectangle principal ? Un algorithme de découpe en fait.

Mes idées :
- Représenter la pièce principale en zone (plus la zone est petite plus je serais précis). Ensuite calculer toutes les possibilités. Je pourrais aussi pondérer les différents placement pour éviter de passer toutes les possibilités.

Si vous avez des pistes elles sont les bienvenues.

Merci d'avance

---

Cherche bin-packing et/ou strip-packing (en commençant par citeseer ou scoolar par ex.), tu va trouver beaucoup de papiers.
Après comme l'a dit graffito, tout dépends de ton nombre de pièces, le BP et le SP étant des problèmes NP-difficile.

Merci à tous pour vos réponses.

J'ai regardé les algos de bin-packing et le probléme est bien plus compliqué que prévu.
Il y a pourtant des implémentations simples (Bottom left : mettre la pièce le plus en bas à gauche) d'autres plus compliqués (metaheuristiques).
Je vais faire quelques essais sur différent algo.

Quelles sont tes contraintes exactement ? Cela te permettra d'éviter certains types d'algo. ou au contraire de guider vers.

Combien de pièces doit-tu placer au maximum ?
Si il n'y en a que <peu>, il reste possible d'examiner toutes les solutions (le <peu> étant fonction de la puissance de calcul à ta disposition, des algos. que tu utilise et de leur implémentation, etc...)

Dois-tu fournir LA meilleure solution (bon courage) ou est-ce qu'une bonne suffit ?
Ainsi, une heuristique ne te donnera qu'une solution (par lancement) sans garantie qu'elle soit la meilleure ni même bonne mais très rapidement alors qu'une méta, elle te fournira la meilleure solution parmi x étudiées (toujours pour un lacement mais la aussi sans garantie que ce soit la solution optimale) mais en demandant plus ou moins de temps.

De même, pour une instance donnée, une heuristique telle que Bottom-First te donnera toujours la même solution alors qu'une méta non.

Tes pièces peuvent-elle subir une rotation ?
Dois-tu respecter une coupe guillotine ?
Ta coupe doit-elle être "facile" ? (à toi de définir le facile en question, par exemple, limiter le nombre d'alternance vertical/horizontale lors de la découpe physique s'il y en a une, etc...)

Par ex. je me suis frotté au BP2D et j'ai utilisé l'heuristique SHF accouplée avec des méta-heuristiques et pour une instance dont je savais qu'il existait au moins une solution sans aucune perte. J'obtenais sans soucis une solution "parfaite" mais la découpe proposée faisait peur aux utilisateurs quand ils pensait aux manipulations :D

Qu'accepteront tes utilisateurs (s'il y en a) en terme de paramétrage ?
Dans mes "recherches" sur le BP, les algos. génétiques et les fourmis ont été efficaces mais étaient sensibles aux paramètres utilisés (sans compter les opérateurs dans le cas des AG) alors que le hill-climbing avec redémarrage était relativement proche en terme d'efficacité et sans paramétrage...

j'ai donné dans un précédent messages quelques liens sur des personnes qui ont bossé sur le BP et le SP.

Perso, j'aimerais bien que tu nous tienne au courant s'il-te-plaît.
C'est un domaine qui m'intéresse vraiment mais mes cours sont très lointains pour tout ce qui est programmation dynamique/linéaire, théorie des graphes...

Je peux fournir mon mémoire à ceux que cela intéresse (en attendant que je trouve le temps/courage/etc...de l'uploader quelque part)

Tout d'abord merci pour ton aide 250rgv.

Citation:

---

Quelles sont tes contraintes exactement ?

---

Pour l'instant j'aimerais faire une version de base avec le minimum de contrainte. En résumé l'utilisateur rentre la taille de sa planche, la taille de ses différentes pièces et le programme lui donne un résultat. Je n'ai pas besoin du résultat optimal mais d'un résultat approchant de bonne qualité. Pour l'instant pas de contrainte guillotine ou de découpe facile. Restons simple ! Par contre mes pièces ne sont pas orientés (elles peuvent subir une rotation).

Citation:

---

Si il n'y en a que <peu>, il reste possible d'examiner toutes les solutions

---

J'ai du mal à voir comment je peux examiner toutes les solutions. Ne serait ce qu'avec une seule pièce et une grande planche, il y a des milliers de positions possibles (au centre, à gauche, à droite et encore toutes ces positions décalés d'1mm à chaque fois). Il faut que je me base sur des critères concret pour chercher les meilleurs positions (ex : le maximum de surface avec un bord de la planche ou d'une autre pièce)

Citation:

---

Ainsi, une heuristique ne te donnera qu'une solution (par lancement) sans garantie qu'elle soit la meilleure ni même bonne mais très rapidement alors qu'une méta, elle te fournira la meilleure solution parmi x étudiées

---

Pour commencer peux tu me préciser la différence entre heuristique et méta-heuristique. Pour moi une heuristique est un algo donnant une solution en un temps faible (voir en un temps déterminé). Les méta-heuristiques sont des algos décrivant des heuristiques générales (applicable à plusieurs problèmes). Mes définitions sont t-elles correctes ?

Citation:

---

Par ex. je me suis frotté au BP2D et j'ai utilisé l'heuristique SHF accouplée avec des méta-heuristiques

---

Pour l'instant je me base sur ce doc (thése de doctorat).
Mon idée était d'implémenter l'algo BL (assez simple et efficace) et un algo décrit dans le document (IMA) qui d'après son auteur obtient de bon résultat.
Le document parle aussi de prétraitement (je ne pense pas en avoir le besoin), de calcul de borne (je ne sais pas trop à quoi cela sert mais j'ai sauté cette partie) ainsi que d'une méta-heuristique basé sur l'algo tabou (est ce vraiment plus efficace ?)
J'ai donc aussi regarder l'algo que tu as déjà implémenter (SHF). Intéressant et décrit en pseudo langage donc plus facile à implémenter pour moi. Je vais surement commencer par celui la.

Citation:

---

Je peux fournir mon mémoire à ceux que cela intéresse

---

Oui avec plaisir. As tu travaillé sur la problématique qui m'intéresse. As tu tester plusieurs algos ? Dis moi en plus la dessus.

Merci pour ton aide

Citation:

---

...contrainte guillotine...

---

Moi, c'était une de mes contraintes non négociables mais ça tombait bien, car, intuitivement, j'ai trouvé beaucoup plus simple la coupe guillotine :D et le SHF m'a bien aidé/conforté sur la manière de faire.

Citation:

---

J'ai du mal à voir comment je peux examiner toutes les solutions...

---

C'est bien pour ça que cela n'est valable que pour quelques pièces à placer :D
Mais tu peut réduire quand même pas mal en te donnant quelques contraintes supplémentaires pas difficile à respecter et relativement <utiles> : le placement doit toujours commencer par mettre une pièce dans un coin (par exemple le coin en bas à gauche pour rester dans les habitudes) et toutes les pièces doivent être adjacentes à une autre pièce par une de ces arrêtes (et pis la découpe telle que effectué dans le SHF te permet de les respecter automatiquement :ccool:).
Comme cela, tu réduit l'espace de recherche et donc, si ton problème est suffisamment petit, tu peut examiner toutes les solutions.

Citation:

---

Pour commencer peux tu me préciser la différence entre heuristique et méta-heuristique...

---

j'ai les mêmes définitions mais je me suis mal exprimé et j'ai fait un gros raccourci avec mon utilisation propre.
Mes implémentations de méta avaient pour tache de générer des solutions potentielles qui était ensuite envoyées à une heuristique de placement (une version modifiée de SHF) pour découpe puis évaluation de la solution. Par exemple, SHF, normalement commence par trier les pièces sur la hauteur en décroissant.
Dans mon utilisation, utilisée en sous-main par une méta, elle utilise les pièces dans l'ordre ou elles sont proposées par la couche supérieure, cad la solution proposée par la méta, a charge pour la méta, d'évaluer ensuite la découpe retournée par l'heuristique.

D'où mon raccourci inexact : heuristique > une solution, méta > n solutions.

Citation:

---

...these_elhayek...

---

Je l'ai lue aussi et j'ai essayé d'implémenter l'IMA mais pas plus car j'avais des bugs et pas le temps de les corriger (cylce de rédaction/correction du mémoire/réorganisation, etc).

Citation:

---

bornes

---

je ne suis pas matheux, mais si j'ai bien tout compris, grosso modo c'est pour limiter tes recherches : après avoir calculé tes bornes inférieures et supérieures, cela te permet de savoir pour ton jeu de pièces et ta planche, dans quel intervalle va se situer ta <gâche> et donc de ne pas chercher des solutions invalides.

Citation:

---

Intéressant et décrit en pseudo langage donc plus facile à implémenter pour moi.

---

tout pareil :D

Citation:

---

Oui avec plaisir...

---

Moi, c'était le BP dans l'imprimerie (BP 2D, coupe guillotine, coûts de mise en route et production à intégrer) mais il y a un certains nombre de contraintes/aspects que je n'ai pas traité par manque de bagage/expérience mathématique et de temps (pour me replonger dans mes cours).
En autres,

• format de planche variable : du fait de la prise en compte des coûts de mise en route/production, une solution (pour un jeu de pièce donné) peut être meilleure par ex. en utilisant une planche de grand format et une petite (sur deux machines A & B) que une seule d'un format un peu plus grand sur la machine C, etc...
• nombre de poses d'un modèle variable :
  Dans mon cas, par ex., 1000 pièces A, 400 pièces B et 800 pièces C ne doivent pas donner lieu à placement de 2200 pièces mais à celui de 3 modèles, chaque modèle pouvant être dupliqué un certain nombre de fois (les poses). La difficulté est que ce nombre de pose n'est pas connu à l'avance et qu'un même modèle peut avoir des poses sur plusieurs <planches> (de même format ou non), tout ceci dépendant entre autre du/des formats et la/les machine(s) les acceptant. Au final, bien sûr, l'impression en x exemplaires des planches doit donner au minimum le nombre d'exemplaire de chaque pièce, la surproduction étant autorisée mais dans des limites.
  J'ai l'impression que pour traiter cela, je dois me lancer dans la programmation linéaire mais mes cours sont très lointains et je ne vois pas comment démarrer :D Et là, je lance un appel à témoin : si quelqu'un a des pistes (même des mots clefs de recherche).. car parmi les papiers en accès libre que j'ai pu obtenir, je n'ai rien trouvé qui parle de cette <variante> du BP (ou alors, j'en ai trouvé mais rien compris et donc oublié :oops:)
  

Citation:

---

quels algos, etc.

---

<validés>

• Heuristiques : SHF et des versions modifiées de SHF : Elle travaille en couche sans rotation de pièces, je l'ai donc modifiée pour travailler sur la forme en totalité et ou en prenant en compte la rotation.
• Méta : Algo. génétiques, Recuit simulé, Hill climbing with restart

<non validés/utilisés pour cause de bugs>

• Heuristiques : IMA
• Méta : Fourmis

mon mémoire est ici : [ame="http://www.megaupload.com/?d=CWWSAWNP"]MEGAUPLOAD - The leading online storage and file delivery service@@AMEPARAM@@Filename:</font> <font style="font-family:arial; color:#FF6700; font-size:22px; font-weight:bold;">memoire.rar@@AMEPARAM@@memoire.rar[/ame]

L'implémentation est en python (en pj).
il se lance (si python est installé) en ligne de commande via "python bprunone.py <probleme.xml>. par exemple :

Code:

---

python bprunone.py p0.bp.xml

---

Avec cet exemple, précisément, pour un jeu de pièces, il va faire tourner différents algos (les critères sont dans le xml) sur différents formats de "planche" sans prise en compte des coûts et génerer des fichiers pour chaque couple algo/format de "planche" : jpg & description des découpes,etc...

ps : désolé pour le lien de la dont l'affichage est "bizarre", mais quoi que soit la description, c'est remplacé par megaupload...:(

Merci de faire partager ton travail.

Je suis actuellement en train de me pencher sur des problèmes de découpe 2D off-line, pièces et contenants variables, de type guillotine avec rotation possible.

Tous les informations données ici me seront très utiles.

Par contre je voulais dans un premier temps porter ton code en Java et l'archive des sources que tu fournis à des erreurs de compilation et d'éxécution (J'ai testé sous eclipse avec python 26 et 27).

Bon finalement j'ai réussi à faire marcher l'ensemble après quelques heures de pêche aux librairies python, et quelques modifs de code...

Bonjour,

Les bons algorithmes de placement sont difficile à faire et surtout très couteux en temps. Comme dit plus haut ils sont classé dans la famille NP complet. Cela signifie en gros que ton temps de calcul va croitre exponentiellement avec le nombre d'element. Pour beaucoup d'élement il est donc irréalisable en un temps normal.
Donc en pratique on réalise des approximations et on tente de parcourir le graphe des meilleurs solutions. Tout en sachant qu'il y a peut-être hors d'atteinte en un temps raisonnable une solution bien meilleure.

Je te suggère une approche simple en selectionnant la meilleure solution parmis 2 ou 3 en fonction d'un tri des pièces au préalable. Les plus grosse en premier, les plus petites en premier ou les plus longues(petites etc ...).
Ensuite essai de placer la pièce comme elle viens, sinon tourne la. Après plusieurs essai infructueux tu t'arrètes. Pour un nombre d'elements peu elevé tu ne devrais pas être très loin de la réalité.