domingo, 26 de julio de 2015
Otras opciones con la técnica de ramificación y acotamiento (VII)
y realizar esta prueba después de la prueba 3 (para que una solución factible que se encuentra con Z > Z* se conserve como una nueva solución de apoyo). La razón para que esta prueba 1 más débil sea suficiente es que no importa qué tan cerca de la cota del subproblema se encuentre Z para la solución óptima (desconocida) del subproblema, la solución de apoyo todavía estará "bastante cerca" de esta solución (si se cumple la nueva desigualdad) como para que no sea necesario seguir analizando el subproblema. Cuando no hay subproblemas restantes, la solución de apoyo actual será la solución cercana a al óptima que se desea. Sin embargo, es mucho más sencillos sondear con esta nueva prueba (en cualquier forma), por lo que el algoritmo trabajará más rápido. Si se trata de problemas grandes, está aceleración puede significar la diferencia entre terminar con una solución que seguramente es cercana a la óptima y nunca
Suscribirse a:
Comentarios de la entrada (Atom)
No hay comentarios.:
Publicar un comentario