29
Vie, Mar

Dra. Graciela Nasini
nasini@fceia.unr.edu.ar 

Numerosos y diversos problemas de optimización de recursos, ligados a situaciones reales, pueden ser formulados como problemas de Optimización Combinatoria. La mayoría de ellos son problemas muy complejos de resolver, pertenecientes a la clase de problemas NP-difíciles. Sin embargo, la necesidad práctica de su resolución, en forma exacta o aproximada, ha dado un gran impulso al estudio estructural de los mismos.
En este sentido, desde el punto de vista teórico, tanto el enfoque poliedral como el enfoque en términos de grafos han sido de gran importancia para la resolución de numerosas conjeturas del área. En términos prácticos, estos estudios han contribuido al diseño y mejora de algoritmos específicos.
La tarea de desarrollo de este proyecto se enmarcará en el estudio de diferentes problemas de Optimización Combinatoria desde el enfoque poliedral y el desarrollo de algoritmos para su resolución.
En particular, nuestro trabajo se orientará en el estudio de los siguientes temas:

TEMA 1: Poliedro de cubrimiento de matrices circulantes.
1.1: Desigualdades de menores generalizadas.
1.2: Descripción del poliedro de cubrimiento en familias de matrices circulantes.

TEMA 2: Algoritmos para Problemas NP-difíciles.
2.1: Problema de Coloreo de empaquetamiento.
2.2: Problema de Asignación de viajes a conductores.