Otras opciones con la técnica de ramificación y acotamiento (I)

Esta sección ha ilustrado la técnica de ramificación y acontamiento con la descripción de un algoritmo básico para resolver problemas  de programación entera binaria. Sin embargo, el marco general de trabajo de la técnica de ramificación y acotamiento proporciona una gran flexibilidad en cuanto al diseño de un algoritmo específico para cualquier tipo de problema dado. Se dispone de muchas opciones y la construcción de un algoritmo eficiente requiere adaptar el diseño específico para que se ajuste a la estructura particular del tipo de problema.

Cada algoritmo de ramificación y acotamiento contiene los mismos pasos básicos de ramificación, acotamiento y sondeo. La flexibilidad consiste en cómo se realizan estos pasos.

La ramificación siempre implica seleccionar un subproblema restante y dividirlo en subproblemas  más pequeños. En este caso, la flexibilidad se encuentra en las en las reglas para seleccionar y dividir. El algoritmo que se presentó elige el subproblema de creación más reciente, porque esto es muy eficiente para reoptimizar cada soltura de PL a partir  de la anterior. Elegir el subproblema con la mejor cota es la otra regla popular, ya que tiende a llegar más rápido  a mejores soluciones de apoyo y más sondeos. También se puede usar una combinación de estas dos reglas. La división casi siempre (pero no siempre) se hace seleccionando una variable de ramificación y asignándole, ya sea valores individuales (como el algoritmo), o intervalos de valores (como en el algoritmo de la siguiente sección). Algoritmos más elaborados por lo general  utilizan una regla para elegir estratégicamente una variable de ramificación que tienda a sondeos rápidos.