El siempre esquivo acertijo que incluso los expertos en matemáticas se han rendido a resolver

En algún momento de la vida, la mayoría de la gente se ha parado sobre una losa de masa para galletas y se ha preguntado cuál es la mejor manera de cortar las galletas con el menor desperdicio posible. Ahora, incluso los expertos en matemáticas han renunciado a encontrar un algoritmo informático que responda a este tipo de problema geométrico.

¿Cómo podemos maximizar la masa mientras cortamos las galletas navideñas? ¿Cómo empacamos una maleta o llenamos un mueble de cocina aprovechando al máximo el espacio? Uno puede haber pensado, «debe haber una mejor manera de hacer esto». Considerar estas cuestiones demasiado profundamente parece ahora una completa pérdida de tiempo. La ciencia ahora está aquí para respaldar que es imposible, por el momento, averiguar qué funciona mejor para más de cuatro o cinco hombres de pan de jengibre picantes o galletas de árbol de Navidad.

El profesor asistente Mikkel Abrahamsen del Departamento de Ciencias de la Computación y dos colegas de investigación estudiaron lo difícil que es descubrir la forma óptima de empaquetar objetos en dos dimensiones sin superposición, un enigma que los científicos de la computación han solucionado durante décadas.

“Si bien los algoritmos nos permiten resolver problemas muy complejos, este sigue siendo demasiado complicado para las computadoras de hoy. Por ahora, no es posible empaquetar más de 5-10 objetos de manera óptima. Y nuestro resultado sugiere que este número probablemente no aumentará mucho por el momento ”, explica Mikkel Abrahamsen.

Empacar las cosas de manera óptima no es solo un problema ocasional en el hogar, sino en una variedad de industrias, incluida la fabricación de ropa y el procesamiento de metales. En cada caso, es importante cortar los materiales con el menor desperdicio posible. En el transporte marítimo, se aplica al embalaje de contenedores.

Embalaje de cuadrados

Izquierda: Embalaje óptimo de cinco cuadrados. Derecha: El empaquetado más conocido actualmente de once cuadrados unitarios en un cuadrado más grande. Crédito: Mikkel Abrahamsen

Solo cuatro galletas de jengibre

Conocemos el tamaño del contenedor cuadrado más pequeño en el que podemos embalar hasta 10 palets cuadrados de 1 × 1 metro. Pero simplemente agregando un palé adicional, se vuelve imposible calcular el tamaño óptimo del contenedor. Abrahamsen explica:

“A medida que se agregan más paletas, el tiempo de cálculo aumenta exponencialmente. Ni siquiera las mejores computadoras pueden mantener el ritmo. Teóricamente es posible. Pero según la velocidad a la que crece la potencia informática, probablemente pasarán millones de años antes de que podamos optimizar el manejo de algunos objetos adicionales «.

Además, si uno está trabajando con formas más complicadas, como el pan de jengibre en forma de árbol de Navidad, Mikkel Abrahamsen dice que las soluciones óptimas solo se pueden encontrar para hasta cuatro objetos hoy.

Infinidad de opciones

¿Qué lo hace tan difícil? Abrahamsen explica que el problema es similar a resolver ecuaciones de grado cinco o superior, y con muchas incógnitas. Aquí, se sabe que tal solución no siempre se puede escribir usando operaciones aritméticas regulares.

“Nuestro estudio demuestra que el problema tiene una naturaleza que nosotros en matemáticas llamamos continua, lo que en pocas palabras, significa que uno debe conocer todas las coordenadas en las que se pueden colocar las cookies y todos los ángulos en los que se pueden colocar. rotado ”, explica Abrahamsen.

Dado que las combinaciones posibles son infinitas, no hay forma de crear una lista de todas las ubicaciones necesarias para probar para encontrar una solución de embalaje óptima. En cambio, los algoritmos que resuelven los problemas de empaquetado de manera óptima deben ser más analíticos, lo que requiere mucho tiempo. Esto contrasta con muchos otros problemas algorítmicos conocidos, en los que se puede probar un número limitado de combinaciones antes de encontrar una que sea óptima. Por tanto, los problemas de empaque son mucho más difíciles.

Entonces, en la práctica, no hay mejores soluciones para los problemas de empaque que las que podemos encontrar los humanos.

“Tanto en la industria como en el mostrador de la cocina, debemos seguir estando satisfechos con nuestras soluciones menos que óptimas y tener la seguridad de que los humanos seguimos siendo mejores que las computadoras para este tipo de tareas, por el momento”, concluye Mikkel Abrahamsen.

  • En informática y matemáticas, los problemas de empaque son una clase de problemas de optimización que implican intentar empaquetar un número de objetos lo más cerca posible en dos o tres dimensiones. Los matemáticos han abordado los problemas de empaque durante cientos de años.
  • Con el nuevo resultado, el problema de empaquetamiento bidimensional se ha graduado a una clase superior de complejidad computacional, que se denota ∃ℝ. Anteriormente se creía que la pregunta pertenecía a la clase NP junto con el famoso “problema del viajante de comercio”, que trata de calcular el recorrido más corto para visitar todas las ciudades de una determinada lista.
  • La investigación fue realizada por Mikkel Abrahamsen del Centro BARC de la Universidad de Copenhague, en el Departamento de Ciencias de la Computación; Tillmann Miltzow de la Universidad de Utrecht en los Países Bajos y Nadja Seiferth de la Freie Universität Berlin en Alemania. La investigación ha recibido financiación de la Fundación VILLUM, entre otros.
  • El estudio ha sido presentado en la prestigiosa conferencia FOCS 2020 (IEEE Symposium on Foundations of Computer Science), que se celebrará del 16 al 19 de noviembre.

Referencia: “Marco para ∃R-Completitud de problemas de empaque bidimensionales” por Mikkel Abrahamsen, Tillmann Miltzow y Nadja Seiferth, 16 de abril de 2020.
arXiv: 2004.07558