For developers
El problema de corte de stock 1D
Cómo cortar un conjunto de piezas requeridas a partir de barras de material usando el mínimo de barras es el problema del corte de material 1D: un problema de optimización clásico y genuinamente difícil. Aquí se explica en qué consiste, por qué no admite una solución por fuerza bruta y cómo se resuelve en la práctica, incluida la API de esta web.
En qué consiste el problema del corte de material 1D
Se parte de unas barras de material de longitud fija (p. ej. barras de 6000 mm) y una lista de piezas requeridas, cada una con su longitud y cantidad. Un patrón de corte es una forma de cortar una única barra para obtener algunas de esas piezas; la longitud sobrante es residuo. El problema es elegir los patrones, y cuántas barras cortar con cada uno, para producir todas las piezas requeridas con el mínimo número de barras de material, o lo que es lo mismo, el mínimo residuo. Una dimensión, porque solo importa la longitud: la hoja atraviesa toda la sección, así que la anchura y el perfil no intervienen.
El problema de empaquetado 1D y por qué es NP-difícil
El problema del corte de material es una generalización del empaquetado unidimensional (bin packing 1D): el empaquetado consiste en colocar un conjunto de elementos de distintos tamaños en el menor número posible de contenedores de tamaño fijo. El corte de material es la misma cuestión, pero con piezas que se repiten en grandes cantidades, por lo que se razona sobre patrones en lugar de piezas individuales. El empaquetado es uno de los problemas clásicos NP-difíciles, y su forma de decisión —¿caben estos elementos en k contenedores?— es NP-completa. El corte de material hereda esa dificultad.
La razón es la explosión combinatoria. El número de patrones de corte distintos crece exponencialmente con el número de tamaños de pieza, y las formas de distribuir las cantidades entre esos patrones crecen de forma explosiva sobre esa base. No se conoce ningún algoritmo que encuentre el óptimo garantizado en un tiempo que escale de forma polinómica con la entrada, y a menos que P sea igual a NP, no lo habrá. Por eso los optimizadores reales no lo enumeran todo, sino que descartan de forma inteligente las posibilidades.
Cómo se resuelve en la práctica
Primer ajuste decreciente (FFD)
La heurística de batalla: ordenar las piezas requeridas de mayor a menor longitud y luego colocar cada una en la primera barra en la que quepa, usando una barra nueva solo cuando no queda sitio en ninguna. Es rápida y sorprendentemente buena, con resultados probados de alrededor de 11/9 del número óptimo de barras más una pequeña constante. La mayoría de las herramientas se quedan ahí; una buena usa FFD como punto de partida, no como el resultado final.
Generación de columnas (Gilmore y Gomory)
La formulación que hizo manejables los casos de gran tamaño. Gilmore y Gomory (1961) plantearon el problema con una variable por patrón de corte y, al haber un número exponencial de patrones, resolvieron la relajación lineal mediante la generación retardada de columnas: se empieza con unos pocos patrones y se genera repetidamente el siguiente más útil resolviendo un subproblema de la mochila acotado. El límite inferior que produce es famoso por lo ajustado que es.
Ramificación y acotación, y ramificación y precio
Para convertir esa relajación fraccionaria en un número entero de barras hay que buscar, pero no a ciegas. La ramificación y acotación explora el árbol de decisiones enteras usando el límite de la programación lineal (PL) para podar ramas enteras que no pueden superar el mejor plan encontrado hasta ahora. Combinado con la generación de columnas, se convierte en la ramificación y precio, la base de la mayoría de los optimizadores de corte exactos.
Límites inferiores y una prueba
Un optimizador serio no solo devuelve un plan: calcula un límite inferior (a partir de la relajación de PL o de un argumento más simple de longitud total) y lo compara. Cuando un plan usa exactamente las barras que el límite demuestra que son inevitables, es óptimo de forma demostrable: ningún plan puede mejorarlo, y el optimizador puede afirmarlo en lugar de cruzar los dedos.
Cómo lo resuelve LinearCutting
LinearCutting ejecuta esta secuencia: una heurística rápida para un plan factible instantáneo, luego una búsqueda guiada por el límite inferior que sigue mejorando hasta que iguala dicho límite (óptimo demostrable, y se lo dice) o agota su tiempo y devuelve el mejor plan que encontró. También modela la física: ancho de corte en cada corte, saneado de extremos, retales de cantidad fija y cortes en ángulo que consumen más material. Porque un plan que ignora la hoja no es solo subóptimo, es incorrecto. Los trabajos de referencia se publican para que pueda comparar los resultados con cualquier otra herramienta.
Se expone como una API JSON: envíe sus piezas y su material, y reciba un plan de corte verificado con los esquemas, el residuo, el número de ajustes y si el plan alcanzó el límite óptimo. Hay clientes oficiales para Python (pip install linearcutting) y JavaScript o TypeScript (npm install linearcutting), por lo que llamarlo requiere unas pocas líneas en cualquiera de los dos lenguajes.
Resuélvalo desde su código
No escriba un optimizador, llame a uno. El mismo motor que utiliza la calculadora de esta web es una API JSON con clientes oficiales para Python y JavaScript, un plan público gratuito y un ejemplo en vivo que puede ejecutar en la documentación.
pip install linearcutting npm install linearcutting