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 de comercio 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 por medio de desigualdades lineales, denominadas cortes . Dichos procedimientos se utilizan comúnmente para encontrar soluciones enteras a problemas de programación lineal entera mixta (MILP), así como para resolver problemas de optimización convexa generales, no necesariamente diferenciables . El uso de planos de corte para resolver MILP fue introducido por Ralph E. Gomory .

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 suaves (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. El óptimo obtenido se prueba para ser una solución entera. Si no lo es, se garantiza que existe una desigualdad lineal que separa el óptimo de la envoltura convexa del verdadero conjunto factible. Encontrar tal desigualdad es el problema de separación , y tal desigualdad es un corte . Se puede agregar un corte al programa lineal relajado. Luego, la solución no entera actual ya no es factible para la relajación. Este proceso se repite hasta que se encuentra una solución entera óptima.

Los métodos de plano de corte para la optimización continua convexa general y 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 los métodos de gradiente habituales para la optimización diferenciable no se pueden utilizar. Esta situación es más típica para 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 estructurada en el que se obtienen formulaciones con un número exponencial de variables. Generar estas variables a demanda por medio de la generación de columnas retrasadas 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 consideraban poco prácticos debido a la inestabilidad numérica, así como ineficaces porque se necesitaban muchas rondas de cortes 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 la ramificación y acotación (llamada ramificación y corte ) y las 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 una tabla simplex, mientras que muchos otros tipos de cortes son costosos o incluso NP-difíciles de separar. Entre otros cortes generales para MILP, el más notable es el de elevación y proyección, que domina los cortes de Gomory. ^{[1] [2]}

El corte de Gomory

Sea un problema de programación entera formulado (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 se debe encontrar para maximizar el objetivo respetando las restricciones lineales.

Idea general

El método procede eliminando primero el requisito de que las x _i sean números enteros y resolviendo el problema de programación lineal relajada asociado para obtener una solución factible básica. 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. Esto se agrega luego como una restricción lineal adicional para excluir el vértice encontrado, creando un programa lineal modificado. Luego se resuelve el nuevo programa y el proceso se repite hasta que se encuentra una solución entera.

Paso 1: resolver el programa lineal relajado

El uso del 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 las 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 los coeficientes y con una barra para indicar la última tabla producida por el método simplex. Estos coeficientes son diferentes de los coeficientes en la matriz A y el vector b. ${\displaystyle x_{i}={\bar {b}}_{i}}$ ${\displaystyle x_{j}=0}$ ${\displaystyle {\bar {b}}_{i}}$ ${\displaystyle {\bar {a}}_{i,j}}$

Paso 2: Encuentra una restricción lineal

Consideremos ahora una variable básica que no sea un número entero. Reescriba 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 entero ya que todos los términos , , , son 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. Por lo tanto, 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 cumplirse para cualquier punto entero en la región factible. Además, las variables no básicas son iguales a cero en cualquier solución básica y si x _i no es un 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

Por lo tanto, la desigualdad anterior excluye la solución factible básica y, por lo tanto, es un corte con las propiedades deseadas. Más precisamente, es negativa para cualquier punto entero en la región factible y estrictamente positiva para la solución factible básica (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}}.}$

Optimización convexa

Los métodos de plano de corte también son aplicables en la 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]

Véase también

• Descomposición de Benders
• Ramificar y cortar
• Rama y límite
• 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". 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". 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). "Localization and Cutting-plane Methods" (notas de clase del curso) . Consultado el 27 de mayo de 2022 .

• Marchand, Hugues; Martin, Alexander; Weismantel, Robert; Wolsey, Laurence (2002). "Planos de corte en programación entera y entera mixta". Matemáticas Aplicadas Discretas . 123 (1–3): 387–446. doi : 10.1016/s0166-218x(01)00348-1 .
• Avriel, Mordecai (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. Mathematical Programming Ser. B , (2008) 112:3–44. [1]
• Cornuéjols, Gérard (2007). El resurgimiento de los recortes de Gomory en los años 1990. Annals of Operations Research , 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)