Problema del agente de comercio k-coloreado

Yasmín A. Ríos Solís
(Instituto Tecnológico de Monterrey) 

En esta charla hablaré de un famoso problema del Viajero de Comercio (el más famoso de los NP-difíciles) en donde una persona tiene que visitar todas las ciudades solo una vez y se busca el camino más corto pero con la particularidad de que puede escoger diferentes tipos de vehículos (colores). Mostraré los diferentes modelos matemáticos de optimización discreta que habían fracasado para luego introducir la simetría que nos permitió resolver el problema para instancias grandes.