Ramificación y Acotación

Ramificación y acotación (branch and bound, B&B) es el método exacto estándar para programación entera mixta (MIP) y muchos problemas de optimización discreta. Lo introdujeron Land y Doig (1960) para MIP, Little et al. (1963) lo aplicaron al TSP y Dakin (1965) clarificó la regla de ramificación para restricciones enteras. El algoritmo particiona la región factible recursivamente en subregiones (ramificación — p. ej. para variable entera x con x* fraccional, dos hijos x ≤ ⌊x*⌋ y x ≥ ⌈x*⌉), resuelve una **relajación LP** en cada nodo para obtener una cota inferior (en minimización), mantiene una cota superior con la mejor solución entera factible encontrada (incumbente), **poda por cota** los nodos cuya cota LP no es mejor que el incumbente, **poda por integralidad** cuando la solución LP es ya entera y descarta nodos infactibles. Cuando el árbol se agota, el incumbente es el óptimo global. Branch-and-cut (Padberg y Rinaldi 1991) acopla B&B con planos de corte y es la columna vertebral de los solvers MIP modernos. Branch-and-price (Barnhart et al. 1998) lo acopla con generación de columnas y resuelve formulaciones enormes. La estrategia de ramificación (most-fractional, strong branching, pseudocost branching), la selección de nodos (best-first, depth-first, best-estimate) y el presolving afectan drásticamente el rendimiento. Wolsey (1998) *Integer Programming* y Nemhauser y Wolsey (1988) son referencias estándar. Los solvers MIP modernos manejan problemas de 100M variables combinando B&B + cortes + heurísticas.