Proyectos de investigadores del Núcleo se adjudican FONDECYT 2017

Jeremy Barbay, Roberto Cominetti, Ivan Rapapaort, Gonzalo Navarro, Fernando Ordoñez y Andreas Wiese lideran proyectos que fueron recomendadas para ser adjudicadas en el presente proceso del concurso FONDECYT regular. Asimismo, Fabio Botler y Jackie Zhang obtuvieron proyectos FONDECYT de postdoctorado. Felicitaciones a todos!

En particular Fernando Ordoñez, Andreas Wiese y Jérémy Barbay lideran proyectos de optimización en las áreas de seguridad, embalaje y ciencias de la computación respectivamente.

Proporcionar herramientas eficientes de apoyo a la toma de decisiones sobre cómo planificar las patrullas de seguridad para proteger la infraestructura crítica existente o para prevenir hechos delictuales es el objetivo de la investigación “Addressing Problem Size and Risk in Security Games”, liderada por Fernando Ordóñez, actual Director de Ingeniería Industrial e investigador del Núcleo Milenio Información y Coordinación en Redes.

El proyecto de investigación asume los ritmos de vigilancia desde la perspectiva del Juego de Stackelberg.

“Una serie de aplicaciones exitosas recientes para abordar este problema representan la interacción entre el defensor y los atacantes como un juego de Stackelberg. Resolver estos juegos (de Stackelberg) para situaciones reales de seguridad requiere un modelado detallado que, a menudo, conduce a problemas de optimización masiva difíciles de resolver con las herramientas existentes. Además, los modelos de juego estándar de Stackelberg suponen que el objetivo del defensor es encontrar la estrategia que optimice su utilidad esperada. Sin embargo, en un dominio de seguridad, los peores escenarios pueden resultar catastróficos, por lo que un modelo de utilidad esperado no es apropiado”, detalla Ordóñez.

Fernando-Ordoñez-Fondecyt-482x600

Fernando Ordoñez

En este marco, su investigación se propone abordar estas dos dificultades centrándose en el desarrollo de métodos de descomposición para estos juegos de Stackelberg e introduciendo nuevas formulaciones en las que se tome en cuenta la preferencia de riesgo de los defensores.

Por su lado, el investigador del Núcleo Milenio Información y Coordinación en Redes y también académico de Ingeniería Industrial Andreas Wiese, lidera el proyecto “Approximation algorithms for packing problems”, que también está en la recta final del Concurso Regular Fondecyt 2017.

Wiese pretende abordar los problemas de embalaje, fundamentales dentro de la optimización combinatoria, y ampliamente estudiados durante las últimas décadas, en particular en las comunidades de informática y programación matemática.

Además de ser interesantes por derecho propio, a menudo aparecen como subproblemas o como características de problemas más grandes, por ejemplo, de recursos limitados como la memoria, los anchos de banda de transmisión o la energía que se necesita para ellos sin contar las aplicaciones prácticas.

Andreas-Wiese-profesor-visitante-horizontal

“Por ejemplo, al cargar un camión o un buque, hay que encontrar la manera de ubicar los objetos en el espacio disponible, posiblemente sujetos a restricciones adicionales como, entre otros, el equilibrio del peso de los objetos embalados. Otros ejemplos son los ajustes como la fabricación industrial donde se busca recortar materias primas como el acero o la madera, así como también optimizar el uso de un canal de transmisión como un cable óptico o una conexión inalámbrica. También se debe considerar cuando los elementos a empaquetar son solicitudes de transmisión que difieren en el ancho de banda requerido y la ventana de tiempo respectiva durante la cual intentan usar el canal. Por último, cuando se planifican cálculos en grandes grupos, memoria y recursos computacionales limitados también plantean problemas de empaque”, describe Andreas.

Dado que los problemas de embalaje son típicamente NP-hard, este proyecto se centrará en los algoritmos de aproximación.

Por su parte Jérémy Barbay, investigador del Núcle Milenio ICR y académico del Departamento de Ciencias de la Computación de la Universidad de Chile liderará el proyecto de investigación titulado: ”Multivariate Analysis of Algorithms and Data Structures in Computational Geometry” que busca refinar técnicas de análisis “pesimistas” en versiones mas optimistas, especialmente en el tiempo de ejecución de algoritmos usados para almacenar los datos.

Más formalmente, se trata de refinar técnicas tradicionales, enfocadas sobre optimizar solamente el peor caso por un tamaño de entrada fijo, en técnicas dichas “finas”, que apuntan en obtener el mejor rendimiento (en tiempo o en espacio) por cada instancia (lo que en turno implica la optimalidad en el peor caso).

“Por ejemplo, en el peor caso se necesita del orden de $n\lg n$ operaciones para ordenar $n$ datos, uno necesita solamente $n-1$ comparaciones para verificar que un arreglo ya esta ordenado, o orden de $n$ operaciones para ordenar un arreglo que ya “casi” esta ordenado. Tal técnica de análisis ha dado buenos resultados sobre problemas clásicos de computación, y este proyecto apunta a generalizar la técnica a mucho mas problemas en Geometría Computacional, que muchas veces tienen aplicaciones en minería de datos (“Data Mining”)”, finaliza Barbay.

Información Periodística: Comunicaciones Ingeniería Industrial