Corte con guillotina

El corte con guillotina es el proceso de producir formas rectangulares pequeñas de dimensiones fijas a partir de una hoja rectangular grande determinada, utilizando únicamente cortes de guillotina. Un corte con guillotina (también llamado corte de borde a borde) es una línea bisectriz recta que va desde un borde de un rectángulo existente hasta el borde opuesto, de manera similar a lo que hace una guillotina para papel.
El corte con guillotina es particularmente común en la industria del vidrio. Las láminas de vidrio se marcan en líneas horizontales y verticales y luego se rompen según estas líneas para obtener paneles más pequeños.​ El procedimiento también es útil para cortar placas de acero, cortar láminas de madera para fabricar muebles, y para cortar el cartón empleado en la fabricación de cajas.​
Existen varios problema de optimización relacionados con el corte con guillotina, tales como maximizar el área total de las piezas producidas o su valor total; o también minimizar la cantidad de desperdicios (partes no utilizadas) de la hoja grande, o el número total de hojas. Se han estudiado en geometría discreta, investigación de operaciones e ingeniería industrial.​
Un problema relacionado pero diferente es la partición con guillotina. En este problema, las dimensiones de los rectángulos pequeños no están fijadas de antemano. El desafío surge del hecho de que la hoja original puede no ser rectangular, sino que puede ser cualquier polígono rectilíneo. En particular, podría contener agujeros (que representan defectos en la materia prima). El objetivo de optimización suele ser minimizar el número de rectángulos pequeños o minimizar la longitud total de los cortes.
Los siguientes términos y notaciones se utilizan a menudo en la literatura sobre corte con guillotina.
Algunos problemas aceptan entradas adicionales, como se explica a continuación. El objetivo es cortar del rectángulo en bruto algunos rectángulos más pequeños que tengan las dimensiones deseadas. A menudo se hacen las siguientes suposiciones:​
En el problema de verificación de patrones, hay un patrón de corte dado como una secuencia de puntos (xi,yi), para i en 1,...,m, donde (xi,yi) es la coordenada inferior izquierda del rectángulo i (hay un único rectángulo de cada dimensión objetivo). El objetivo es decidir si este patrón se puede implementar utilizando únicamente cortes de guillotina y, de ser así, encontrar una secuencia para dichos cortes.
Una condición necesaria obvia es que no se superpongan dos rectángulos de entrada en ambas dimensiones. Ben Messaoud, Chengbin y Espinouse​ fijaron una condición más fuerte, que es a la vez necesaria y suficiente. Los rectángulos de entrada están ordenados de izquierda a derecha, de modo que x1 = ... = xm. Existe una permutación p sobre los índices tal que, con esta permutación, los rectángulos quedarían ordenados de abajo hacia arriba, es decir, yp(1) = ... = yp(m). Dados cuatro índices i1 = i2 y j1 = j2, el conjunto E(i1,i2,j1,j2) contiene los índices de todos los rectángulos cuya esquina inferior izquierda está en el rectángulo [xi1,xi2] X [yp(j1),yp(j2)]. Un patrón de corte es un patrón de guillotina si y solo si, para todas las cuaternas de índices i1 = i2 y j1 = j2, al menos se cumple una de las siguientes condiciones para E(i1,i2,j1,j2):
La condición 2 implica que los rectángulos en E(i1,i2,j1,j2) pueden separarse mediante un corte vertical (que va entre los dos intervalos horizontales). La condición 3 implica que los rectángulos en E(i1,i2,j1,j2) se pueden separar mediante un corte horizontal. Todas las condiciones juntas implican que, si cualquier conjunto de rectángulos adyacentes contiene más de un elemento, entonces pueden separarse mediante algún corte con guillotina.
Esta condición se puede verificar mediante el siguiente algoritmo:
Encontrar un corte con guillotina para un patrón determinado se realiza de la siguiente manera:
La ordenación de los pasos se realiza una vez y el paso de fusión se realiza m-1 veces. Por lo tanto, el tiempo de ejecución de todo el algoritmo es O(m).
Cuando el algoritmo devuelve "sí", también produce una secuencia de cortes de guillotina; cuando devuelve "no", también produce subconjuntos específicos de rectángulos que no pueden separarse mediante cortes con guillotina.
La condición necesaria y suficiente se puede utilizar para presentar el problema de corte de tiras con guillotina como programa lineal entero mixto.​ Su modelo tiene 3n/4 variables binarias y 2n restricciones, y no se considera útil en la práctica.
Estas son variantes de los problemas bidimensionales de corte de material, empaquetado en contenedores y empaquetado de rectángulos, donde los cortes están obligados a ser cortes con guillotina.​
El caso especial en el que solo hay un tipo (es decir, todos los rectángulos objetivo son idénticos y están en la misma orientación) se denomina problema de "carga de palet con guillotina". Tarnowski, Terno y Scheithauer​ idearon un algoritmo de tiempo polinomial para resolverlo.
Sin embargo, cuando hay dos o más tipos, todos los problemas de optimización relacionados con el corte con guillotina son NP-hard. Debido a su importancia práctica, se han ideado varios algoritmos exactos y algoritmos de aproximación.
La separación con guillotina es un problema relacionado en el que la entrada es una colección de n formas convexas separadas por pares en el plano, y el objetivo es separarlos usando una secuencia de cortes de guillotina. Obviamente, puede que no sea posible separarlas todas. Jorge Urrutia Galicia planteó la cuestión de si es posible separar una fracción constante de ellos,​ es decir, si existe una constante c tal que, en cualquier colección de tamaño n, hay un subconjunto de tamaño cn que es separable con guillotina.
Pach y Tardos​ demostraron que:
Abed, Chalermsook, Correa, Karrenbauer, Pérez-Lantero, Soto y Wiese​ demostraron que:
Khan y Pittu​ demostraron:
Algunas variantes del problema incluyen: