Relajación (aproximación)
En optimización matemática y campos relacionados, la relajación es una estrategia de modelado . Una relajación es una aproximación de un problema difícil por un problema cercano que es más fácil de resolver. Una solución del problema relajado proporciona información sobre el problema original.
Por ejemplo, una relajación de programación lineal de un problema de programación de enteros elimina la restricción de integralidad y, por lo tanto, permite soluciones racionales no enteras. Una relajación lagrangiana de un problema complicado en la optimización combinatoria penaliza las violaciones de algunas restricciones, lo que permite resolver un problema relajado más fácil. Las técnicas de relajación complementan los algoritmos de ramificación y límite de optimización combinatoria; La programación lineal y las relajaciones lagrangianas se utilizan para obtener límites en algoritmos de ramificación y límite para la programación de enteros. [1]
La estrategia de modelado de relajación no debe confundirse con métodos iterativos de relajación , como la sobre-relajación sucesiva (SOR); Los métodos iterativos de relajación se utilizan para resolver problemas de ecuaciones diferenciales , mínimos cuadrados lineales y programación lineal . [2] [3] [4] Sin embargo, se han utilizado métodos iterativos de relajación para resolver las relajaciones lagrangianas. [a]
La primera propiedad establece que el dominio factible del problema original es un subconjunto del dominio factible del problema relajado. La segunda propiedad establece que la función objetivo del problema original es mayor o igual que la función objetivo del problema relajado. [1]
Si es una solución óptima del problema original, entonces y . Por lo tanto, proporciona un límite superior en .
Si además de los supuestos anteriores, , , se cumple lo siguiente: Si una solución óptima para el problema relajado es factible para el problema original, entonces es óptima para el problema original. [1]
