Estudio poliedral del problema de coloreo de máximo impacto
Continuamos en este trabajo el estudio de una formulación natural del problema de coloreo de máximo impacto por medio de programación lineal entera. Presentamos varias familias de desigualdades válidas, estudiamos bajo qué condiciones estas desigualdades definen facetas del poliedro asociado, y est...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Objeto de conferencia Resumen |
| Lenguaje: | Español |
| Publicado: |
2015
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/59241 http://44jaiio.sadio.org.ar/sites/default/files/sio9-9.pdf |
| Aporte de: |
| Sumario: | Continuamos en este trabajo el estudio de una formulación natural del problema de coloreo de máximo impacto por medio de programación lineal entera.
Presentamos varias familias de desigualdades válidas, estudiamos bajo qué condiciones estas desigualdades definen facetas del poliedro asociado, y estudiamos la complejidad computacional de los problemas de separación asociados. Presentamos además experimentos computacionales sobre instancias reales, que muestran que este enfoque puede ser útil en la práctica para resolver este problema. |
|---|