1. Ramificación: entre los subproblemas restantes (no sondeados), se selecciona el de más reciente creación. (Los empates se rompen con la cota más grande). Entre las variables restringidas a enteros, que tienen valores no enteros en la solución óptima de la soltura de PL del subproblema, se elige la primera en el orden natural, como la variable de ramificación. Sea xj esta variable y x*j su valor en esta solución. Se ramifica desde el nodo del subproblema para crear dos nuevos subproblemas agregando las restricciones respectivas xj ≤ [x*j] y xj ≥ [x*j] +1.
No hay comentarios.:
Publicar un comentario