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
- .
En cambio, la relajación del programa entero original utiliza 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 de enteros) 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.
Ejemplo
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. 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 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 la 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 manera que el peso total de los conjuntos que contienen cada elemento es al menos uno y el peso total de todos los conjuntos se minimiza.
Como ejemplo específico del problema de cobertura de conjuntos, considere la instancia F = {{ a , b }, { b , c }, { a , c }}. Hay tres cubiertas de juegos óptimas, cada una de las cuales incluye dos de los tres juegos 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, 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 tanto, en este ejemplo, la relajación de la programación lineal tiene un valor que difiere del del programa entero 0-1 no relajado.
Calidad de la solución de programas relajados y originales
La relajación de la programación lineal de un programa entero puede resolverse utilizando cualquier técnica de programación lineal estándar. Si la solución óptima del programa lineal tiene todas las variables 0 o 1, 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 matriz 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 que el 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 que el del programa. programa original. Por tanto, la relajación proporciona un límite optimista en la solución del programa entero.
En la instancia de ejemplo del problema de cobertura de conjuntos descrito anteriormente, en el que la relajación tiene un valor de solución óptimo de 3/2, podemos deducir que el valor de solución óptimo 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 enteros (el número 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 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.
Brecha de aproximación e integralidad
La relajación de programación lineal es una técnica estándar para diseñar algoritmos de aproximación para problemas difíciles de optimización. 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 una instancia 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 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.
Normalmente, la brecha de integralidad se traduce en la relació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 una 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. 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 relación de aproximación en la relajación de la 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- é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 original de cobertura del conjunto no relajado mediante la técnica de redondeo aleatorio ( Raghavan y Tompson 1987 ). . 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 una 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 aleatorio que encuentra una cobertura de conjunto dentro de un factor logarítmico del óptimo. Como mostró Young (1995) , 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 codicioso 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 descubiertos restantes. Este algoritmo codicioso 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 razón de aproximación significativamente mejor ( Feige 1998 ).
Se pueden utilizar técnicas similares de redondeo aleatorio 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 lo describen Raghavan, Tompson y Young.
Bifurca y enlaza para soluciones exactas
Además de sus usos en la aproximación, la programación lineal juega un papel importante en los algoritmos de bifurcación y enlace para calcular la verdadera solución óptima a los problemas difíciles de optimización.
Si algunas variables en la solución óptima tienen valores fraccionarios, podemos iniciar un proceso de tipo bifurcado y ligado , en el que resolvemos de forma recursiva 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 de enteros 0-1 original en el que algunas de las variables tienen valores asignados, ya sea 0 o 1, y las variables restantes aún pueden asumir valor. 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 de variable y en el que V 0 es el conjunto completo de variables del problema original. Luego, para cada subproblema i , realiza los siguientes pasos.
- Calcule la solución óptima para la relajación de programación lineal del subproblema actual. Es decir, para cada variable x j en V i , reemplazamos la restricción de que x j sea 0 o 1 por la restricción relajada de que esté en el intervalo [0,1]; sin embargo, las variables a las que ya se les han asignado valores no se relajan.
- Si la solución relajada del subproblema actual es peor que la mejor solución entera encontrada hasta ahora, retroceda desde esta rama de la búsqueda recursiva.
- Si la solución relajada tiene todas las variables establecidas en 0 o 1, pruébela con la mejor solución entera encontrada hasta ahora y conserve la mejor de las dos soluciones.
- De lo contrario, sea x j cualquier variable que se establezca en un valor fraccionario en la solución relajada. Forme dos subproblemas, uno en el que x j se establece en 0 y el otro en el que x j se establece en 1; en ambos subproblemas, las asignaciones de valores existentes a algunas de las variables todavía se utilizan, por lo que el conjunto de variables restantes se convierte en V i \ { x j }. Busque de forma recursiva ambos subproblemas.
Aunque es difícil demostrar límites teóricos sobre el desempeño de algoritmos de este tipo, pueden resultar muy efectivos en la práctica.
Método de plano de corte
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, e infinitos politopos diferentes tienen esta propiedad. Idealmente, a uno le gustaría usar 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 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 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 de comercio por Dantzig, Fulkerson y Johnson (1954) y generalizado a otros programas enteros por Gomory (1958) , aprovecha esta multiplicidad de posibles relajaciones por encontrar una secuencia de relajaciones que restrinjan más el espacio de la solución hasta que finalmente se obtenga una solución entera. Este método comienza con 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 restringen 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, en el marco de la combinatoria poliédrica ( Aardal y Weismantel 1997 ).
El método de rama y corte relacionado combina el plano de corte y los métodos de rama y encuadernación. 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 ramifica en una de las variables fraccionarias restantes.
Ver también
- Coloración fraccionada , una relajación de programación lineal de coloración de gráficos .
- Redondeo aleatorio , para obtener una solución al problema original desde una solución a la relajación.
Referencias
- Aardal, Karen ; Weismantel, Robert (1997), "Combinatoria poliédrica: una bibliografía anotada", Bibliografías anotadas en optimización combinatoria (PDF) , Wiley.
- Agmon, Shmuel (1954), "El método de relajación para las desigualdades lineales" , Canadian Journal of Mathematics , 6 : 382–392, doi : 10.4153 / CJM-1954-037-2.
- Dantzig, George ; Fulkerson, RD ; Johnson, Selmer (1954), "Solución de un problema de viajantes de comercio a gran escala", Revista de la Sociedad de Investigación de Operaciones de América , 2 (4): 393–410, doi : 10.1287 / opre.2.4.393.
- Feige, Uriel (1998), "Un umbral de ln n para aproximar la cobertura del conjunto", Journal of the ACM , 45 (4): 634–652, CiteSeerX 10.1.1.70.5014 , doi : 10.1145 / 285055.285059.
- Gomory, Ralph E. (1958), "Esquema de un algoritmo para soluciones enteras para programas lineales", Boletín de la American Mathematical Society , 64 (5): 275-279, doi : 10.1090 / S0002-9904-1958-10224- 4.
- Lovász, László (1975), "Sobre la razón de las coberturas integrales y fraccionarias óptimas", Matemáticas discretas , 13 (4): 383–390, doi : 10.1016 / 0012-365X (75) 90058-8.
- Motzkin, TS ; Schoenberg, IJ (1954), "El método de relajación para las desigualdades lineales" , Canadian Journal of Mathematics , 6 : 393–404, doi : 10.4153 / CJM-1954-038-x.
- Raghavan, Prabhakar; Thompson, Clark D. (1987), "Redondeo aleatorio: una técnica para demostrar buenos algoritmos y demostraciones algorítmicas", Combinatorica , 7 (4): 365–374, doi : 10.1007 / BF02579324.
- Young, Neal E. (1995), "Redondeo aleatorio sin resolver el programa lineal", Proc. 6to ACM-SIAM Symp. Algoritmos discretos (SODA) , Soda '95, págs. 170–178, ISBN 9780898713497.