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 Transformación Digital MiPyMEs 2025
31-03-2025 Gacetillas
Hasta el 18 de abril permanecerá abierta la convocatoria destinada a estudiantes de Ingeniería Industrial y la Tecnicatura Universitaria en Inteligencia Artificial que quieran participar de este programa que busca acompañar a las micro, pequeñas y medianas empresas de la...
Seguir LeyendoConcurso Nacional Mejor Tesis de Ingeniería de INVAP
25-03-2025 Gacetillas
Hasta el 31 de mayo permanecerá abierta la convocatoria a la tercera edición del Concurso Nacional a las Mejores Tesis de Ingeniería del país lanzado por INVAP.
Seguir LeyendoCurso FICA 2025. Francés para la Integración Cultural y Acad…
19-03-2025 Gacetillas
El Área de Relaciones Internacionales de la FCEIA brindará un curso de formación en francés como lengua extranjera dirigido a estudiantes de ingeniería que quieran realizar un intercambio en una universidad francesa.
Seguir LeyendoPrograma de Transformación Digital MiPyMEs 2025
Hasta el 18 de abril permanecerá abierta la convocatoria destinada a estudiantes de Ingeniería Industrial y la Tecnicatura Universitaria en Inteligencia Artificial que quieran participar de este programa que busca acompañar a las micro, pequeñas y medianas empresas de la ciudad en los nuevos desafíos que imponen los retos digitales.
Concurso Nacional Mejor Tesis de Ingeniería de INVAP
Hasta el 31 de mayo permanecerá abierta la convocatoria a la tercera edición del Concurso Nacional a las Mejores Tesis de Ingeniería del país lanzado por INVAP.
Curso FICA 2025. Francés para la Integración Cultural y Académica
El Área de Relaciones Internacionales de la FCEIA brindará un curso de formación en francés como lengua extranjera dirigido a estudiantes de ingeniería que quieran realizar un intercambio en una universidad francesa.