Linear programming relaxation

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.

For example, in a 0–1 integer program, all constraints are of the form

${\displaystyle x_{i}\in \{0,1\}}$.

The relaxation of the original integer program instead uses a collection of linear constraints

${\displaystyle 0\leq x_{i}\leq 1.}$

The resulting relaxation is a linear program, hence the name. This relaxation technique transforms an NP-hardoptimization problem (integer programming) into a related problem that is solvable in polynomial time (linear programming); the solution to the relaxed linear program can be used to gain information about the solution to the original integer program.

Consider the set cover problem, the linear programming relaxation of which was first considered by Lovász in 1975.^[1] In this problem, one is given as input a family of setsF = {S₀, S₁, ...}; the task is to find a subfamily, with as few sets as possible, having the same union as F.

To formulate this as a 0–1 integer program, form an indicator variablex_i for each set S_i, that takes the value 1 when S_i belongs to the chosen subfamily and 0 when it does not. Then a valid cover can be described by an assignment of values to the indicator variables satisfying the constraints

${\displaystyle \textstyle x_{i}\en \{0,1\}}$

(that is, only the specified indicator variable values are allowed) and, for each element e_j of the union of F,

${\displaystyle \textstyle \sum _{\{i\mid e_{j}\in S_{i}\}}x_{i}\geq 1}$

(that is, each element is covered). The minimum set cover corresponds to the assignment of indicator variables satisfying these constraints and minimizing the linear objective function

${\displaystyle \textstyle \min \sum _ {i} x_ {i}.}$

The linear programming relaxation of the set cover problem describes a fractional cover in which the input sets are assigned weights such that the total weight of the sets containing each element is at least one and the total weight of all sets is minimized.

Como ejemplo específico del problema de cobertura de conjuntos, consideremos la instancia F = {{ a , b }, { b , c }, { a , c }}. Existen 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, existe una solución fraccionaria en la que a cada conjunto se le asigna un peso de 1/2, y para la cual el valor total de la función objetivo es 3/2. Así, en este ejemplo, la relajación de programación lineal tiene un valor diferente al del programa entero 0-1 sin relajación.

La relajación de programación lineal de un programa entero puede resolverse mediante cualquier técnica estándar de programación lineal. Si 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 no suele ser cierto, salvo en algunos casos especiales (por ejemplo, problemas con especificaciones de matrices totalmente unimodulares ).

En todos los casos, la calidad de la solución del programa lineal es al menos tan buena como la del programa entero, ya que cualquier solución de un programa entero también sería una solución válida para un programa lineal. 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 original. Por lo tanto, la relajación proporciona una cota optimista para la solución del programa entero.

