Un algoritmo para el Strip Packing Problem obtenido mediante la extracción de habilidades de expertos usando minería de datos

Abstract

La capacidad del ser humano para resolver problemas NP-Duro de forma manual no ha recibido la debida atención por la comunidad científica. Este artículo considera el problema del Strip Packing, que consiste en posicionar ortogonalmente un conjunto de piezas rectangulares dentro de un contenedor de ancho fijo y altura infinita, sin solaparlas, minimizando la altura alcanzada de las piezas dentro del contenedor. Se desarrolló un juego computacional que permite obtener soluciones manuales, propuestas por jugadores expertos, para distintas instancias del problema. La contribución del artículo consiste en presentar un algoritmo que se extrajo mediante patrones y minería de datos aplicada a soluciones encontradas por los jugadores expertos. El algoritmo generado se basa en elementos de árboles y heurísticas presentes en la literatura. Adicionalmente se presentan resultados computacionales, donde se logra encontrar la mejor solución conocida en 94.3% de un conjunto de instancias de la literatura y 79% para instancias generadas aleatoriamente.