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.
Por ejemplo, en un programa de números enteros 0-1 , todas las restricciones tienen la forma
La relajación del programa entero original utiliza en cambio una colección de restricciones lineales.
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 del programa lineal relajado se puede utilizar para obtener información sobre la solución del 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 en 1975. [1] En este problema, se da como entrada una familia de conjuntos F = { S 0 , S 1 , ...}; la tarea es encontrar una subfamilia, con la menor cantidad de conjuntos posible, que tenga la misma unión que F .
Para formular esto como un programa entero 0–1, se forma 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. Luego, se puede describir una cobertura válida mediante una asignación de valores a las variables indicadoras que satisfacen las restricciones
(es decir, sólo se permiten los valores de la variable indicadora especificada) y, para cada elemento e j de la unión de F ,
(es decir, cada elemento está cubierto). La cobertura mínima del conjunto corresponde a la asignación de variables indicadoras que satisfacen estas restricciones y minimizan la función objetivo lineal.
La relajación de programación lineal del problema de cobertura de conjuntos describe una cobertura fraccionaria en la que a los conjuntos de entrada se les asignan pesos tales que el peso total de los conjuntos que contienen cada elemento es al menos uno y se minimiza el peso total de todos los conjuntos.
Como ejemplo específico del problema de cobertura de conjuntos, considere la instancia F = {{ a , b }, { b , c }, { a , c }}. Hay tres coberturas de conjuntos óptimas, cada una de las cuales incluye dos de los tres conjuntos dados. Por lo tanto, el valor óptimo de la función objetivo del programa entero 0–1 correspondiente es 2, el número de conjuntos en las coberturas óptimas. Sin embargo, hay una solución fraccionaria en la que a cada conjunto se le asigna el peso 1/2, y para la cual el valor total de la función objetivo es 3/2. Por lo tanto, en este ejemplo, la relajación de programación lineal tiene un valor diferente al del programa entero 0–1 no relajado.
La relajación de programación lineal de un programa entero puede resolverse utilizando cualquier técnica de programación lineal estándar. Si sucede que, en la solución óptima, todas las variables tienen valores enteros, entonces también será una solución óptima para el programa entero original. Sin embargo, esto generalmente no es cierto, excepto en algunos casos especiales (por ejemplo, problemas con especificaciones de matrices totalmente unimodulares ).
En todos los casos, sin embargo, la calidad de la solución del programa lineal es al menos tan buena como la del programa entero, porque cualquier solución de programa entero también sería una solución de programa lineal válida. Es decir, en un problema de maximización, el programa relajado tiene un valor mayor o igual al del programa original, mientras que en un problema de minimización como el problema de cobertura de conjuntos, el programa relajado tiene un valor menor o igual al del programa original. Por lo tanto, la relajación proporciona un límite optimista para la solución del programa entero.
En el ejemplo del problema de cobertura de conjuntos descrito anteriormente, en el que la relajación tiene un valor de solución óptima de 3/2, podemos deducir que el valor de solución óptima del programa entero no relajado es al menos tan grande. Dado que el problema de cobertura de conjuntos tiene valores de solución que son enteros (la cantidad de conjuntos elegidos en la subfamilia), la calidad de solución óptima debe ser al menos tan grande como el siguiente entero más grande, 2. Por lo tanto, en este caso, a pesar de tener un valor diferente del problema no relajado, la relajación de programación lineal nos da un límite inferior estricto para la calidad de solución del problema original.
La relajación de programación lineal es una técnica estándar para diseñar algoritmos de aproximación para problemas de optimización difíciles. En esta aplicación, un concepto importante es la brecha de integralidad , la relación máxima entre la calidad de la solución del programa entero y de su relajación. En una instancia de un problema de minimización, si el mínimo real (el mínimo del problema entero) es , y el mínimo relajado (el mínimo de la relajación de programación lineal) es , entonces la brecha de integralidad de esa instancia es . En un problema de maximización la fracción se invierte. La brecha de integralidad es siempre al menos 1. En el ejemplo anterior, la instancia F = {{ a , b }, { b , c }, { a , c }} muestra una brecha de integralidad de 4/3.
Por lo general, la brecha de integridad se traduce en la razón de aproximación de un algoritmo de aproximación. Esto se debe a que un algoritmo de aproximación se basa en alguna estrategia de redondeo que encuentra, para cada solución relajada de tamaño , una solución entera de tamaño como máximo (donde RR es la razón de redondeo). Si hay una instancia con brecha de integridad IG , entonces cada estrategia de redondeo devolverá, en esa instancia, una solución redondeada de tamaño al menos . Por lo tanto, necesariamente . La razón de redondeo RR es solo un límite superior en la razón de aproximación, por lo que en teoría la razón de aproximación real puede ser menor que IG , pero esto puede ser difícil de probar. En la práctica, un IG grande generalmente implica que la razón de aproximación en la relajación de programación lineal puede ser mala, y puede ser mejor buscar otros esquemas de aproximación para ese problema.
Para el problema de cobertura de conjuntos, Lovász demostró que la brecha de integralidad para una instancia con n elementos es H n , el n º número armónico . Se puede convertir la relajación de programación lineal para este problema en una solución aproximada de la instancia de cobertura de conjuntos no relajada original mediante la técnica de redondeo aleatorio . [2] Dada una cobertura fraccionaria, en la que cada conjunto S i tiene peso w i , elija aleatoriamente el valor de cada variable indicadora 0-1 x i para que sea 1 con probabilidad w i × (ln n +1), y 0 en caso contrario. Entonces, cualquier elemento e j tiene una probabilidad menor que 1/( e × n ) de permanecer descubierto, por lo que con probabilidad constante todos los elementos están cubiertos. La cobertura generada por esta técnica tiene un tamaño total, con alta probabilidad, (1+o(1))(ln n ) W , donde W es el peso total de la solución fraccionaria. Por lo tanto, esta técnica conduce a un algoritmo de aproximación aleatorio que encuentra una cobertura de conjuntos dentro de un factor logarítmico del óptimo. Como Young demostró en 1995 [3], tanto la parte aleatoria de este algoritmo como la necesidad de construir una solución explícita a la relajación de programación lineal pueden eliminarse utilizando el método de probabilidades condicionales , lo que conduce a un algoritmo voraz determinista para la cobertura de conjuntos, ya conocido por Lovász, que selecciona repetidamente el conjunto que cubre el mayor número posible de elementos restantes descubiertos. Este algoritmo voraz aproxima la cobertura de conjuntos dentro del mismo factor H n que Lovász demostró como la brecha de integralidad para la cobertura de conjuntos. Hay fuertes razones de teoría de la complejidad para creer que ningún algoritmo de aproximación de tiempo polinomial puede lograr una relación de aproximación significativamente mejor. [4]
Se pueden utilizar técnicas de redondeo aleatorio similares y algoritmos de aproximación desaleatorizados junto con la relajación de programación lineal para desarrollar algoritmos de aproximación para muchos otros problemas, como describen Raghavan, Tompson y Young.
Además de sus usos en aproximación, la programación lineal juega un papel importante en los algoritmos de ramificación y acotación para calcular la verdadera solución óptima a problemas de optimización difíciles.
Si algunas variables en la solución óptima tienen valores fraccionarios, podemos iniciar un proceso de tipo ramificación y acotación , en el que resolvemos recursivamente subproblemas en los que algunas de las variables fraccionarias tienen sus valores fijos en cero o en uno. En cada paso de un algoritmo de este tipo, consideramos un subproblema del programa entero 0–1 original en el que algunas de las variables tienen valores asignados, ya sea 0 o 1, y las variables restantes aún son libres de tomar cualquiera de los valores. En el subproblema i , sea V i el conjunto de variables restantes. El proceso comienza considerando un subproblema en el que no se han asignado valores a las variables, y en el que V 0 es el conjunto completo de variables del problema original. Luego, para cada subproblema i , realiza los siguientes pasos.
Aunque es difícil demostrar límites teóricos sobre el rendimiento de algoritmos de este tipo, pueden ser muy efectivos en la práctica.
Dos programas enteros 0–1 que son equivalentes, en el sentido de que tienen la misma función objetivo y el mismo conjunto de soluciones factibles, pueden tener relajaciones de programación lineal bastante diferentes: una relajación de programación lineal puede verse geométricamente como un politopo convexo que incluye todas las soluciones factibles y excluye todos los demás vectores 0–1, y una cantidad infinita de politopos diferentes tienen esta propiedad. Idealmente, sería bueno utilizar como relajación la envoltura convexa de las soluciones factibles; la programación lineal sobre este politopo produciría automáticamente la solución correcta para el programa entero original. Sin embargo, en general, este politopo tendrá exponencialmente muchas facetas y será difícil de construir. Las relajaciones típicas, como la relajación del problema de cobertura de conjuntos discutida anteriormente, forman un politopo que contiene estrictamente la envoltura convexa y tiene vértices distintos de los vectores 0–1 que resuelven el problema no relajado.
El método del plano de corte para resolver programas enteros 0-1, introducido por primera vez para el problema del viajante de comercio por Dantzig, Fulkerson y Johnson en 1954 [5] y generalizado a otros programas enteros por Gomory en 1958, [6] aprovecha esta multiplicidad de posibles relajaciones al encontrar una secuencia de relajaciones que restringen más estrictamente el espacio de soluciones hasta que finalmente se obtiene una solución entera. Este método comienza a partir de cualquier relajación del programa dado y encuentra una solución óptima utilizando un solucionador de programación lineal. Si la solución asigna valores enteros a todas las variables, también es la solución óptima para el problema no relajado. De lo contrario, se encuentra una restricción lineal adicional (un plano de corte o corte ) que separa la solución fraccionaria resultante de la envoltura convexa de las soluciones enteras, y el método se repite en este nuevo problema con restricciones más estrictas.
Se necesitan métodos específicos para cada problema para encontrar los cortes utilizados por este método. Es especialmente deseable encontrar planos de corte que formen facetas de la envoltura convexa de las soluciones enteras, ya que estos planos son los que restringen más estrechamente el espacio de soluciones; siempre existe un plano de corte de este tipo que separa cualquier solución fraccionaria de las soluciones enteras. Se han realizado muchas investigaciones sobre métodos para encontrar estas facetas para diferentes tipos de problemas de optimización combinatoria, en el marco de la combinatoria poliédrica . [7]
El método de ramificación y corte relacionado combina los métodos de plano de corte y de ramificación y límite. En cualquier subproblema, ejecuta el método de plano de corte hasta que no se puedan encontrar más planos de corte y luego se ramifica en una de las variables fraccionarias restantes.
