TRPM2de3

UNIVERSITAT POLITÈCNICA
DE CATALUNYA

UNIVERSITAT POLITECNICA DE CATALUNYA

Tesis doctoral:
METALGORITMO DE OPTIMIZACIÓN COMBINATORIA
MEDIANTE LA EXPLORACIÓN DE GRAFOS

Director de la tesis:
Dr. D. Albert Corominas Subías
Para optar al Grado de Doctor Ingeniero Industrial, presenta:
Rafael Pastor Moreno

Barcelona, Junio 1999

Procedimientos de resolución enumerativos.

108

3.5.9. Branch andprice.
Como definen Johnson et al. (1997), se llama algoritmos branch and price a aquellos
algoritmos branch and bound, en los que los programas lineales resultantes de la
relajación son resueltos en cada vértice del árbol de búsqueda mediante generación de
columnas.
Gass & Harris (1996) definen la técnica de "generación de columnas" -introducida en
1961 por Gilmore & Gomory en la resolución deproblemas de corte- como un
procedimiento que permite solucionar problemas de programación lineal de grandes
dimensiones, mediante la generación de las columnas de la matriz de restricciones sólo
cuando son necesarias (así, es habitualmente empleado cuando la matriz de restricciones
es demasiado grande para ser almacenada o cuando sólo es conocida implícitamente);
Savelsbergh (1997) define dichatécnica como un esquema pricing para resolver
programas lineales de gran tamaño: en vez de valorar variables no básicas por
enumeración, se encuentra la variable con menor (o mayor) coste reducido mediante la
resolución de un problema de optimización. Como aclaran Jünger et al. (1994), Saltzman
(1995), Johnson et al. (1997), el propio Savelsbergh (1997) y Jünger & Thienel (1998), la
idea básica essimple: consiste en resolver el programa lineal con un número de
columnas omitidas (ya que son demasiadas para manejarlas eficientemente y además
muchas de ellas tendrán su variable asociada igual a O en una solución óptima)
mediante, por ejemplo, el simplex, y comprobar la optimalidad de la solución obtenida
resolviendo un subproblema, llamado pricing problem, con el que se definen las
columnas (lasvariables) que deben entrar en la base; si se encuentran dichas columnas
el programa lineal es reoptimizado, si no ya se ha alcanzado la solución óptima. Una
condición necesaria para que este procedimiento sea eficaz, es que el pricing problem
sea fácil de solucionar.
Según Saltzman (1995) y Jünger & Thienel (1998), branch and price es un concepto dual
al de branch and cut (similar en espíritusegún Savelsbergh 1997) y puede ser aplicado a
programas enteros con un gran número de variables; por tanto, en un esquema branch
and bound el hecho diferencial de este procedimiento es la forma de resolución del
programa lineal, y, como en todos los procedimientos de este tipo, el proceso de
ramificación se ejecuta cuando el programa lineal no proporciona una solución óptima
entera. Sin embargo, comoalgunos autores opinan (Johnson 1989, Johnson et al. 1997,
Mehrotra & Trick 1997, Savelsbergh 1997, etc.), no es apropiado aplicar un branch and
bound "standard" sobre las columnas existentes ya que pueden inferir en el algoritmo de
generación de columnas, y es conveniente diseñar un conjunto de reglas especiales de
ramificación: la regla de ramificación debe ser compatible con el problemapricing:
debe ser capaz de modificar el subproblema de forma que las columnas que son

Procedimientos de resolución enumerativos.

109

infactibles debido a las restricciones de ramificación no sean generadas y el
subproblema de generación de columnas permanezca tratable (Savelsbergh 1997).
Como expone Savelsbergh (1997), recientemente se han comenzado a desarrollar
estrategias de ramificación quemanejan esas dificultades: Desrochers, Desrosiers &
Solomon en 1992 para el VRP, Desrochers & Soumis en 1989 y Anbil, Tanga &
Johnson en 1991 para el problema de secuenciación de tripulaciones, y Vanee, Barnhart,
Johnson & Nemhauser en 1992 para el problema de corte. Para el problema de
asignación generalizada, Johnson et al. (1997) y Savelsbergh (1997) proponen dos
formulaciones alternativas: por...