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 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.
Considere 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 el menor número posible de conjuntos, que tenga la misma unión que F.
Para formular esto como un programa entero 0-1, forme una variable indicadora x i para cada conjunto Si , que tome el valor 1 cuando Si pertenece a la subfamilia elegida y 0 cuando no. Entonces una cobertura válida puede describirse mediante una 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, 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 de modo que el peso total de los conjuntos que contienen cada elemento sea al menos uno y el peso total de todos los conjuntos se minimice.
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 óptimos, cada una de las cuales incluye dos de los tres conjuntos dados. Por tanto, el valor óptimo de la función objetivo del correspondiente programa entero 0-1 es 2, el número de conjuntos en las coberturas óptimas. Sin embargo, existe 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 la programación lineal tiene un valor diferente al del programa entero 0-1 no relajado.
La relajación de la programación lineal de un programa entero se puede resolver 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 ).
Sin embargo, en todos los casos, 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 de cobertura de conjuntos el programa relajado tiene un valor menor o igual al del programa original. Por tanto, la relajación proporciona una cota optimista en 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 igual de grande. Dado que el problema de cobertura de conjuntos tiene valores de solución que son números enteros (el número de conjuntos elegidos en la subfamilia), la calidad óptima de la solución debe ser al menos tan grande como el siguiente entero mayor, 2. Por lo tanto, en este caso, a pesar de tener una solución diferente valor del problema no relajado, la relajación de la programación lineal nos da un límite inferior estricto en la calidad de la solución del problema original.
La relajación de la 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 su relajación. En un caso de un problema de minimización, si el mínimo real (el mínimo del problema de números enteros) es y el mínimo relajado (el mínimo de la relajación de la programación lineal) es , entonces la brecha de integralidad de ese caso 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.
Normalmente, la brecha de integralidad se traduce en el índice 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 relación de redondeo). Si hay una instancia con brecha de integralidad IG , entonces cada estrategia de redondeo devolverá, en esa instancia, una solución redondeada de tamaño al menos . Por lo tanto necesariamente . El índice de redondeo RR es solo un límite superior del índice de aproximación, por lo que en teoría el índice 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 relación de aproximación en la relajación de la programación lineal podría 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 enésimo número armónico . Se puede convertir la relajación de la programación lineal para este problema en una solución aproximada de la instancia de cobertura del conjunto original no relajado mediante la técnica de redondeo aleatorio . [2] Dada una cobertura fraccionaria, en la que cada conjunto Si tiene peso wi , 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 fraccionada. Por lo tanto, esta técnica conduce a un algoritmo de aproximación aleatoria que encuentra una cobertura de conjunto dentro de un factor logarítmico del óptimo. Como demostró Young 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 la programación lineal pueden eliminarse utilizando el método de probabilidades condicionales , lo que lleva a un algoritmo determinista codicioso para la cobertura de conjuntos, ya conocido. para Lovász, que selecciona repetidamente el conjunto que cubre el mayor número posible de elementos restantes descubiertos. Este codicioso algoritmo aproxima la cobertura del conjunto dentro del mismo factor H n que Lovász demostró como la brecha de integralidad para la cobertura del conjunto. Existen fuertes razones teóricas 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 la programación lineal para desarrollar algoritmos de aproximación para muchos otros problemas, como lo describen Raghavan, Tompson y Young.
Además de sus usos en aproximación, la programación lineal juega un papel importante en algoritmos de ramificación y ligada 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 rama y enlace , en el que resolvemos recursivamente subproblemas en los que algunas de las variables fraccionarias tienen sus valores fijos en cero o 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 asumir cualquiera de los dos. valor. En el subproblema i , sea Vi 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 resultar muy eficaces 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 todos soluciones factibles y excluye todos los demás vectores 0–1, y una infinidad de politopos diferentes tienen esta propiedad. Idealmente, a uno le gustaría utilizar como relajación el casco convexo de las soluciones factibles; La programación lineal en este politopo produciría automáticamente la solución correcta al 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 discutido anteriormente, forman un politopo que contiene estrictamente el casco convexo 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 por Dantzig, Fulkerson y Johnson en 1954 [5] y generalizado a otros programas enteros por Gomory en 1958, [6] aprovecha esta ventaja. multiplicidad de posibles relajaciones al encontrar una secuencia de relajaciones que restrinjan más estrechamente el espacio de soluciones hasta que finalmente se obtenga una solución entera. Este método parte 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 al 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 del casco convexo de las soluciones enteras, y el método se repite en este nuevo problema más restringido.
Se necesitan métodos específicos del problema para encontrar los cortes utilizados por este método. Es especialmente deseable encontrar planos de corte que formen facetas del casco convexo de las soluciones enteras, ya que estos planos son los que limitan más estrechamente el espacio de la solución; 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, bajo el marco de la combinatoria poliédrica . [7]
El método de rama y corte relacionado combina el plano de corte y los métodos de rama y encuadernado. En cualquier subproblema, ejecuta el método del plano de corte hasta que no se pueden encontrar más planos de corte y luego se bifurca en una de las variables fraccionarias restantes.
