Discussion :

[sami_c]

Bonjour
Je voudrais écrire un programme permettant d'optimiser la coupe d'une lame aluminium. Voici le problème :
J'achète X lames toutes de même longueur L
Je voudrais produire N lames de longueurs respective l1, l2, l3 ... avec des quantités différences :
- n1 lames de longueur l1
- n2 lames de longueur l2
...
- ni lames de longueur li

bien sûr li < L, mais l1+l2+l3+...+li peur être >= ou <= à L

Je cherche donc à optimiser les quantités "ni" afin d'avoir le minium de perte quand je coupe une lame L
Je pense que le problème peut être résolu en utilisant un truc de recherche opérationnelle mais depuis que j'ai étudié ça à la fac (ça fait plus de 10 ans :p) je ne me rappelle plus de rien

merci d'avance

[sami_c]

En fait ce type de problème est de type "Sac à dos"
http://fr.wikipedia.org/wiki/Probl%C...sac_%C3%A0_dos

Une solution ? Quelqu'un a eu l'occasion de développer un algorithme pareil ?

[250rgv]

Bonjour,

Cherche plutôt 'Stock Cutting' ou 'Stock Cutting 1D'.

J'ai plus travaillé sur du Bin packing 2D mais voici ma biblio, cela devrait te donner quelques points de départ.

