Matemáticos de la Universidad de Sevilla estudian la resolución de los problemas más difíciles
La matemática combinatoria es uno de los campos de mayor impacto científico y social, dado que muchos problemas de los que se ocupa se encuentran entre los mayores desafíos de la matemática actual y tienen discreto, logística, complejidad, etc.
El proyecto se basa en el estudio de problemas combinatorios de gran dificultad, es decir, aquellos para los que no se conoce aún ningún algoritmo de resolución eficiente, haciendo especial énfasis en sus aspectos algorítmicos, geométricos y de aplicaciones.
El objetivo principal de este proyecto es reunir la experiencia en Investigación Operativa, Matemática Aplicada, Algebra Computacional y Computación de los distintos grupos involucrados para lograr nuevos resultados y aplicaciones novedosas de algunos problemas considerados claves para el avance de la optimización combinatoria.
Fases del estudio
El proyecto consta esencialmente de dos partes. La primera fase describe nuevos enfoques metodológicos de resolución de problemas combinatorios, mientras que la segunda está dedicada al estudio de algunos problemas específicos y sus aplicaciones.
Los problemas que considera el equipo de investigación, entre muchos otros, son los de tarificación en redes (Network pricing), localización, diseño y logística en redes (location, desing and logistics in networks), problema y compresión digital mediante transformadas wavelet discretas (Discrete Wavelet Transform).
Su estudio está motivado por las siguientes aplicaciones que serán el objetivo último del proyecto: neurociencia, agregación de preferencias, gestión de bases de datos, protección de datos estadísticos, minería de datos, compresión de datos e imágenes, diseño de redes óptimas de transporte, localización de servicios y planificación de producción.
En particular, el interés del proyecto se centra en desarrollar las herramientas geométricas fundamentales que pueden utilizarse para el análisis y resolución de los problemas de optimización combinatoria. En primer lugar, algunos de estos problemas son incluso sintácticamente problemas geométricos. En segundo lugar, en muchos casos, problemas concretos de los estudiados en optimización combinatoria se pueden obtener de configuraciones geométricas. Finalmente, los métodos utilizados para la resolución de los problemas se basan, frecuentemente, en la estructura geométrica de los mismos.
Enfoque multidisciplinar
De acuerdo con el trabajo seminal de Edmonds (1965), un algoritmo es eficiente si su tiempo de ejecución está acotado por un polinomio que es función de la longitud de los datos que describen el problema. La clase de todos estos algoritmos se denota por P.
A comienzos de los años 70 varios autores (Cook 1971 y Karp 1972) independientemente definen la clase NP de los problemas para los que una solución puede ser comprobada eficientemente y probaron la existencia de problemas en esta clase. Entre ellos se hallan muchos problemas combinatorios con una apariencia de lo más sencilla. Todavía hoy en día, la pregunta de si P coincide o no con NP es uno de los desafíos de la Matemática Contemporánea.
Su importancia radica en que si se encontrase un algoritmo eficiente para algún problema en NP, todos serían resolubles en tiempo polinomial y ambas clases (P y NP) serían coincidentes.
Un gran número de problemas que aparecen en aplicaciones prácticas son de los considerados difíciles. El equipo de investigación se propone analizar algunos de ellos poniendo especial énfasis en sus aplicaciones.
Este enfoque es multidisciplinar por definición, e involucra al menos las siguientes disciplinas: algorítmica (para desarrollar métodos que puedan ser programados en ordenadores y resolver automáticamente ciertos problemas), álgebra computacional y combinatoria (para analizar propiedades generales de estructuras algebraicas y combinatorias), geometría discreta y computacional (para desarrollar y analizar propiedades que resuelvan eficientemente problemas geométricos), optimización lineal entera (para optimización de funciones lineal en variables enteras), y análisis estocástico (para hacer uso de herramientas probabilísticas para el análisis de la incertidumbre).
Con este diseño los científicos pretenden aprovechar los conocimientos en las diferentes áreas de los miembros del equipo para ser aplicados en problemas diferentes. El proyecto no trata por tanto de realizar, simplemente, investigación básica en matemática discreta, si no que además, busca ayudar a la resolución de problemas decisivos en el mundo actual.
Telegram