Método del plano de corte

Técnica de optimización para resolver programas lineales enteros (mixtos)

La intersección del cubo unitario con el plano de corte . En el contexto del problema del viajante en tres nodos, esta desigualdad (bastante débil ^{[ ¿ por qué? ]} ) establece que cada recorrido debe tener al menos dos aristas. ${\displaystyle x_{1}+x_{2}+x_{3}\geq 2}$

En optimización matemática , el método del plano de corte es cualquiera de una variedad de métodos de optimización que refinan iterativamente un conjunto factible o una función objetivo mediante desigualdades lineales, denominadas cortes . Estos procedimientos se utilizan comúnmente para encontrar soluciones enteras a problemas de programación lineal entera mixta (MILP), así como para resolver problemas generales de optimización convexa , no necesariamente diferenciables. Ralph E. Gomory introdujo el uso de planos de corte para resolver MILP .

Los métodos de plano de corte para MILP funcionan resolviendo un programa lineal no entero, la relajación lineal del programa entero dado. La teoría de la programación lineal dicta que bajo supuestos leves (si el programa lineal tiene una solución óptima y si la región factible no contiene una línea), siempre se puede encontrar un punto extremo o un punto de esquina que sea óptimo. Se prueba que el óptimo obtenido es una solución entera. Si no es así, se garantiza que existirá una desigualdad lineal que separa el óptimo del casco convexo del verdadero conjunto factible. Encontrar tal desigualdad es el problema de separación , y tal desigualdad es una reducción . Se puede añadir un corte al programa lineal relajado. Entonces, la solución actual no entera ya no es factible para la relajación. Este proceso se repite hasta encontrar una solución entera óptima.

Los métodos del plano de corte para la optimización continua convexa general y sus variantes se conocen con varios nombres: método de Kelley, método de Kelley-Cheney-Goldstein y métodos de paquete . Se utilizan popularmente para la minimización convexa no diferenciable, donde una función objetivo convexa y su subgradiente se pueden evaluar de manera eficiente pero no se pueden usar los métodos de gradiente habituales para la optimización diferenciable. Esta situación es más típica de la maximización cóncava de funciones duales lagrangianas . Otra situación común es la aplicación de la descomposición de Dantzig-Wolfe a un problema de optimización estructurado en el que se obtienen formulaciones con un número exponencial de variables. Generar estas variables bajo demanda mediante generación retardada de columnas es idéntico a realizar un plano de corte en el respectivo problema dual.

Historia

Los planos de corte fueron propuestos por Ralph Gomory en la década de 1950 como un método para resolver problemas de programación entera y programación entera mixta. Sin embargo, la mayoría de los expertos, incluido el propio Gomory, los consideraron poco prácticos debido a la inestabilidad numérica, además de ineficaces porque se necesitaban muchas rondas de recortes para avanzar hacia la solución. Las cosas cambiaron cuando, a mediados de la década de 1990, Gérard Cornuéjols y sus colaboradores demostraron que eran muy eficaces en combinación con ramificaciones y cortes (llamados ramificaciones y cortes ) y formas de superar las inestabilidades numéricas. Hoy en día, todos los solucionadores MILP comerciales utilizan cortes de Gomory de una forma u otra. Los cortes de Gomory se generan de manera muy eficiente a partir de un cuadro simplex, mientras que muchos otros tipos de cortes son costosos o incluso NP difíciles de separar. Entre otros recortes generales para MILP, el más notable es el de levantamiento y proyecto que domina los recortes de Gomory. ^{[1] [2]}

corte de gomory

Formule un problema de programación entera (en forma canónica ) como:

${\displaystyle {\begin{aligned}{\text{Maximize }}&c^{T}x\\{\text{Subject to }}&Ax\leq b,\\&x\geq 0,\,x_{i}{\text{ all integers}}.\end{aligned}}}$

donde A es una matriz y b, c es un vector. El vector x es desconocido y debe encontrarse para maximizar el objetivo respetando las restricciones lineales.

Idea general

El método procede eliminando primero el requisito de que x _i sean números enteros y resolviendo el problema de programación lineal relajada asociado para obtener una solución básica factible. Geométricamente, esta solución será un vértice del politopo convexo que consta de todos los puntos factibles. Si este vértice no es un punto entero, entonces el método encuentra un hiperplano con el vértice en un lado y todos los puntos enteros factibles en el otro. Luego, esto se agrega como una restricción lineal adicional para excluir el vértice encontrado, creando un programa lineal modificado. Luego se resuelve el nuevo programa y se repite el proceso hasta encontrar una solución entera.

Paso 1: resolver el programa lineal relajado

Usar el método simplex para resolver un programa lineal produce un conjunto de ecuaciones de la forma

