Qu'est-ce que le problème de découpe ? Explication simple

Vous avez un panneau de mélaminé de 2440×1220 mm. Vous devez en tirer 12 pièces de dimensions variées. Comment les disposer pour gaspiller le moins de matière possible ? Ce problème, en apparence simple, est l’un des défis classiques de la recherche opérationnelle. Les mathématiciens l’étudient depuis les années 1960 sous le nom de « cutting stock problem » — le problème de découpe. Ce guide explique de quoi il s’agit, pourquoi il est difficile, et comment les logiciels modernes le résolvent au quotidien dans les ateliers.

Le problème expliqué simplement

Imaginez que vous devez découper 5 pièces dans une barre de métal de 6 mètres. Les pièces mesurent 2,5 m, 1,8 m, 1,2 m, 0,9 m et 0,6 m. Comment les répartir pour utiliser le minimum de barres ?

• Option A : une barre avec 2,5 m + 1,8 m + 1,2 m = 5,5 m (reste 0,5 m) et une barre avec 0,9 m + 0,6 m = 1,5 m (reste 4,5 m). Total : 2 barres, 5 m de chute.
• Option B : une barre avec 2,5 m + 1,8 m + 0,9 m + 0,6 m = 5,8 m (reste 0,2 m) et une barre avec 1,2 m (reste 4,8 m). Total : 2 barres, 5 m de chute.
• Option C : une barre avec 2,5 m + 1,2 m + 0,9 m + 0,6 m = 5,2 m (reste 0,8 m) et une barre avec 1,8 m (reste 4,2 m). Total : 2 barres, 5 m de chute.

Avec 5 pièces, il y a déjà des dizaines de combinaisons. Avec 50 pièces, le nombre dépasse les milliards. C’est ça, le problème de découpe.

D’où vient le problème : de la bobine de papier au panneau

Il est né dans l’industrie du papier et du bois de placage, bien avant qu’un atelier de menuiserie puisse en tirer quoi que ce soit.

La première formulation connue revient à Leonid Kantorovitch, qui décrit dès 1939 la découpe de matériaux dans un contexte de planification industrielle — des travaux qui lui vaudront le prix Nobel d’économie. Le sujet reste théorique jusqu’à ce que Paul Gilmore et Ralph Gomory publient en 1961, dans Operations Research, la méthode de génération de colonnes qui le rend calculable : au lieu d’énumérer tous les schémas de coupe possibles, on n’en fabrique un nouveau que lorsqu’il est capable d’améliorer la solution en cours. L’application visée était la refente de bobines de papier en laizes.

Ce détour par les origines explique une chose utile pour choisir un outil aujourd’hui : la formulation classique est unidimensionnelle. Une bobine se coupe en largeur, et c’est tout. Tout ce qui fait la difficulté du panneau — la seconde dimension, la rotation, la contrainte guillotine, le sens du fil — a été ajouté par-dessus, plus tard. C’est pourquoi un logiciel qui traite très bien le linéaire ne traite pas nécessairement bien la plaque : ce ne sont pas deux réglages du même moteur, ce sont deux générations du même problème.

Pourquoi c’est un problème NP-difficile

En informatique théorique, les problèmes sont classés par leur difficulté. Le problème de découpe appartient à la catégorie NP-difficile. Concrètement, cela signifie qu’il n’existe pas d’algorithme connu capable de trouver la solution parfaite en un temps raisonnable pour un grand nombre de pièces.

Le nombre de dispositions possibles croît de façon exponentielle :

• 5 pièces : 120 ordres de passage possibles
• 10 pièces : plus de 3,6 millions
• 20 pièces : plus de deux milliards de milliards
• 100 pièces, soit une cuisine complète : davantage que le nombre d’atomes de l’univers observable

Tester toutes les possibilités est physiquement impossible au-delà d’une vingtaine de pièces. Les algorithmes modernes ne cherchent donc pas la solution parfaite — ils cherchent une très bonne solution en un temps acceptable.

Les variantes du problème

Le problème de découpe existe en plusieurs variantes selon le domaine d’application :

Pour un menuisier ou un ébéniste, les variantes 2D (guillotine et libre) sont les plus courantes. La découpe 1D concerne les poseurs de sols, les métalliers et les fabricants de cadres.

