Los problemas de empaquetamiento y el cubrimiento de conjuntos son dos conceptos duales fundamentales en optimización combinatoria, los cuales son equivalentes a través de transformaciones apropiadas. Estos problemas son relevantes en la práctica, pero difíciles de resolver en general. Una manera a menudo exitosa de resolver esta clase de problemas es el enfoque poliedral relativo al espacio de soluciones del problema. En este proyecto en particular, abordamos aplicaciones del problema de cubrimiento de conjuntos que provienen del problema de dominación en grafos y sus variantes. En particular se estudiarán los siguientes temas: TEMA 1: Problema de dominación en grafos redes. Numerosas aplicaciones pueden ser modeladas como problemas de dominación en grafos (ver Henning (1997)). El problema de dominación clásico en un grafo es el problema de hallar un conjunto dominante de cardinal mínimo, es decir, un subconjunto de vértices de cardinal mínimo que tenga intersección no vacía con las vecindades cerradas del grafo. Este problema admite una formulación en términos del problema de cubrimiento de conjuntos. El enfoque poliedral ha sido de gran importancia para la resolución del problema y ha contribuido a la construcción y mejora de algoritmos específicos de resolución de algunas instancias. En particular, el problema de dominación en grafos redes se traduce en el problema de cubrimiento sobre matrices circulantes. TEMA 2: Problema de códigos de identificación en grafos. Habitualmente, las distintas aplicaciones que se modelan como problemas de dominación en grafos, imponen restricciones adicionales a los conjuntos dominantes, surgiendo de esta manera variaciones del problema (ver Henning (1997)). En efecto, a partir del concepto de dominación en grafos se modelan entre otros, problemas de locación de servicios (contenedores de residuos domiciliarios, hospitales, estaciones de bomberos, cajeros automáticos, etc.). Ejemplos clásicos son la detección de incendios en edificios y la detección de fallas en redes de procesadores. En estos casos se necesita instalar detectores de incendio o de fallas en ciertos lugares. Los detectores son suficientemente potentes como para detectar el problema incluso en los sitios contiguos a los lugares en donde se encuentran, por lo tanto se pretende instalar la menor cantidad de detectores posibles de manera que a partir del conjunto de detectores que dieron la alarma, se pueda identificar el sitio exacto en donde se ha producido la amenaza. Este conjunto de detectores es lo que se conoce como un código de identificación y el problema de cubrimiento de conjuntos también permite la formulación del problema de mínimo código de identificación como un programa entero.
Novedades
Programa de Becas Roberto Rocca 2024
17-06-2024 Gacetillas
Hasta el 28 de junio permanecerá abierta la inscripción al Programa de Becas Roberto Rocca destinado a estudiantes de 1° y 2° año de las carreras de Ingeniería Electrónica, Eléctrica y Mecánica.
Seguir LeyendoApertura convocatoria a las 31º Jornadas de Jóvenes Investi…
08-08-2024 Gacetillas
La Asociación de Universidades Grupo Montevideo informa que se encuentra abierta la convocatoria para presentar trabajos de investigación en el marco de las 31º JORNADAS DE JÓVENES INVESTIGADORES de la Asociación de Universidades Grupo Montevideo (AUGM), a realizarse en la...
Seguir LeyendoEncuentro: ¿Qué vemos a través de los procesos de evaluación…
15-04-2024 Gacetillas
Este espacio que se desarrollará en dos encuentros los días 25/6 y 2/7 de 14 a 16 horas en la sede Pellegrini 250 de la FCEIA, busca identificar las principales dificultades y obstáculos que se presentan en los aprendizajes y...
Seguir LeyendoEventos de Extensión 2024
19-03-2024 Gacetillas
Compartimos información sobre dos eventos de extensión que se desarrollarán durante 2024.
Seguir LeyendoPrograma de Becas Roberto Rocca 2024
Hasta el 28 de junio permanecerá abierta la inscripción al Programa de Becas Roberto Rocca destinado a estudiantes de 1° y 2° año de las carreras de Ingeniería Electrónica, Eléctrica y Mecánica.
Apertura convocatoria a las 31º Jornadas de Jóvenes Investigadores de AUGM
La Asociación de Universidades Grupo Montevideo informa que se encuentra abierta la convocatoria para presentar trabajos de investigación en el marco de las 31º JORNADAS DE JÓVENES INVESTIGADORES de la Asociación de Universidades Grupo Montevideo (AUGM), a realizarse en la Universidad de la República – UdelaR, Montevideo, Uruguay.
Encuentro: ¿Qué vemos a través de los procesos de evaluación?
Este espacio que se desarrollará en dos encuentros los días 25/6 y 2/7 de 14 a 16 horas en la sede Pellegrini 250 de la FCEIA, busca identificar las principales dificultades y obstáculos que se presentan en los aprendizajes y en la enseñanza en los primeros años, tomando como referencia de abordaje las instancias de evaluación.