OPTIMIZACIÓN COMBINATORIA: TEORÍA, ALGORITMOS Y APLICACIONES

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.