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

La ramificación casi siempre se hace resolviendo una soltura. Sin embargo, existen muchas formas de solturas. Por ejemplo, considérese la soltura de Lagrange, en donde se elimina el conjunto completo de restricciones funcionales (en forma matricial), Ax ≤ b (excepto quizá algunas restricciones "convenientes"), y después la función objetivo,

Maximizar Z = cx,

se reemplaza por

Maximizar ZR = cx - λ(Ax - b)

en donde el vector fijo λ ≤ 0. Si x* es una solución óptima para el problema original, su Z ≤ ZR, por o que al obtener un valor óptimo de ZR con la soltura de Lagrange se llega a una cota válida. Si λ se elige bien, esta cota tiende a ser razonablemente cerrada (al menos comparable a la cota de la soltura de PL). Sin restricciones funcionales, esta soltura se puede obtener muy rápido. Las desventajas son que las pruebas de sondeo 2 y 3 (cambiadas) no son tan poderosas como las de la soltura de PL. No obstante, en ocasiones se usan las dos solturas juntas con bastantes ventajas.