Relajación de programación lineal
En matemáticas, la relajación de un programa lineal entero (mixto) es el problema que surge al eliminar la restricción de integralidad de cada variable.
La relajación resultante es un programa lineal , de ahí el nombre. Esta técnica de relajación transforma un problema de optimización NP-hard (programación entera) en un problema relacionado que se puede resolver en tiempo polinomial (programación lineal); la solución al programa lineal relajado se puede utilizar para obtener información sobre la solución al programa entero original.
Considérese el problema de cobertura de conjuntos , cuya relajación de programación lineal fue considerada por primera vez por Lovász (1975) . En este problema, se da como entrada una familia de conjuntos F = { S 0 , S 1 , ...}; la tarea es encontrar una subfamilia, con el menor número posible de conjuntos, que tienen la misma unión como F .
Para formular esto como un programa entero 0-1, forme una variable indicadora x i para cada conjunto S i , que toma el valor 1 cuando S i pertenece a la subfamilia elegida y 0 cuando no lo hace. Entonces, una cobertura válida puede describirse mediante la asignación de valores a las variables indicadoras que satisfacen las restricciones.
(es decir, solo se permiten los valores de la variable indicadora especificada) y, para cada elemento e j de la unión de F ,
(es decir, se cubre cada elemento). La cobertura mínima establecida corresponde a la asignación de variables indicadoras que satisfacen estas restricciones y minimizan la función objetivo lineal.