Une dernière distinction sépare le manuel de l’atelier. La version académique suppose un matériau homogène, une quantité illimitée de panneaux identiques et des coupes sans épaisseur. La version de l’atelier ajoute le trait de scie, la contrainte guillotine imposée par la machine, le sens du fil sur les décors, un stock de chutes aux dimensions dépareillées, et une taille minimale sous laquelle un reste ne vaut plus la peine d’être conservé. Ces conditions ne compliquent pas seulement le calcul : elles changent la réponse. Un plan optimal au sens du manuel peut être tout simplement irréalisable sur une scie à panneaux — et c’est pour cela qu’un solveur de production ne cherche pas la meilleure solution mathématique, mais la meilleure solution exécutable.

Comment les algorithmes résolvent le problème

Puisque la solution exacte est hors de portée, les logiciels utilisent des approches heuristiques — des stratégies qui trouvent de bonnes solutions rapidement sans garantir l’optimum absolu.

Heuristiques gloutonnes (greedy) — L’algorithme place les pièces une par une, en choisissant à chaque étape le meilleur emplacement local. Rapide mais parfois sous-optimal. La plus connue est FFD (First Fit Decreasing) : trier les pièces de la plus grande à la plus petite, puis placer chacune dans le premier espace qui convient.

Programmation linéaire — Le problème est formulé comme un système d’équations et résolu par des méthodes mathématiques (simplex, branch-and-bound). Cette approche donne des résultats proches de l’optimum mais nécessite plus de temps de calcul.

Métaheuristiques — Algorithmes génétiques, recuit simulé, recherche tabou. Ces méthodes explorent l’espace des solutions en imitant des processus naturels (évolution, refroidissement). Elles excellent sur les problèmes de grande taille.

Approches hybrides — Les logiciels modernes combinent plusieurs stratégies : une heuristique rapide pour générer une première solution, puis une métaheuristique pour l’améliorer.

Une question revient toujours à ce stade : laisser tourner le calcul plus longtemps donne-t-il un meilleur plan ? Jusqu’à un certain point, puis cela cesse de compter. L’essentiel du gain arrive tôt, parce que les premières passes corrigent les décisions qui coûtent des panneaux entiers ; au-delà, la recherche affine des millimètres et confirme le plus souvent que le plan déjà trouvé est difficile à battre. Ce n’est donc presque jamais la durée du calcul qui explique un chantier qui gaspille : c’est une cote de panneau mal saisie, ou une contrainte de fil posée là où elle n’était pas nécessaire.

L’impact pratique dans votre atelier

Le problème de découpe n’est pas qu’une curiosité académique. Il a des conséquences directes sur votre activité :

Coût matière — La différence entre une disposition manuelle (20-30 % de chutes) et une disposition optimisée (5-10 %) représente des milliers d’euros par an pour un atelier actif.

Temps de préparation — Tracer manuellement un plan de découpe pour 40 pièces prend 30 à 60 minutes. L’algorithme le fait en quelques secondes.

Nombre de panneaux — Moins de chutes signifie moins de panneaux à acheter, transporter et stocker. Pour un projet de cuisine (40 pièces), l’optimisation peut économiser 2 à 3 panneaux.

Environnement — Les chutes de mélaminé et de MDF ne sont pas facilement recyclables. Réduire les chutes réduit votre empreinte environnementale.

Du problème théorique au logiciel pratique

Le lien entre la théorie et la pratique est direct. Quand vous lancez une optimisation dans un logiciel de découpe, voici ce qui se passe en coulisses :

1. Le logiciel convertit votre liste de pièces et vos panneaux en un problème mathématique structuré.
2. Il applique un ou plusieurs algorithmes pour explorer les dispositions possibles.
3. Il retient la meilleure solution trouvée dans le temps imparti.
4. Il génère un plan visuel que vous pouvez imprimer et suivre à l’atelier.

Tout cela se fait en quelques secondes, là où la résolution manuelle prendrait des heures — et produirait un résultat inférieur.

Ce que le menuisier doit retenir

Vous n’avez pas besoin de comprendre les mathématiques derrière le problème de découpe pour en bénéficier. Retenez trois points :

1. Le nombre de dispositions possibles est trop grand pour le cerveau humain dès que vous dépassez 10 pièces.
2. Les algorithmes trouvent des solutions proches de l’optimum en quelques secondes.
3. La différence entre une découpe manuelle et une découpe optimisée se mesure en centaines, voire milliers d’euros par an.