1. ALVAREZ-VALDES R., PARAJON A., TAMARITt J.M., A Computational Study of LP-Based Heuristic Algorithms for Two-Dimensional Cutting Stock Problems,Rapport, Université de Valence, Espagne, 19p.
2. ALVIM A.C.F., GLOVER F., RIBEIRO C.C., ALOISE D.J.,1999. Local Search for the bin packing problem, In Extended Abstracts of the 3rd Metaheuristics International Conference, Angra dos Reis, Brésil, p7-12 .
3. ALVIM A.C.F., GLOVER F., RIBEIRO C.C., ALOISE D.J.,2002. A Hybrid Improvement Heuristic for The Bin Packing Problem, In Extended Abstracts of the 4th Metaheuristics International Conference, Porto, Portugal, p63-68.
4. BEISIEGEL B., KALLRATH J., KOCHETOV Y., RUDNEV A.,2005. Simulated Annealing Based Algorithm for the 2D Bin Packing Problem With Impurities, In Operations Research Proceedings, Springer, Heidelberg, Allemagne, p309-314.
5. BELOV G., SCHEITHAUER G.,2003a. A Branch & Cut & Price Algorithm for One Dimensional Stock Cutting and Two Dimensional Two Stage Cutting, Rapport, NM,Université de Dresde, Allemagne, 28p.
6. BELOV G., SCHEITHAUER G.,2003b. A branch-and-cut-and-price algorithm for one- and twodimensional two-staged cutting (stock) problems, Rapport, NM,Université de Dresde, Allemagne, 52p.
7. BENFOLD W., MANFRIN M., MANUEL A., MANSO R., SPINELLA S.,2005. A Genetic Algorithm for 2D Glass Cutting Problem, Rapport, IRIDIA, Université Libre de Bruxelles, Belgique, p9.
8. CHAUVET F., OULD HAOUBA A., PROTH J.M., 1998. Cutting Problem : A Fast Algorithm For Computing A Near-Optimal Solution, Rapport n°3421, INRIA, France, 24p.
9. CHRISTOFIDES N., WHITLOCK C., 1977. An algorithm for the two dimensional cutting problems, Operation Research, vol.25, n°1, p30-44.
10. CLAUTIAUX F., 2005. Bornes Inférieures et Méthodes Exactes pour le Problème de Bin Packing en Deux Dimensions Avec Orientation Fixe, Thèse, Université de technologie, Compiègne, France, 134p.
11. COFFMAN E.G., CSIRIK Jr. J., JOHNSON D.S., WOEGINGER G.J., 2004. An Introduction to Bin Packing, Bibliographie, Université de Szeged, Hongrie, 50p.
12. DORIGO M., DI CARO G., 1999. The Ant Colony Optimization Meta-Heuristic, IRIDIA, Université Libre de Bruxelles, Belgique, 27p.
13. DUCATELLE F., 2001. Ant Colony Optimisation for Bin Packing and Cutting Stock Problems, Master of Science, Université d'Édimbourg, Ecosse, 77p.
14. DYCKHOFF H., SCHEITHAUER G., TERNO J., 1997. Cutting & Packing, Bibliographie, 22p.
15. EL HAYEK J.,2006. Le Problème de Bin-Packing en 2D, le Cas Non-Orienté - Résolution Approchée et Bornes Inférieures, Thèse, Université de technologie, Compiègne, France, 114p.
16. FAINA L., 2000. A Global Optimization Algorithm for the Three Dimensional Packing Problem, Université de Perouse, Italie, 22p.
17. FAINA L. Simulated Annealing, Université de Perouse, Italie, 4p.
18. FALKENAUER E., 1996. A Hybrid Grouping Genetic Algorithm for Bin Packing, Journal of Heuristics, vol.2, p 5-30.
19. FALKENAUER E., DELCHAMBRE A., 1992. A Genetic Algorithm for Bin Packing and Line Balancing, in Proceedings of the 1992 IEEE International Conference on Robotics and Automation, Page : 95/97 7p.
20. FEKETE S.P., SCHEPERS J., 1998. New Classes of Lower Bounds for Bin Packing Problems, 10p.
21. FEKETE S.P., SCHEPERS J., 1999. A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing, Mathematics of Operations Research, vol.29.
22. FEKETE S.P., SCHEPERS J., 2000a. On more Dimensional Packing I : Models, Rapport n°97.288, Université de Berlin, Allemagne, 17p.
23. FEKETE S.P., SCHEPERS J., 2000b. On more Dimensional Packing II : Bounds, Rapport n°97.289, Université de Berlin, Allemagne, 22p.
24. FEKETE S.P., SCHEPERS J., 2000c. On more Dimensional Packing III : Exact Algorithms, Rapport n°97.290, Université de Berlin, Allemagne, 31p.
25. FEKETE S.P., SCHEPERS J., 2001. New Classes of Fast Lower Bounds for Bin Packing Problems, Rapport n°97.290, Université de Berlin, Allemagne, 21p.
26. GILMORE P.C. Et GOMORY R.E., 1961. A linear programming approach to the cutting-stock problem, Operations Research vol.9, p849-859.
27. GILMORE P.C. Et GOMORY R.E., 1963. A linear programming approach to the cutting-stock problem (part II), Operations Research vol.11, p863-887.
28. GLOVER F., LAGUNA M., 1997. Tabu Search, 18p.
29. HAN X., IWAMA K., YE D., ZHANG G., 2006. Strip Packing vs. Bin Packing, Algorithmic Aspects in Information and Management, Springer Berlin / Heidelberg, Allemagne, p358-367.
30. HARWIG J.M., BARNES J.W., MOORE J.T., 2004. An adaptive Tabu Search approach for 2D orthogonal packing problems, to appear in Military Operations Research, 11, 2006 , 31p.
31. HERTZ A., TAILLARD E., DE WERRA D., 1995. A Tutorial On Tabu Search, 13p.
32. HERZ. J.C., 1972. Recursive Computational Procedure For Two-Dimensional Stock Cutting, IBM,Journal of Research and Development, vol.16,n° 5, p 462-469.
33. HINTERDING R., JULIFF K., 1993. A Genetic Algorithm for Stock Cutting : an Exploration of Mapping Schemes, 13p.
34. IMAHORI S., 2004. Studies on Local Search Algorithms for Cutting and Packing Problems, Thèse, Université de Kyoto, Japon, 130p.
35. IMAHORI S., 2005. Rectangle Packing : How to Represent Solutions, 2nd ESICUP Meeting, Southampton, Angleterre, 23p.
36. KARELAHTI J., 2002. Solving the Cutting Stock Problem in the Steel Industry, Thèse, Université d'Helsinki, 86p.
37. LASDON L.S., 2002. Optimization Theory For Large Systems, Dover Publications Inc, 544p.
38. LEVINE J., DUCATELLE F., 2003. Ant Colony Optimisation and Local Search for Bin Packing and Cutting Stock Problems, Journal of the Operational Research Society, vol.93, 16p.
39. LION P., 2004. Métiers de la Communication et des Industries Graphiques, Impression offset et connaissances associées, Editions Charles Corlet,117p.
40. LODI A., 1999. Algorithms for Two Dimensional Bin Packing and Assignment Problems, Thèse, Université de Bologne, Italie, 208p.
41. LODI A., MARTELLO S., VIGO D., 1999. Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems, INFORMS Journal on Computing, vol.11, n°4, p345-357.
42. LODI A., MARTELLO S., VIGO D., 2004a. Models and Bounds for Two-Dimensional Level Packing Problems, Journal of Combinatorial Optimization, vol.8, p363-379. Page : 96/97
43. LODI A., MARTELLO S., VIGO D., 2004b.TSpack : A Unified Tabu Search Code for Multi-Dimensional Bin Packing Problems, Annals of Operations Research, vol.131, n°1-4, p203-2013.
44. MARTELLO S., PISINGER D., VIGO D., 1997. The Three-Dimensional Bin Packing Problem, Rapport DEIS-OR-97-6, Université de Bologne, Italie, 25p.
45. MARTELLO S., VIGO D.. Two Dimensional Bin Packing Problems : Models and Algorithms, Support de cours, Université de Bologne, Italie, 42p.
46. NTENE N., VAN VUUREN JH, 2006. A Survey and Comparison of Level Heuristics for The 2D Oriented Strip Packing Problem, Université de Stellenbosch, Afrique du Sud, 27p.
47. PISINGER D., 1995. Algorithms for the Knapsack Problem, Thèse, Université de Copenhague, 200p.
48. PISINGER D., 2002. Heuristics for the Container Loading Problem, European Journal of Operational Research, vol.141,n°2, p382-392.
49. PISINGER D., EGEBLAD J., 2006. Heuristic Approaches for the Two- And Three-Dimensional Knapsack Packing Problems, Rapport n°6-13, Université de Copenhague, 30p.
50. RUSSEL S., NORVIG P., 2003. Résolution de problèmes par l'exploration, Exploration informée, In Intelligence Artificielle, Person Education, p67-154.
51. BEN MESSAOUD S., CHU C., ESPINOUSE M.L., 2003. SHF : Une Nouvelle Heuristique pour le Problème de Découpe Guillotine en 2D, In Proceedings of MOSIM'03, Toulouse, France, 6p.
52. SCHEITHAUER G., TERNO J., 1993. Modelling of Packing Problems, Optimization, vol.28, p63-84.
53. SEGARAN T., 2007. Optimization. In Programming Collective Intelligence, O'Reilly, p86-100.
54. SEGOUIN A., MARTINEZ Y., 1992. Rapport de stage, Université d'Orléans, 25p.
55. YAGIURA M., IBARAKI T., 1996. Genetic and Local Search Algorithms as Robust and Simple Optimization Tools, in proceedings of 1st Metaheuristics International Conference, Kluwer Academic Press, p63-82.
56. YALAOUI A., CHU C., 2006. Optimisation par Colonies de Fourmis Hybride - Découpe a Deux Dimensions 2BP/O/G, In Proceedings of MOSIM'06, Rabat, Maroc, 7p.

[sami_c]

Merci
Je ne pensais pas que ça allait être aussi compliqué que ça !!!

[250rgv]

C'est pas le problème le plus compliqué non plus
La biblio. que je t'ai donné se concentrait principalement sur des problèmes en 2D, l'idée est que tu t'en serve de point de départ pour te faire la tienne.
Deux bons filons (d'où vient une grande partie de la biblio) : Google Scholar & CiteSeerX

A noter, selon ton nombre de lames à "traiter", ton implémentation, le langage et la machine qui fera tourner le tout, la force brute peut aussi fonctionner , après, pour les différents algorithmes, c'est selon la qualité de la solution que tu recherche : la meilleure - et là, ben, y faut ce qu'il faut - ou une bonne, voire très bonne et tu peut utiliser des méta-heuristiques qui sont (pour moi dont les cours de math. remontent à quelques années) plus simples à implémenter, voir t'amuser à mélanger méthodes exactes et métas.

[250rgv]

un thread sur dvlp sur le même problème que toi.

Toujours ici, il y en d'autres en utilisant "stock cutting" comme mots de recherche

[sami_c]

un thread sur dvlp sur le même problème que toi.

merci c'est exactement le même sujet !