En el ejemplo del problema de cobertura de conjuntos descrito anteriormente, donde 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 sin relajar 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 la solución óptima debe ser al menos tan grande como el siguiente entero mayor, 2. Por lo tanto, en este caso, a pesar de tener un valor diferente al del problema sin relajar, la relajación de programación lineal nos da una cota inferior ajustada para la calidad de la 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 la de su relajación. En un caso de un problema de minimización, si el mínimo real (el mínimo del problema entero) es${\displaystyle M_{\text{int}}}$y el mínimo relajado (el mínimo de la relajación de programación lineal) es${\displaystyle M_{\text{frac}}}$, entonces la brecha de integralidad de esa instancia es${\displaystyle IG={\frac {M_{\text{int}}}{M_{\text{frac}}}}}$. En un problema de maximización, la fracción se invierte. La brecha de integralidad siempre es 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 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${\displaystyle M_{\text{frac}}}$, una solución entera de tamaño como máximo${\displaystyle RR\cdot M_{\text{frac}}}$(donde RR es la razó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${\displaystyle M_{\text{int}}=IG\cdot M_{\text{frac}}}$Por lo tanto, necesariamente${\displaystyle RR\geq IG}$El coeficiente de redondeo RR es solo una cota superior para el coeficiente de aproximación, por lo que, en teoría, el coeficiente de aproximación real puede ser inferior a IG , aunque esto puede ser difícil de demostrar. En la práctica, un valor elevado de IG suele implicar que el coeficiente de aproximación en la relajación de programación lineal podría ser deficiente, y que quizás sea 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 th 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 , se elige aleatoriamente el valor de cada variable indicadora 0–1 x _i como 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 sin cubrir, 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 aleatoria 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 para 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 sin cubrir. Este algoritmo voraz aproxima la cobertura de conjuntos con el mismo factor H _n que Lovász demostró como la brecha de integralidad para la cobertura de conjuntos. Existen fuertes razones teóricas de complejidad para creer que ningún algoritmo de aproximación en tiempo polinomial puede lograr una razón de aproximación significativamente mejor. ^{[ 4 ]}   

Técnicas de redondeo aleatorio similares , y algoritmos de aproximación desaleatorizados, pueden utilizarse 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 la aproximación, la programación lineal desempeña 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 fijados a 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 tomar cualquiera de los dos 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 ₀ es el conjunto completo de variables del problema original. Luego, para cada subproblema i , realiza los siguientes pasos.

1. Calcula 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.
2. Si la solución relajada del subproblema actual es peor que la mejor solución entera encontrada hasta el momento, retroceda desde esta rama de la búsqueda recursiva.
3. Si la solución relajada tiene todas las variables establecidas en 0 o 1, compárela con la mejor solución entera encontrada hasta el momento y quédese con la que sea mejor.
4. De lo contrario, sea x _j cualquier variable que tenga un valor fraccional en la solución relajada. Formule dos subproblemas, uno en el que x _j sea igual a 0 y otro en el que x _j sea igual a 1; en ambos subproblemas, se siguen utilizando las asignaciones de valores existentes a algunas de las variables, por lo que el conjunto de variables restantes se convierte en V _i  \  { x _j }. Busque recursivamente en ambos subproblemas.

Si bien es difícil demostrar los límites teóricos del rendimiento de algoritmos de este tipo, pueden ser muy eficaces en la práctica.

Dos programas enteros binarios equivalentes, ya que comparten la misma función objetivo y el mismo conjunto de soluciones factibles, pueden tener relajaciones de programación lineal muy diferentes: una relajación de programación lineal puede visualizarse geométricamente como un politopo convexo que incluye todas las soluciones factibles y excluye todos los demás vectores binarios, y existen infinitos politopos diferentes que poseen esta propiedad. Idealmente, se desearía utilizar como relajación la envoltura convexa de las soluciones factibles; la programación lineal sobre este politopo proporcionaría automáticamente la solución correcta al programa entero original. Sin embargo, en general, este politopo tendrá un número exponencial de facetas y será difícil de construir. Las relajaciones típicas, como la del problema de cobertura de conjuntos mencionado anteriormente, forman un politopo que contiene estrictamente la envoltura convexa y tiene vértices distintos de los vectores binarios que resuelven el problema sin relajar.

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 multiplicidad de posibles relajaciones al encontrar una secuencia de relajaciones que restringen más el espacio de soluciones hasta obtener finalmente 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 para el problema sin relajar. 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 a fin de 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 con mayor precisión el espacio de soluciones; siempre existe un plano de corte de este tipo que separa cualquier solución fraccionaria de las soluciones enteras. Se ha investigado mucho sobre métodos para encontrar estas facetas para diferentes tipos de problemas de optimización combinatoria , dentro del 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 acotación. En cualquier subproblema, ejecuta el método del plano de corte hasta que no se encuentran más planos de corte, y luego se ramifica en una de las variables fraccionarias restantes.

• Coloreado fraccional , una relajación de programación lineal del coloreado de grafos .
• Redondeo aleatorio , para obtener una solución al problema original a partir de una solución a la relajación.

• 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 desigualdades lineales" , Canadian Journal of Mathematics , 6 : 382–392 , doi : 10.4153/CJM-1954-037-2 , archivado del original el 24 de febrero de 2012 , recuperado el 16 de abril de 2010..
• Dantzig, George ; Fulkerson, DR ; Johnson, Selmer (1954), "Solución de un problema del viajante a gran escala", Journal of the Operations Research Society of America , 2 (4): 393– 410, doi : 10.1287/opre.2.4.393.
• Feige, Uriel (1998), "Un umbral de ln n para aproximar la cobertura de conjuntos", 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 de programas lineales", Boletín de la Sociedad Matemática Americana , 64 (5): 275– 279, doi : 10.1090/S0002-9904-1958-10224-4.
• Lovász, László (1975), "Sobre la relación de coberturas óptimas integrales y fraccionarias", 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 desigualdades lineales" , Canadian Journal of Mathematics , 6 : 393–404 , doi : 10.4153/CJM-1954-038-x , archivado del original el 24 de febrero de 2012 , recuperado el 16 de abril de 2010..
• Raghavan, Prabhakar; Thompson, Clark D. (1987), "Redondeo aleatorio: una técnica para algoritmos y pruebas algorítmicas demostrablemente buenos", Combinatorica , 7 (4): 365–374 , doi : 10.1007/BF02579324.
• Young, Neal E. (1995), "Redondeo aleatorio sin resolver el programa lineal" , Actas del 6.º Simposio ACM-SIAM sobre Algoritmos Discretos (SODA) , Soda '95, págs. 170–178 , ISBN  9780898713497.