${\displaystyle x_{i}+\sum _{j}{\bar {a}}_{i,j}x_{j}={\bar {b}}_{i}}$

donde x _i es una variable básica y x _j son las variables no básicas (es decir, la solución básica que es una solución óptima para el programa lineal relajado es y ). Escribimos coeficientes y con una barra para indicar el último cuadro producido por el método simplex. Estos coeficientes son diferentes de los coeficientes de la matriz A y del vector b. ${\displaystyle x_{i}={\bar {b}}_{i}}$ ${\displaystyle x_{j}=0}$ ${\displaystyle {\bar {b}}_{i}}$ ${\displaystyle {\bar {a}}_{i,j}}$

Paso 2: encontrar una restricción lineal

Consideremos ahora una variable básica que no es un número entero. Reescribe la ecuación anterior de modo que las partes enteras se sumen en el lado izquierdo y las partes fraccionarias en el lado derecho: ${\displaystyle x_{i}}$

${\displaystyle x_{i}+\sum _{j}\lfloor {\bar {a}}_{i,j}\rfloor x_{j}-\lfloor {\bar {b}}_{i}\rfloor ={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}.}$

Para cualquier punto entero en la región factible, el lado izquierdo es un número entero ya que todos los términos , , , son números enteros. El lado derecho de esta ecuación es estrictamente menor que 1: de hecho, es estrictamente menor que 1 mientras que es negativo. Por lo tanto el valor común debe ser menor o igual a 0. Entonces la desigualdad ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle \lfloor {\bar {a}}_{i,j}\rfloor }$ ${\displaystyle \lfloor {\bar {b}}_{i}\rfloor }$ ${\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor }$ ${\displaystyle -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}}$

${\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}\leq 0}$

debe ser válido para cualquier punto entero en la región factible. Además, las variables no básicas son iguales a 0 en cualquier solución básica y si x _i no es un número entero para la solución básica x ,

${\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor >0.}$

Conclusión

Entonces, la desigualdad anterior excluye la solución básica factible y, por lo tanto, es un corte con las propiedades deseadas. Más precisamente, es negativo para cualquier punto entero en la región factible y estrictamente positivo para la solución básica factible (no entera) del programa lineal relajado. Al introducir una nueva variable de holgura x _k para esta desigualdad, se agrega una nueva restricción al programa lineal, a saber ${\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}}$

${\displaystyle x_{k}+\sum _{j}(\lfloor {\bar {a}}_{i,j}\rfloor -{\bar {a}}_{i,j})x_{j}=\lfloor {\bar {b}}_{i}\rfloor -{\bar {b}}_{i},\,x_{k}\geq 0,\,x_{k}{\mbox{ an integer}}.}$

Optimizacion convexa

Los métodos del plano de corte también son aplicables en programación no lineal . El principio subyacente es aproximar la región factible de un programa no lineal (convexo) mediante un conjunto finito de semiespacios cerrados y resolver una secuencia de programas lineales aproximados . ^[3]

Ver también

• Descomposición de Benders
• Rama y corte
• Rama y atado
• Generación de columnas
• Descomposición de Dantzig-Wolfe

Referencias

1. Gilmore, Paul C; Gomory, Ralph E. (1961). "Un enfoque de programación lineal para el problema del material de corte". La investigación de operaciones . 9 (6): 849–859. doi :10.1287/opre.9.6.849.
2. Gilmore, Paul C; Gomory, Ralph E. (1963). "Un enfoque de programación lineal para el problema del material de corte-Parte II". La investigación de operaciones . 11 (6): 863–888. doi :10.1287/opre.11.6.863.
3. Boyd, S.; Vandenberghe, L. (18 de septiembre de 2003). "Métodos de localización y plano de corte" (apuntes del curso) . Consultado el 27 de mayo de 2022 .

• Marchand, Hugues; Martín, Alejandro; Weismantel, Robert; Wolsey, Laurence (2002). "Planos de corte en programación entera y entera mixta". Matemática Aplicada Discreta . 123 (1–3): 387–446. doi : 10.1016/s0166-218x(01)00348-1 .
• Avriel, Mardoqueo (2003). Programación no lineal: análisis y métodos. Publicaciones de Dover. ISBN 0-486-43227-0 
• Cornuéjols, Gérard (2008). Desigualdades válidas para programas lineales enteros mixtos. Ser. de Programación Matemática. B , (2008) 112:3–44. [1]
• Cornuéjols, Gérard (2007). Renacimiento de los recortes de Gomory en la década de 1990. Anales de investigación de operaciones , vol. 149 (2007), págs. 63–66. [2]

enlaces externos

• "Programación entera" Sección 9.8 Programación matemática aplicada Capítulo 9 Programación entera (texto completo). Bradley, Hax y Magnanti (Addison-Wesley, 1977)