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, el enfoque poliedral y la teoría de grafos han aportado en forma similar en la descripción estructural de los problemas y la resolución de conjeturas del área. En términos prácticos, estos estudios han contribuido al diseño y mejora de algoritmos específicos.
El desarrollo de este proyecto se enmarca en el estudio teórico estructural de diferentes problemas de Optimización Combinatoria y su aplicación al desarrollo de algoritmos para su resolución.
En particular, se abordarán los siguientes temas:
TEMA 1: Problemas de dominación en grafos.
1.1: Enfoque poliedral de problemas de dominación múltiple en grafos circulares.
1.2: Complejidad computacional de problemas de Secuencias Grundy de dominación.
TEMA 2: Problema de diseño de jornadas laborales en empresas de transporte.
2.1: Algoritmos de corte y ramificación para su modelo como problema de coloreo por lista en digrafos.
2.2: Algoritmos de generación de columnas para su modelo como problema de cubrimiento.
