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.

Los aspectos algorítmicos aparecen en la búsqueda de soluciones, exactas o aproximadas, en cualquier circunstancia de tamaño o incertidumbre en los datos. Los aspectos geométricos se centran en la descripción poliédrica de aquellos problemas que se puedan formular como programas enteros o enteros mixtos, así como en el conocimiento de desigualdades entre invariantes de los grafos asociados. Las mejores desigualdades corresponden, en el espacio de invariantes, con facetas de la descripción poliédrica.

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 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.

Así mismo, el equipo científico considera problemas complejos de decisión que involucran a diferentes objetivos y agentes, para los que la teoría de juegos, la optimización multiobjetivo y la decisión multicriterio son herramientas fundamentales, y cuyas aplicaciones cubren entre otros el estudio de los equilibrios en economía, de la competencia y cooperación en el contexto de problemas relacionados con la gestión de inventarios, las redes de flujo y la planificación de proyectos competitivos, el diseño y análisis de estructuras de votación, la conciliación en problemas de bancarrota, y el estudio de redes sociales, etc.

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.

Los problemas denominados "difíciles" son aquellos para los que no se conocen algoritmos eficientes. 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.

Más información:

Justo Puerto Albandoz
Dpto. de Estadística e Investigación
Facultad de Matemáticas
Universidad de Sevilla

Email: puerto@us.es