En matemáticas aplicadas , la rama y el precio es un método de optimización combinatoria para resolver problemas de programación lineal de enteros (ILP) y programación lineal de enteros mixtos (MILP) con muchas variables. El método es un híbrido de métodos de generación de ramificaciones, enlaces y columnas .
Descripción del algoritmo
La rama y el precio es un método de rama y límite en el que en cada nodo del árbol de búsqueda, se pueden agregar columnas a la relajación de programación lineal (relajación LP). Al comienzo del algoritmo, los conjuntos de columnas se excluyen de la relajación LP para reducir los requisitos computacionales y de memoria y luego las columnas se vuelven a agregar a la relajación LP según sea necesario. El enfoque se basa en la observación de que para problemas grandes, la mayoría de las columnas no serán básicas y tendrán su correspondiente variable igual a cero en cualquier solución óptima. Por tanto, la gran mayoría de las columnas son irrelevantes para resolver el problema.
El algoritmo normalmente comienza utilizando una reformulación, como la descomposición de Dantzig-Wolfe , para formar lo que se conoce como el problema principal . La descomposición se realiza para obtener una formulación del problema que dé mejores límites cuando se resuelve la relajación que cuando se resuelve la relajación de la formulación original. Pero, la descomposición generalmente contiene muchas variables y, por lo tanto, se resuelve una versión modificada, llamada Problema principal restringido , que solo considera un subconjunto de las columnas. [2] Luego, para verificar la optimización, se resuelve un subproblema llamado problema de precios para encontrar columnas que puedan ingresar a la base y reducir la función objetivo (para un problema de minimización). Esto implica encontrar una columna que tenga un costo reducido negativo . Tenga en cuenta que el problema de precios en sí puede ser difícil de resolver, pero como no es necesario encontrar la columna con el costo reducido más negativo, se pueden utilizar métodos de búsqueda heurísticos y locales. [3] El subproblema solo debe resolverse hasta su finalización para demostrar que una solución óptima al Problema principal restringido es también una solución óptima al Problema principal. Cada vez que se encuentra una columna con un costo reducido negativo, se agrega al Problema principal restringido y la relajación se vuelve a optimizar. Si ninguna columna puede entrar en la base y la solución a la relajación no es un número entero, se produce la ramificación. [1]
La mayoría de los algoritmos de sucursales y precios son específicos del problema, ya que el problema debe formularse de tal manera que se puedan formular reglas de ramificación efectivas y que el problema de precios sea relativamente fácil de resolver. [4]
Si se utilizan planos de corte para ajustar las relajaciones LP dentro de un algoritmo de bifurcación y precio, el método se conoce como precio y corte de bifurcación . [5]
Aplicaciones de sucursal y precio
El método de sucursal y precio se puede utilizar para resolver problemas en una variedad de áreas de aplicación, que incluyen:
- Gráfico de varios colores. [3] Esta es una generalización del problema de coloración de gráficos en el que a cada nodo de un gráfico se le debe asignar un número preestablecido de colores y los nodos que comparten un borde no pueden tener un color en común. El objetivo es entonces encontrar el número mínimo de colores necesarios para tener una coloración válida. El problema de los múltiples colores se puede utilizar para modelar una variedad de aplicaciones, incluida la programación de trabajos y la asignación de canales de telecomunicaciones.
- Problemas de generación de rutas para vehículos . [2]
- Problema de asignación generalizado . [6]
Ver también
Referencias externas
- Diapositivas de conferencias sobre sucursal y precio
- Código de prototipo para una sucursal genérica y un algoritmo de precios
- Preguntas frecuentes de BranchAndCut.org
- SCIP un marco de código abierto para sucursales de corte y precio y un solucionador de programación de enteros mixtos
- ABACUS - Un sistema de sucursales y CUt - software de código abierto
Referencias
- ↑ a b Akella, M .; S. Gupta; A. Sarkar. "Rama y precio: generación de columnas para resolver enormes programas de enteros" (PDF) . Archivado desde el original (PDF) el 21 de agosto de 2010 . Consultado el 19 de diciembre de 2012 .
- ^ a b Feillet, Dominique (2010). "Un tutorial sobre generación de columnas y sucursales y precios para problemas de generación de rutas de vehículos". 4OR . 8 (4): 407–424. doi : 10.1007 / s10288-010-0130-z .
- ^ a b Mehrota, Anuj; MA Trick (2007). Un enfoque de ramificación y precio para la multicoloración de gráficos . Extendiendo los Horizontes: Avances en Computación, Optimización y Tecnologías de Decisión . Serie de interfaces de investigación de operaciones / ciencias de la computación. 37 . págs. 15-29 . CiteSeerX 10.1.1.163.6870 . doi : 10.1007 / 978-0-387-48793-9_2 . ISBN 978-0-387-48790-8.
- ^ Gamrath, G. " Ramas genéricas de corte y precio" (PDF) .
- ^ Desrosiers, J .; ME Lubbecke (2010). "Algoritmos de corte y precio de rama". Enciclopedia Wiley de Investigación de Operaciones y Ciencias de la Gestión .
- ^ Savelsbergh, M. (1997). "Un algoritmo de sucursal y precio para el problema de asignación generalizada". Investigación operativa . 831-841. 45 (6): 831–841. doi : 10.1287 / opre.45.6.831 .
- Barnhart, Cynthia; Johnson, Ellis L .; Nemhauser, George L .; Savelsbergh, Martin WP; Vance, Pamela H. (1998), "Ramificación y precio: generación de columnas para resolver programas de enteros enormes", Investigación de operaciones , 46 (3): 316–329, CiteSeerX 10.1.1.197.7390 , doi : 10.1287 / opre. 46.3.316 , JSTOR 222825