En matemáticas aplicadas , el método de ramificación y precio es un método de optimización combinatoria para resolver problemas de programación lineal entera (ILP) y programación lineal entera mixta (MILP) con muchas variables. El método es un híbrido entre los métodos de ramificación y cota y de generación de columnas .
El método de ramificación y precio es un método de ramificación 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, se excluyen conjuntos de columnas de la relajación LP para reducir los requisitos computacionales y de memoria y luego se agregan columnas nuevamente 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 variable correspondiente igual a cero en cualquier solución óptima. Por lo 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 Maestro . La descomposición se realiza para obtener una formulación del problema que proporcione 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 normalmente contiene muchas variables y, por lo tanto, se resuelve una versión modificada, llamada Problema Maestro Restringido , que solo considera un subconjunto de las columnas. [2] Luego, para verificar la optimalidad, se resuelve un subproblema llamado problema de fijación 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 fijación de precios en sí mismo 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ística y local. [3] El subproblema solo debe resolverse por completo para demostrar que una solución óptima para el Problema Maestro Restringido es también una solución óptima para el Problema Maestro. Cada vez que se encuentra una columna con un costo reducido negativo, se agrega al problema maestro restringido y se vuelve a optimizar la relajación. Si ninguna columna puede ingresar a la base y la solución de la relajación no es un entero, se produce una ramificación. [1]
La mayoría de los algoritmos de ramificación y precio 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 precio y rama, el método se conoce como precio de rama y corte . [5]
El método de rama y precio se puede utilizar para resolver problemas en una variedad de áreas de aplicación, entre ellas: