Brecha de Optimalidad

La brecha de optimalidad cuantifica la distancia entre el valor de la mejor solución factible hallada (cota superior UB en minimización) y la mejor cota dual obtenida hasta el momento (cota inferior LB); existen dos definiciones estándar. Brecha absoluta = |UB - LB|. Brecha relativa (la variante canónica en MILP) = |UB - LB| / max(ε, |UB|), o en algunos solucionadores |UB - LB| / max(ε, |LB|) — la elección del denominador varía según el proveedor, con ε para evitar la división por cero. Una brecha igual a cero certifica el incumbent como óptimo y termina el algoritmo; en la práctica los solucionadores se detienen con bandera 'casi óptimo' al caer la brecha por debajo de una tolerancia del usuario (típicamente 0,01-1%). El fundamento lógico es la dualidad: en LP la dualidad débil ofrece UB ≥ LB para todo par primal-dual factible, y la dualidad fuerte la convierte en igualdad. En MILP la relajación LP produce la LB, el branch-and-bound la actualiza nodo a nodo, y las heurísticas primales más la exploración por ramificación actualizan la UB. Interpretación: una brecha del 5% significa 'el valor de la solución es a lo sumo un 5% peor que el óptimo' — no existe mejora matemática por debajo de la LB conocida. Usos prácticos: comunicación del riesgo a la dirección (peor caso), decisiones de terminación temprana (compromiso tiempo-calidad en branch-and-cut largos) y benchmarking de heurísticas. La brecha de dualidad de Lagrange en programación convexa no lineal y la brecha de relajación en no convexa son conceptos análogos. Referencias canónicas: Nemhauser y Wolsey (1988) y Wolsey (1998).