For developers
Le problème de découpe en longueur 1D
Comment couper un ensemble de pièces à partir de barres standard en utilisant le moins de barres possible : voilà le problème de la découpe en longueur 1D. Un problème d'optimisation classique et réellement complexe. Voici sa définition, pourquoi la force brute ne fonctionne pas, et comment il est résolu en pratique, y compris par l'API de ce site.
Qu'est-ce que le problème de découpe en longueur 1D
Vous avez des barres d'une longueur fixe (par exemple 6000 mm) et une liste de pièces à produire, chacune avec sa longueur et sa quantité. Un schéma de coupe est une façon de découper une barre en plusieurs de ces pièces ; la longueur restante est de la perte. Le problème est de choisir les schémas, et le nombre de barres à couper pour chacun, afin de produire toutes les pièces requises avec le moins de barres possible, et donc le moins de perte. Une seule dimension, car seule la longueur compte : la lame traverse toute la section, donc la largeur et le profil n'entrent pas en jeu.
Le problème du bin packing 1D et sa complexité NP-difficile
Le problème de la découpe est une généralisation du bin packing 1D : le bin packing consiste à ranger des objets de tailles distinctes dans un minimum de conteneurs de taille fixe. Le problème de la découpe est le même, mais quand les objets se répètent en grandes quantités, on raisonne alors en schémas de coupe plutôt qu'en objets individuels. Le bin packing est un problème NP-difficile classique, et sa forme décisionnelle (ces objets rentrent-ils dans k conteneurs ?) est NP-complète. Le problème de la découpe hérite de cette complexité.
La raison est l'explosion combinatoire. Le nombre de schémas de coupe distincts augmente de façon exponentielle avec le nombre de longueurs de pièce, et le nombre de façons de répartir les quantités sur ces schémas explose à son tour. Il n'existe aucun algorithme connu qui trouve l'optimum garanti en temps polynomial, et à moins que P=NP, il n'y en aura jamais. Les vrais solveurs n'énumèrent donc pas tout ; ils sont plus malins pour écarter des possibilités.
Comment le résoudre en pratique
Heuristique du premier ajustement décroissant (FFD)
L'heuristique la plus courante : trier les pièces de la plus longue à la plus courte, puis placer chacune dans la première barre où elle rentre. On n'entame une nouvelle barre que si aucune n'a assez de place. C'est rapide et étonnamment efficace, garanti à environ 11/9 du nombre optimal de barres plus une petite constante. La plupart des outils s'arrêtent là ; un bon outil utilise FFD comme point de départ, pas comme solution finale.
Génération de colonnes (Gilmore et Gomory)
La formulation qui a rendu les grands problèmes solubles. Gilmore et Gomory (1961) ont décrit le problème avec une variable par schéma de coupe. Comme il y en a un nombre exponentiel, ils ont résolu la relaxation linéaire par génération de colonnes retardée : démarrer avec quelques schémas, puis générer le plus utile suivant en résolvant un sous-problème du sac à dos borné. La borne inférieure que cette méthode produit est réputée très juste.
Séparation et évaluation (branch-and-bound) et branch-and-price
Pour convertir cette relaxation fractionnaire en un nombre entier de barres, il faut une recherche, mais pas à l'aveugle. La méthode de séparation et évaluation explore l'arbre des choix entiers en utilisant la borne de la PL pour élaguer des branches entières qui ne peuvent améliorer le meilleur plan connu. Combinée à la génération de colonnes, elle devient le branch-and-price, la base des solveurs exacts de découpe.
Bornes inférieures, et une preuve
Un solveur sérieux ne retourne pas juste un plan. Il calcule une borne inférieure (issue de la relaxation PL, ou d'un simple argument de longueur totale) et compare. Quand un plan utilise exactement le nombre de barres que la borne prouve inévitable, il est prouvé optimal : aucun plan ne peut faire mieux, et le solveur peut l'affirmer au lieu de juste espérer un bon résultat.
Comment LinearCutting le résout
LinearCutting utilise cette approche : une heuristique rapide pour un plan réalisable instantané, puis une recherche guidée par la borne qui s'améliore jusqu'à atteindre la borne inférieure (prouvé optimal, et il vous le dit) ou jusqu'à épuisement du temps alloué, retournant alors le meilleur plan trouvé. Il modélise aussi la physique : le trait de scie à chaque coupe, l'éboutage, les chutes en quantité fixe et les coupes d'angle qui consomment plus de matière. Un plan qui ignore la lame n'est pas seulement sous-optimal, il est faux. Les tests de performance sont publics pour vous permettre de comparer les résultats avec n'importe quel autre outil.
La solution est exposée via une API JSON : envoyez vos pièces et vos barres, recevez un plan de coupe vérifié avec les schémas de débit, la perte, le nombre de réglages et l'information si le plan est optimal. Des clients officiels existent pour Python (pip install linearcutting) et JavaScript ou TypeScript (npm install linearcutting). L'appel ne prend que quelques lignes dans les deux langages.
Résolvez-le depuis votre code
N'écrivez pas un solveur, appelez-en un. Le moteur du calculateur de ce site est une API JSON avec des clients officiels Python et JavaScript, un niveau d'accès gratuit, et un exemple interactif dans la documentation.
pip install linearcutting npm install linearcutting