Resolución del problema de la mochila mediante la metaheurística PSO acelerada con JAX

ERMANTRAUT, JOEL; CRISOL, TOMAS; DÍAZ, ARIEL; BALMACEDA, LEANDRO; ROSTAGNO, ADRIÁN; AGGIO, SANTIAGO; BLANCO, ANÍBAL M.; IPARRAGUIRRE, JAVIER

Congreso; 49JAIIO - SIIIO: Simposio Argentino de Informática Industrial e Investigación Operativa; 2020

Un problema muy desafiante de la matemática aplicada moderna es la optimización numérica de problemas NP duros. Muchos problemas de interés a las ciencias e ingenierías caen en esta categoría y resulta deseable contar con algoritmos de búsqueda e implementaciones computacionales, que puedan pro-porcionar soluciones de aceptable calidad, en tiempos compatibles con aplicacio-nes prácticas. Una combinación que ha demostrado buenas prestaciones en múl-tiples aplicaciones son las metaheurísticas aceleradas en placas gráficas (GPU). Sin embargo, las herramientas típicas que permiten la programación de acelera-dores demandan mucho conocimiento del hardware por parte del usuario. En este trabajo se explora el desempeño de una implementación de la metaheurística PSO sobre hardware masivamente paralelo a través de un compilador ?just in time? llamado JAX. Esta herramienta permite acelerar programas usando un lenguaje de programación orientado a la productividad tal como lo es Python. Se utiliza como caso de estudio el clásico problema de la mochila, el cual admite la gene-ración de instancias arbitrariamente complejas de manera sencilla. Los resultados muestran que es posible lograr aceleraciones de hasta 83 veces empleando como plataforma arquitecturas de computadoras contemporáneas. Adicionalmente, se publican resultados en el uso de unidades tensoriales, los cuales muestran el po-tencial del uso de estos dispositivos.