Algunas perspectivas sobre la solución de problemas de programación entera (II)

La segunda falacia es que al eliminar algunas soluciones factibles (las o enteras) de un problema de programación lineal, será más fácil de resolverlo. Todo lo contrario: sólo cuando todas estas soluciones factibles están ahí, se puede garantizar (véase la sección 5.1) que existe una solución factible en el vértice (solución básica factible) que es óptima para el problema completo. Esta garantía es la clave de la extraordinaria eficiencia del método símplex. Como resultado, en general es mucho más sencillo resolver los problemas de programación líneal que los de programación entera.

ES lógico, entonces, que la mayor parte de los buenos algoritmos de programación entera incorporen el método simplex (o el método símplex dual) lo más que puedan, y relacionen partes del problema de PE bajo consideración con el problema correspondiente de programación líneal  (es decir, el mismo problema con la restricción de valores enteros eliminada). Para cualquier problema dado de programacion entera, el problema correspondiente de programación líneal se conoce como su soltura de PL. El algortimo que se presenta en las dos secciones siguientes ilustra cómo se puede usar una sucesión de solturas de PL para porciones de un problema de programación entera, con objeto de resolver de manera eficiente un problema completo de PE.