For developers
Il problema del taglio di barre (1D)
Come tagliare una serie di lunghezze richieste da barre di materiale standard utilizzando il minor numero di barre è il problema del taglio di barre (1D): un classico problema di ottimizzazione, genuinamente complesso. Ecco di cosa si tratta, perché non può essere risolto con la forza bruta e come viene risolto nella pratica, anche dall'API di questo sito.
Cos'è il problema del taglio di barre (1D)
Vengono fornite delle barre di materiale di lunghezza fissa (ad esempio barre da 6000 mm) e una lista di pezzi richiesti, ciascuno con una lunghezza e una quantità. Uno schema di taglio è un modo per tagliare una singola barra di materiale per ottenere alcuni di quei pezzi; la lunghezza che avanza è scarto. Il problema consiste nello scegliere gli schemi e il numero di barre da tagliare per ciascuno schema, in modo da produrre tutti i pezzi richiesti utilizzando il minor numero possibile di barre, e quindi minimizzando lo scarto totale. È un problema monodimensionale perché conta solo la lunghezza: la lama attraversa l'intera sezione, quindi larghezza e profilo non influiscono.
Bin packing 1D e perché è NP-hard
Il problema del taglio di barre è una generalizzazione del bin packing 1D: il bin packing richiede di inserire un set di articoli di dimensioni distinte nel minor numero di contenitori di dimensioni fisse. Il cutting stock è la stessa cosa, ma con grandi quantità di articoli ripetuti, quindi si ragiona in termini di schemi di taglio anziché di singoli articoli. Il bin packing è uno dei classici problemi NP-hard, e la sua forma decisionale (possono questi articoli entrare in k contenitori?) è NP-completa. Il problema del taglio di barre ne eredita la complessità.
La ragione è l'esplosione combinatoria. Il numero di schemi di taglio distinti cresce in modo esponenziale con il numero di dimensioni dei pezzi, e il numero di modi per distribuire le quantità tra quegli schemi esplode a sua volta. Non esiste un algoritmo noto che trovi l'ottimo garantito in un tempo che scali polinomialmente con l'input e, a meno che P non sia uguale a NP, non esisterà. I solutori reali quindi non enumerano tutto, ma escludono in modo intelligente intere classi di possibilità.
Come viene risolto nella pratica
First-fit-decreasing (FFD)
L'euristica più comune: ordina i pezzi richiesti dal più lungo al più corto, poi posiziona ciascuno sulla prima barra in cui entra, aprendo una nuova barra solo quando non c'è più spazio. È veloce e sorprendentemente efficace, con un risultato garantito entro circa 11/9 del numero ottimale di barre più una piccola costante. Molti strumenti si fermano qui; uno strumento valido usa l'FFD come punto di partenza, non come traguardo.
Generazione di colonne (Gilmore e Gomory)
La formulazione che ha reso trattabili i problemi di grandi dimensioni. Gilmore e Gomory (1961) hanno descritto il problema con una variabile per ogni schema di taglio e, dato il numero esponenziale di schemi, hanno risolto il rilassamento lineare tramite generazione ritardata di colonne: si parte con pochi schemi e si genera ripetutamente quello successivo più utile risolvendo un sottoproblema dello zaino (knapsack). Il limite inferiore che produce è notoriamente stretto.
Branch-and-bound e branch-and-price
Per trasformare quel rilassamento frazionario in un numero intero di barre, è necessario effettuare una ricerca, ma non alla cieca. Il branch-and-bound esplora l'albero delle scelte intere usando il limite LP per potare interi rami che non possono migliorare il piano migliore trovato finora. Combinato con la generazione di colonne, diventa branch-and-price, la base della maggior parte dei solutori esatti per il taglio di barre.
Limiti inferiori e una prova
Un solutore serio non restituisce solo un piano, ma calcola un limite inferiore (dal rilassamento LP o da un più semplice calcolo sulla lunghezza totale) e lo confronta. Quando un piano utilizza esattamente tante barre quante il limite dimostra essere inevitabili, è provatamente ottimale: nessun piano può fare di meglio, e il solutore può confermarlo invece di sperare di essere stato fortunato.
Come lo risolve LinearCutting
LinearCutting esegue questa procedura: un'euristica veloce per un piano fattibile istantaneo, poi una ricerca guidata da un limite che continua a migliorare finché non raggiunge il limite inferiore (provatamente ottimale, e te lo comunica) o esaurisce il tempo a disposizione e restituisce il miglior piano trovato. Modella anche la fisica: lo spessore del taglio, il rifilo di testa, i ritagli a quantità fissa e i tagli angolati che consumano materiale extra, perché un piano che ignora la lama non è solo subottimale, è sbagliato. I benchmark sono pubblici, così puoi confrontare i risultati con qualsiasi altro strumento.
È esposto come API JSON: invia i tuoi pezzi e il materiale, ricevi un piano di taglio verificato con i layout, lo scarto, il numero di impostazioni e la conferma se il piano ha raggiunto il limite ottimale. Ci sono client ufficiali per Python (pip install linearcutting) e JavaScript o TypeScript (npm install linearcutting), quindi basta qualche riga di codice per chiamarlo in entrambi i linguaggi.
Risolvilo dal tuo codice
Evita di scrivere un solutore e usane uno già pronto. Lo stesso motore del calcolatore di questo sito è un'API JSON con client ufficiali per Python e JavaScript, un piano gratuito e un esempio funzionante nella documentazione.
pip install linearcutting npm install linearcutting