En la 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 . Estos procedimientos se utilizan comúnmente para encontrar soluciones de números enteros a problemas de programación lineal de números enteros mixtos (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 moderados (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 es así, se garantiza que existe una desigualdad lineal que separa el óptimo del casco convexo del verdadero conjunto factible. Encontrar tal desigualdad es el problema de la separación , y tal desigualdad es un recorte . Se puede agregar 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 que se encuentra una solución entera óptima.
Los métodos de plano de corte para la optimización continua convexa general y las variantes se conocen con varios nombres: método de Kelley, método de Kelley-Cheney-Goldstein y métodos de agrupación . Se utilizan popularmente para la minimización convexa no diferenciable, donde una función objetivo convexa y su subgrado se pueden evaluar de manera eficiente, pero no se pueden utilizar 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 las funciones duales de Lagrange . Otra situación habitual 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 la generación de columna retardada es idéntico a realizar un plano de corte en el problema dual respectivo.
Corte de gomory
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 de enteros y de programación de enteros mixtos. Sin embargo, la mayoría de los expertos, incluido el propio Gomory, los consideraba poco prácticos debido a la inestabilidad numérica, así como 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 efectivos en combinación con bifurcaciones (llamadas bifurcaciones 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 elevación y proyecto que domina los recortes de Gomory. [ cita requerida ]
Deje que un problema de programación de enteros se formule (en forma canónica ) como:
El método procede primero eliminando el requisito de que x i sea números enteros y resolviendo el problema de programación lineal 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, el método encuentra un hiperplano con el vértice en un lado y todos los puntos enteros factibles en el otro. Esto luego se agrega como una restricción lineal adicional para excluir el vértice encontrado, creando un programa lineal modificado. A continuación, se resuelve el nuevo programa y se repite el proceso hasta que se encuentra una solución entera.
El uso del método simplex para resolver un programa lineal produce un conjunto de ecuaciones de la forma
donde x i es una variable básica y el x j ' s son las variables no básicas. Reescribe esta ecuación para que las partes enteras estén en el lado izquierdo y las partes fraccionarias estén en el lado derecho:
Para cualquier punto entero en la región factible, el lado derecho de esta ecuación es menor que 1 y el lado izquierdo es un número entero, por lo tanto, el valor común debe ser menor o igual a 0. Entonces, la desigualdad
debe ser válido para cualquier punto entero en la región factible. Además, las variables no básicas son iguales a ceros en cualquier solución básica y si x i no es un número entero para la solución básica x ,
Entonces, la desigualdad anterior excluye la solución factible básica y, por lo tanto, es un corte con las propiedades deseadas. Al introducir una nueva variable de holgura x k para esta desigualdad, se agrega una nueva restricción al programa lineal, a saber
Optimizacion convexa
Los métodos de 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 medios espacios cerrados y resolver una secuencia de programas lineales aproximados .
Ver también
Referencias
- Marchand, Hugues; Martín, Alejandro; Weismantel, Robert; Wolsey, Laurence (2002). "Planos de corte en programación de enteros y enteros mixtos". 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. Programación Matemática Ser. B , (2008) 112: 3-44. [1]
- Cornuéjols, Gérard (2007). Renacimiento de los cortes de Gomory en la década de 1990. Annals of Operations Research , vol. 149 (2007), págs. 63–66. [2]
enlaces externos
- "Programación de enteros" Sección 9.8 Programación matemática aplicada Capítulo 9 Programación de enteros (texto completo). Bradley, Hax y Magnanti (Addison-Wesley, 1977)