TRPM1 de 3
TRPM1 de 3
TRPM1 de 3
Director de la tesis: Dr. D. Albert Corominas Subas Para optar al Grado de Doctor Ingeniero Industrial, presenta: Rafael Pastor Moreno
PATA
PG
e
IH Departament
Mi reconocimiento ms sincero a mi director de tesis que ha hecho posible su realizacin. Gracias Albert.
Gracias tambin a mis compaeros por sus valiosos consejos y nimos: Don Ramn, Anna, Joaqun y Manel.
ndice
NDICE 1. INTRODUCCIN. JUSTIFICACIN. OBJETIVOS. ALCANCE. 1.1. Introduccin y justificacin: marco general de los problemas de optimizacin combinatoria. 1.1.1. Problemas de optimizacin combinatoria. 1.1.2. Procedimientos de resolucin enumerativos. 1.1.2.1. Procedimientos basados en la "fuerza bruta". 1.1.2.2. Procedimientos que utilizan "bsqueda heurstica". 1.1.2.3. Programacin dinmica. 1.1.2.4. Branch and bound. 1.1.2.5. Otros procedimientos guiados y del rea de la inteligencia artificial. 1.1.3. Relaciones entre los diferentes procedimientos de resolucin. 1.2. Objetivos y alcance. 2. PROBLEMAS DE OPTIMIZACIN COMBINATORIA. 2.1. Definicin. 2.2. Ejemplos. 2.3. Complejidad de los problemas de optimizacin combinatoria. 2.4. Representacin de los problemas de optimizacin combinatoria. 1 1 1 5 9 10 10 10 10 11 13 15 15 17 20 29
3. PROCEDIMIENTOS DE RESOLUCIN ENUMERATIVOS. 35 3.1. Clasificacin de los procedimientos de resolucin enumerativos. 38 3.1.1. Ciegos / guiados. 39 3.1.2. Heursticos / exactos. 40 3.1.3. Obtencin de una solucin factible / una solucin subptima / una o todas las soluciones ptimas. 42 3.1.4. Agrupando estados equivalentes / sin agrupar estados equivalentes. 43 3.1.5. Conjuntos de procedimientos referenciados. .43 3.2. Funciones de evaluacin. 45 3.3. Procedimientos de bsqueda basados en la "fuerza bruta". 50 3.3.1. Procedimiento del Museo Britnico (British Museum). 51 3.3.2. Bsqueda aleatoria. 52 3.3.3. Bsqueda en profundidad (depthfirst search o DFS). 52 3.3.4. Bsqueda en anchura (breadth first search o BFS). 54 3.3.5. Bsqueda primero el de menor coste (uniform cost search o cheapest first strategy). 56 3.3.6. Bsqueda primero el de mejor cota (best bound search). 56 3.3.7. Bsqueda primero el mejor (best first search o BF). 57
ndice
3.3.8. Bsqueda primero el mejor* (best first search* o BF*). 3.3.9. Bsqueda primero los mejores (best few). 3.3.10. Parallel depth first search (PDFS). 3.3.11. Floating down search (FDS). 3.3.12. Jump backtracking. 3.3.13. Procedimientos de bsqueda usualmente descritos en el rea de la inteligencia artificial. 3.4. Procedimientos de bsqueda basados en programacin dinmica (dynamic programming o DP). 3.5. Procedimientos de bsqueda basados en la poda de vrtices mediante cotas. 3.5.1. Branch and bound. 3.5.1.1. Formalizacin. 3.5.1.2. Particularidades de la funcin objetivo. 3.5.1.3. Estrategias de ramificacin / separacin. 3.5.1.4. Propiedades de la solucin ptima. 3.5.1.5. Clculo de la cota superior. 3.5.1.6. Procedimientos de acotacin / relajacin. 3.5.1.7. Dominancias. 3.5.1.8. Estrategias de exploracin / seleccin. 3.5.1.9. Clasificacin de los algoritmos branch and bound para problemas de permutacin. 3.5.2. Branch and search. 3.5.3. Branch and relax. 3.5.4. Branch and reduce. 3.5.5. Branch and prune. 3.5.6. Depth-first I Breadth-first I Best-first I... branch and bound. 3.5.7. Branch and bound con estrategia primero el de mejor cota local (locally best bound rule). 3.5.8. Branch and cut. 3.5.9. Branch and price. 3.5.10. Branch and cut and price. 3.6. Procedimientos de bsqueda usualmente descritos en el rea de la inteligencia artificial. 3.6.1. Backtracking dirigido por la dependencia (dependency directed backtracking o DDB). 3.6.2. Profundizacin iterativa (iterative deepening o ID). 3.6.3. Profundizacin iterativa primero en profundidad (depth first iterative deepening o DFID). 3.6.4. Profundizacin iterativa primero el de menor coste (uniformcost iterative deepening).
ndice
Hi
3.6.5. Bsqueda recursiva primero el mejor (recursive best-first search o RBFS). 3.6.6. Ensanchamiento iterativo (iterative broadening). 3.6.7. Algoritmo Z y Z*. 3.6.8. Algoritmo A y A*. 3.6.9. Profundizacin iterativa A* (iterative deepening A* o IDA*). 3.6.10. Profundizacin iterativa A* con control de las reexpansiones (iterative deepening with controlled reexpansion o IDA*_CR). 3.6.11. Algoritmo MREC. 3.6.12. Algoritmo MA*. 3.6.13. Algoritmos de potencia heurstica. 3.6.14. Algoritmo A* ponderado (weighted-A * o WA*). 3.6.15. Algoritmo IDA* ponderado (weighed-IDA* o WIDA*). 3.6.16. Algoritmo B y B'. 3.6.17. Bsqueda en profundidad-m (depth-m search). 3.6.18. Bsqueda en anchura limitada (breadth-limited search o BUS). 3.6.19. Procedimientos de bsqueda harried method. 3.7. Procedimientos de bsqueda hbridos. 3.7.1. Algoritmo a pila. 3.7.2. Estrategias hbridas como combinacin de las estrategias hill climbing (HC), backtracking (BT) y best first (BF). 3.7.3. Procedimientos de branch and bound en programacin dinmica discreta o programacin dinmica discreta en procedimientos de branch and bound. 3.7.4. Programacin dinmica acotada (bounded dynamic programming o BDP). 3.7.5. Procedimientos branch and bound con tcnicas de exploracin de entornos. 3.8. Procedimientos de bsqueda basados en tcnicas de reduccin. 3.8.1. Tcnicas de reduccin procedentes del rea de la investigacin operativa. 3.8.2. El problema de satisfaccin de restricciones: tcnicas de reduccin y procedimientos enumerativos para su resolucin. 3.8.2.1. Algoritmos sistemticos de bsqueda. 3.8.2.2. Tcnicas de consistencia y de propagacin local. 3.8.2.3. Propagacin de restricciones. 3.8.2.4. Resolucin de los problemas de optimizacin. 3.8.2.5. Programacin lgica de restricciones (Constraint Logic Programming o CLP).
120 122 124 125 129 131 133 134 134 136 137 137 141
142 142 143 144
144
146 150 153 153 . 155 168 171 173 184 190 191
ndice
iv
3.9. Procedimientos heursticos. 3.9.1. Procedimientos basados en branch and bound. 3.9.2. Procedimientos basados en A*. 3.9.3. Procedimientos basados en programacin dinmica: programacin dinmica restringida (restricted dynamic programming). 3.9.4. Otros procedimientos. 3.9.4.1. Estrategias de escalada (hill climbing y steepest ascent). 3.9.4.2. Bsqueda en haz de amplitud n (beam search). 3.9.4.3. Fix and relax (F&R). 3.9.4.4. Procedimientos heursticos de mejora. 3.9.4.5. Procedimientos heursticos en inteligencia artificial. 4. PROCEDIMIENTOS DE EXPLORACIN EN PARALELO. 4.1. Paralelismo. 4.2. Paralelismo en problemas de optimizacin combinatoria. 4.3. Libreras branch and bound en paralelo. 5. PROCEDIMIENTOS GENERALIZADOS DE EXPLORACIN. 5.1. Corominas & Companys (1977). 5.2. Kumar & Kanal (1983a). 5.3. Kumar & Kanal (1983b). 5.4. Nau et al. (1984). 5.5. Ibaraki( 1988). 5.6. Helman (1989). 5.7. Correa (1995). 6. ANLISIS DEL PRELIMINARES. ESTADO DEL ARTE Y CONCLUSIONES
205 205 206 208 209 212 213 215 215 221 232 235 236 238 238 242 244 248 249
253
7. BRANCH AND WIN: METALGORITMO DE RESOLUCIN DE PROBLEMAS DE OPTIMIZACIN COMBINATORIA MEDIANTE LA EXPLORACIN DE RBOLES OR. 7.1. Introduccin. 7.2. Definiciones previas. 7.2.1. Problema a resolver. Objetivo. 7.2.2. Vrtice. 7.2.3. Vrtice vaco y vrtice terminal. 7.2.4. Procedimiento de separacin. 7.2.5. Vrtice sucesor o precedente y vrtice descendiente o antecesor.
ndice
7.2.6. Vrtice separado y totalmente separado. 7.2.7. Procedimiento de acotacin. 7.2.8. Procedimiento de reduccin. 7.2.9. Procedimiento de resolucin heurstico. 7.2.10. Procedimiento de examen, 7.2.11. Procedimiento de evaluacin. 7.2.12. Relaciones de dominancia. 7.2.13. Propiedades de la solucin ptima. 7.2.14. Procedimiento de exploracin de entornos. 7.2.15. Estados de un vrtice. 7.3. Formalizacin del metalgoritmo branch and win. 7.3.1. Definiciones. 7.3.2. Formalizacin de branch and win. 7.3.3. Subrutinas. 7.3.3.1. Subrutina SELECCIONAR_DE_L ( ). 7.3.3.2. Subrutina EXAMINARJTERMINAL ( ). 7.3.3.3. Subrutina EXPLORAR_ENTORNO ( ). 7.3.3.4. Subrutina SELECCIONAR_DE_FAMILIA ( ). 7.3.3.5. Subrutina EXAMINAR_GENERAL ( ). 7.3.3.6. Subrutina NUEVO_SUCESOR ( ). 7.3.3.7. Subrutina GENERAR ( ). 7.4. Detalle de los procedimientos y caractersticas de branch and win. 7.4.1. Inicializacin de branch and win. 7.4.2. Procedimiento de separacin. 7.4.3. Procedimiento de examen. 7.4.4. Procedimiento de seleccin del prximo vrtice a tratar. 7.4.5. Propiedades que debe cumplir la solucin ptima. 7.4.6. Relaciones de dominancia.
258 258 259 260 261 261 261 261 262 262 263 264 264 265 266 266 267 267 268 268 269 269 270 270 272 277 280 281
283
283 283 290
293 294
ndice
vi
9. APLICACIN DE BRANCH AND WIN EN PROBLEMAS DE OPTIMIZACIN COMBINATORIA. RESULTADOS Y ANLISIS. 9.1. Introduccin. 9.2. El problema de flow-shop tipo P. 9.2.1. El problema de taller mecnico flow-shop tipo P. 9.2.2. Estrategias ensayadas en el problema flow-shop tipo P. 9.2.2.1. Condiciones de partida. 9.2.2.2. Calidad de la solucin preferible inicial. 9.2.2.3. Optimizacin local en vrtices terminales no vacos. 9.2.2.4. Funcin de evaluacin y seleccin dinmica. 9.2.2.5. Solucin heurstica en los vrtices, con o sin optimizacin local. 9.3. El problema de cubrimiento. 9.3.1. Introduccin al problema de cubrimiento. 9.3.2. Estrategias ensayadas en el problema de cubrimiento. 9.3.2.1. Condiciones de partida. 9.3.2.2. Estrategias ensayadas. 10. CONCLUSIONES FINALES Y POSIBLES EXTENSIONES. 11. REFERENCIAS BIBLIOGRFICAS.
297 297 297 298 299 300 300 303 304 307 309 309 312 313 314 319 323
1. INTRODUCCIN. JUSTIFICACIN. OBJETIVOS. ALCANCE. Actualmente, aunque existen procedimientos especficos para resolver algunos problemas concretos de optimizacin combinatoria, la mayora se deben solucionar con tcnicas generales de exploracin del espacio de soluciones, y ms concretamente mediante procedimientos de exploracin enumerativos en rboles y grafos de bsqueda. El objetivo de esta tesis consiste en formalizar el escenario, confuso y disperso, que en estos momentos engloba a dichos procedimientos: se realiza una amplia recopilacin, estudio y anlisis de los procedimientos y estrategias de resolucin de problemas de optimizacin combinatoria existentes, y se propone una formalizacin general de un metalgoritmo de exploracin de grafos que engloba a dichos procedimientos, y que, adems, incorpora la posibilidad de utilizacin de nuevas herramientas que se estn desarrollando en el campo de la inteligencia artificial (tcnicas de consistencia y de propagacin local de restricciones) y de la ingeniera informtica (paralelismo).
1.1. Introduccin y justificacin: marco general de los problemas de optimizacin combinatoria. A continuacin se realiza una breve introduccin a los problemas de optimizacin combinatoria, para exponer de manera informal cul es el problema que se presenta y justificar la razn de ser de esta tesis. Concretamente, en el apartado 1.1.1. se describe un conocido problema industrial, que resulta ser un problema de optimizacin combinatoria, y un procedimiento de resolucin por enumeracin de soluciones factibles; a travs de este ejemplo, se pretende mostrar el enorme nmero de soluciones que se pueden presentar en un problema de optimizacin combinatoria y varios conceptos que aparecen frecuentemente en los procedimientos enumerativos que se utilizan para su resolucin. En el apartado 1.1.2. se presentan diferentes procedimientos enumerativos de resolucin de problemas de optimizacin combinatoria. Finalmente, en el apartado 1.1.3. se introducen las controvertidas y confusas relaciones que existen entre estos procedimientos. 1.1.1. Problemas de optimizacin combinatoria. En el momento de plantear el diseo de un sistema productivo, la distribucin de la planta es una decisin importante; en general, se puede pensar en dos tipos posibles de diseo: el diseo por proceso (que lleva a una distribucin por secciones) y el diseo por producto (que conduce al concepto de lnea de produccin o montaje). En un diseo orientado a lnea de montaje, una unidad de producto pasa por el puesto de cada operario (estacin de trabajo) quien ejecuta las tareas que se le han asignado, y
transcurrido un tiempo prefijado (tiempo de ciclo) un transportador la lleva a la estacin siguiente; por tanto, en cada estacin se hace el mismo trabajo una y otra vez. Cada operario puede realizar ms de una tarea, aunque cada tarea se asigna a un nico operario. El problema consiste en asignar el conjunto de tareas a realizar entre las diferentes estaciones de trabajo. Habitualmente, la asignacin de tareas debe realizarse atendiendo a una serie de premisas: existen relaciones de precedencias entre tareas, pueden existir estaciones en paralelo, puede ser que las estaciones de trabajo no sean iguales, que existan tareas incompatibles entre s o forzadas a realizarse en la misma estacin, etc. A continuacin se muestra mediante un ejemplo, en qu podra consistir el proceso de resolucin de este tipo de problemas. Sea un problema de diseo de lneas de produccin de 10 tareas, cuyas duraciones, tareas precedentes inmediatas y grafo de precedencias, se describen en la tabla y grafo siguientes: Tarea A B C D E F G H I J Duracin Precedentes 5 10 A 5 A 2 B,C D 7 5 D 10 F 2 E 5 G,H 7 I
Tabla de datos y grafo, de un ejemplar del problema de diseo de lneas, de Mize et al. (1973).
Adems, supngase que se requiere un tiempo de ciclo de 10 unidades. El proceso de asignacin de las tareas a las estaciones puede resumirse como una secuencia de decisiones entre un conjunto de posibilidades: * a la primera estacin se puede asignar la tarea A y ninguna ms por relaciones de precedencia, lo que implica: Estacin Tareas Tiempo * carga Tiempo disponible Estacin cerrada?
1 2
No
* la siguiente tarea que se puede asignar es la B (utilizando una nueva estacin de trabajo) o la C (en la primera estacin o utilizando una nueva): , Estacin Tareas.^
1 2 3
A B
Estacin
< N'
y<-
Tareas .
y
A,C
Estacin cerrada? S
2
Estacin "Tareas Tiempo carga Tiempo disponible Estacin cerrada?
1 2 3
A C
5 5
5 5
S No
* supngase que se selecciona la primera posibilidad, entonces nicamente se puede asignar la tarea C utilizando una nueva estacin de trabajo: Estacin Tareas
--~ -K*
1 2 3 4
A B C
Tiempo carga 5 10 5
Tiempo disponible
Estacin cerrada?
5 0 5
S S No
* a partir de esta situacin slo se puede asignar la tarea D, pero se puede decidir si a la estacin 3 o a la 4; de forma similar se adoptaran el resto de decisiones. Como se puede comprobar, en cada proceso de decisin se selecciona una asignacin factible entre las de un conjunto finito, que viene determinado por la secuencia de asignaciones anteriores. As, si en vez de haber elegido la primera posibilidad en el segundo turno de decisin, se hubiera seleccionado cualquiera de las otras dos, la solucin del problema podra haber sido totalmente diferente; aunque tal vez no, ya que las dos asignaciones parciales siguientes conducen a la misma situacin: son equivalentes.
Estacin
< " "
Tareas
A,C B D,E F,H
1 2 3 4 5
Tiempo carga 10 10 9 7
Tiempo disponible 0 0 1 3
Estacin cerrada? S S S No
Estacin
5'
Tareas
v
t
>
2 3 4 5
Tiempo carga 10 10 9 7
Estacin cerrada? S S S No
Cada una de las diferentes asignaciones factibles que se pueden realizar constituyen una solucin del problema de lneas de montaje planteado. Se dice que un problema con un conjunto de soluciones finito o infinito pero enumerable (imagnese un circuito, en un problema de buscar un camino entre dos vrtices de un grafo), es un problema combinatorio. Usualmente, la asignacin de las tareas a las estaciones de trabajo se debe realizar de forma que partiendo de un nmero de estaciones de trabajo conocido, el tiempo ciclo sea el menor posible, o que partiendo de una tasa de produccin (y por tanto de un tiempo ciclo mximo), el nmero de estaciones de trabajo necesarias sea mnimo. Se dice que un problema combinatorio para el que se busca el valor ptimo (mnimo o mximo) de una funcin objetivo sobre la regin de soluciones factibles, es un problema de optimizacin combinatoria. Un concepto que aparece frecuentemente en los problemas de optimizacin combinatoria es el de cota, que se corresponde con un valor tal que no es posible encontrar ninguna solucin factible con un valor mejor de la funcin objetivo. Volviendo al ejemplo anterior, supngase que se requiere un tiempo ciclo de 10 unidades y que se desea minimizar el nmero total de estaciones de trabajo. El tiempo total necesario para realizar una unidad de producto suma 58 unidades de tiempo, por tanto, la cota (en este caso inferior) del nmero mnimo de estaciones es 6 ( [58/10]"1" ); de todas formas, podra no existir ninguna solucin con tan slo 6 estaciones de trabajo.
El problema de lneas de produccin o montaje es un problema de optimizacin combinatoria, pero existen muchos otros problemas industriales que tambin lo son: diseo de rutas de recogida de personas, basuras, etc., gestin de proyectos con recursos limitados, problemas de carga de camiones y contenedores, diseo de rutas de transporte y distribucin, diseo de redes elctricas y de telecomunicaciones, localizacin de servicios e instalaciones, secuenciacin de diferentes modelos de coches en las lneas de montaje, corte de bobinas para la fabricacin de neumticos, etc. 1.1.2. Procedimientos de resolucin enumerativos. Como se ha comentado, cualquier asignacin factible de las tareas a las estaciones constituye una solucin del problema de lneas de montaje. En un problema de optimizacin combinatoria el nmero de soluciones factibles puede llegar a ser enormemente elevado, y, a pesar de la gran velocidad de clculo de los ordenadores actuales, no se debe caer en el error de intentar generar y evaluar todas las soluciones y seleccionar la mejor. Sin tener en cuenta las restricciones impuestas por las relaciones de precedencia e incompatibilidades, en una lnea formada por n tareas existen n! diferentes rdenes posibles de asignacin de stas: para tan slo 20 tareas existen 2.43 E+18 posibles asignaciones. Usualmente, los requisitos tecnolgicos de precedencias e incompatibilidades reducen considerablemente el nmero de asignaciones factibles; pero incluso as, la enumeracin y evaluacin de todas las soluciones excede a la capacidad de los ordenadores. Si existen r precedencias, para analizar todas las posibles soluciones se deben generar aproximadamente n! / 2r secuencias factibles (Coves 1994), adems de un conjunto de soluciones que no son factibles y, por tanto, una vez determinada su infactibilidad no son estudiadas: para 20 tareas y 20 restricciones existen aproximadamente 2.32 E+12 asignaciones factibles. El hecho de que un reducido nmero de elementos genere un elevado nmero de soluciones es conocido con el trmino explosin combinatoria. En la segunda etapa del proceso de resolucin del ejemplar anterior, se ha seleccionado la primera opcin a falta de algn criterio. Si el objetivo es utilizar el nmero mnimo de estaciones, parece ms lgico seleccionar la segunda posibilidad descartndose, aunque sea temporalmente, las otras dos. Para ello se puede asociar una funcin de evaluacin a cada opcin, que descarte las poco prometedoras y se concentre en las que parece que conducen a situaciones consideradas mejores. Un ejemplo de funcin de evaluacin en el problema de lneas de montaje es e = n + t / TC, donde n es el nmero de estaciones ya utilizadas, t es el tiempo ocupado de la estacin que est siendo completada y TC es el tiempo de ciclo; en este caso, se trata de seleccionar la opcin que presenta el menor valor de dicha funcin de evaluacin.
La representacin ms clara de la evolucin del proceso de resolucin de los problemas de optimizacin combinatoria, y sobre todo para el uso de este tipo de funciones, es mediante un rbol o grafo de bsqueda. A continuacin se recogen, aunque con ciertos matices, las definiciones que Scholl (1986) y Brunat (1996) realizan sobre una serie de trminos relacionados con dicha forma de representacin; stas constituyen la terminologa bsica que se utiliza en esta tesis: * Grafo: conjunto de elementos que se denominan vrtices y una lista de aristas que unen parejas de dichos vrtices. * Grafo simplemente conexo: grafo en el que existe una cadena (secuencia de aristas) entre cualquier pareja de vrtices. * rbol: grafo conexo acclico. * Vrtice hijo: vrtice sucesor (descendiente inmediato) de otro. * Vrtice padre: vrtice precedente (ascendente inmediato) de otro u otros. * Vrtices hermanos: vrtices hijos del mismo vrtice padre. * Semigrado exterior de un vrtice: nmero de sus vrtices hijos. * Semigrado interior de un vrtice: nmero de sus vrtices padres. * Vrtice no terminal: vrtice de semigrado exterior no nulo. * Vrtice terminal u hoja: vrtice de semigrado exterior nulo. * Anchura de un rbol: nmero mximo de vrtices en un mismo nivel. * Profundidad de un rbol: nivel mximo de los vrtices del rbol. * Arborescencia: grafo simplemente conexo con un nico vrtice con semigrado interior nulo (denominado vrtice raz) y donde todos los dems tienen semigrado interior igual auno. * Arborescencia binaria: arborescencia en la que el semigrado exterior de todos los vrtice es, como mximo, igual a dos.
* Nivel (profundidad) de un vrtice: nmero de vrtices del camino que va de la raz hasta ese vrtice. Aunque en ciertas terminologas se distingue claramente entre rbol y arborescencia, existen otras en las que nicamente se utiliza el trmino rbol. En este texto se utilizan indistintamente los trminos rbol y arborescencia, aunque siempre en referencia a un grafo orientado. El rbol de bsqueda asociado al ejemplar del problema de lneas de montaje anterior es el que se muestra en el grafo siguiente, donde a cada arco se asocia la asignacin tareaestacin realizada, y en el interior de cada vrtice se indica el valor de la funcin de evaluacin e = n + t / TC; para dirigir la exploracin se utiliza el criterio de seleccionar el vrtice de cada etapa, de menor valor de e:
Los procedimientos de resolucin de problemas de optimizacin combinatoria que se basan en explorar el rbol o grafo con el que se puede representar el espacio de estados del problema, se denominan procedimientos de resolucin enumerativos. La idea principal de este tipo de procedimientos consiste en partir (ramificar) sucesivamente el espacio de soluciones posibles en subconjuntos ms pequeos y resolver el problema sobre cada subconjunto. En el rbol de enumeracin, los problemas resultantes son llamados subproblemas o vrtices. Si fuera posible construir todo el rbol, se podra garantizar la optimalidad de la solucin obtenida, pero como se ha mostrado, es inviable para problemas de dimensiones interesantes. Para reducir el nmero de subproblemas a resolver, se calculan cotas solucionando problemas relajados de los definidos en los vrtices; si la cota de la solucin de un subproblema es peor o igual que la mejor solucin disponible, el subproblema (la rama del rbol) es eliminado, es podado. Como ya se ha comentado, la representacin ms clara de la evolucin del proceso de resolucin de los problemas de optimizacin combinatoria es mediante rboles o grafos
de bsqueda. Ambas representaciones se pueden clasificar atendiendo a cmo el procedimiento de particin (ramificacin) divide el espacio de soluciones: * rboles y grafos OR: aqullos en los que el proceso de ramificacin divide el espacio de soluciones en subconjuntos, de forma que la solucin del problema en cualquiera de los subconjuntos proporciona una solucin del problema original. * rboles y grafos AND/OR: aqullos en los que el proceso de ramificacin divide el espacio de soluciones en subconjuntos, de forma que la solucin del problema original requiere la resolucin de los subproblemas de dos o ms subconjuntos y la combinacin (suma, resta, etc.) de dichas soluciones. A modo de ejemplo, sea un problema de cubrimiento que consiste en seleccionar el nmero mnimo de puestos de servicios necesarios para cubrir una serie de zonas, a partir de la matriz que indica qu zonas cubre cada puesto de servicio: Servicio! Servicio! Servicios Servito4 Servicios Servicioo Zonal Zona2 Zona3 Zona4 ;Zona5 Zona6
X X
X X X X X X X X
Matriz de datos de un ejemplar del problema de cubrimiento.
El espacio de estados del problema se puede representar mediante un rbol OR, en el que la ramificacin se basa en seleccionar o no, un puesto de servicio. De esta manera se puede obtener una solucin del problema, resolviendo de forma factible el subproblema asociado a cualquiera de los vrtices del rbol.
Por otro lado, este mismo ejemplar tambin admite una representacin mediante un rbol AND/OR: se divide la zona a cubrir en tres subzonas totalmente independientes entre s (zonas Zl y 72, zonas Z3, Z4 y Z5, y zona Z6), se resuelve un subproblema en cada una de ellas (mediante una representacin en rbol OR), y se combinan las soluciones obtenidas para obtener la solucin del problema original. Las ramas AND se representan unindolas mediante un semicrculo, como se muestra en la siguiente figura.
Una vez introducido el funcionamiento general de los procedimientos de resolucin enumerativos, a continuacin se exponen brevemente unos conjuntos de tcnicas de este tipo, que son estudiadas y sintetizadas posteriormente en el presente trabajo. 1.1.2.1. Procedimientos basados en la "fuerza bruta". Los procedimientos cuya herramienta de exploracin principal consiste en el uso de la "fuerza bruta", son tcnicas enumerativas de bsqueda en las que el orden en el que se explora para encontrar la solucin slo depende de la posicin de los vrtices en el rbol de bsqueda. Esta clase de procedimientos son considerados impracticables para problemas no triviales (Barr & Feigenbaum 1981), al explorar intilmente una gran regin del espacio de soluciones factibles y producirse, como ocurre en el problema de lneas de montaje, la temida explosin combinatoria. Las diferentes tcnicas de este tipo existentes difieren en el orden en el que se exploran los vrtices, y entre stas cabe destacar la bsqueda en profundidad (depth first search), la bsqueda en anchura (breadth first search), la bsqueda primero el de menor coste (uniform cost search o cheapest first strategy), la bsqueda primero el mejor (best first search), etc.
1.1.2.2. Procedimientos que utilizan "bsqueda heurstica". Los procedimientos enumerativos que incorporan "bsqueda heurstica" son aqullos en los que el orden en el que se explora para encontrar la solucin est guiado mediante un indicador; de esta forma, se selecciona el siguiente vrtice a explorar basndose en informacin heurstica que se dispone de cada uno de los vrtices candidatos. Este tipo de procedimientos son los que habitualmente se utilizan para resolver problemas de dimensiones industriales. 1.1.2.3. Programacin dinmica. Como ya se ha comentado en el problema de lneas de montaje, a partir de varios vrtices diferentes de un nivel se puede alcanzar un mismo vrtice del nivel siguiente. La idea principal que se pone en prctica en los procedimientos basados en programacin dinmica, consiste en explorar el rbol de bsqueda eliminando los vrtices redundantes y conservando nicamente el mejor de todos ellos: agrupando los vrtices equivalentes. 1.1.2.4. Branch and bound. El trmino branch and bound se refiere a una familia de procedimientos de resolucin enumerativos, cuya principal caracterstica consiste en que dedican un gran esfuerzo a reducir el nmero de vrtices a explorar, calculando una cota del valor de una funcin objetivo asociada a los subproblemas: si la cota de un vrtice es peor o igual que el valor de una solucin factible (o en particular, peor que la mejor solucin conocida, que se suele denominar preferible), el vrtice es eliminado. Como comentan Gass & Harris (1996), las tcnicas branch and bound son frecuentemente utilizadas para solucionar problemas de programacin entera. 1.1.2.5. Otros procedimientos guiados y del rea de la inteligencia artificial. Adems de las tcnicas descritas en los apartados anteriores, existen algunos otros procedimientos de resolucin tambin desarrollados en el rea de la investigacin operativa: branch and price, branch and cut, branch and reduce, bounded dynamic programming, etc. En el rea de la inteligencia artificial tambin se han diseado, o al menos formalizado, muchos otros procedimientos de exploracin enumerativos que utilizan diversas tcnicas para dirigir la bsqueda, hacerla lo ms breve posible e incluso convertirla en un procedimiento heurstico. Entre stos cabe destacar sobre todo el A*, que consiste en
**
un procedimiento semejante al branch and bound pero con una forma especifica de seleccin del prximo vrtice a explorar. Otros procedimientos desarrollados en el rea de la inteligencia artificial son el procedimiento A, el IDA*, el WA*, el WIDA*. el depth first iterative deepening, el depth-m search, etc. 1.1.3. Relaciones entre los diferentes procedimientos de resolucin. La mayora de procedimientos de bsqueda enumerativos han sido utilizados tanto en el rea de la investigacin operativa como en el de la inteligencia artificial. En numerosas ocasiones, algunos de stos han sido bautizados con diferentes nombres an tratndose de la misma tcnica (as por ejemplo, el algoritmo de bsqueda en profundidad o bsqueda primero en profundidad ha sido denominado hasta de otras seis formas diferentes: linear search, single branch search, estrategia de bsqueda LIFO, bsqueda hacia el fondo, bsqueda vertical y estrategia en profundidad), y algunos otros presentan conexiones tan profundas entre ellos que podran considerarse redundantes: en Barr & Feigenbaum (1981) y Kumar & Kanal (1983b), se comenta que el branch and bound (B&B), la programacin dinmica (PD) y el A* son muy parecidos, aunque el B&B y la PD se han utilizado en investigacin operativa y el A* en inteligencia artificial. Adems, las relaciones entre ellos son controvertidas. Por ejemplo, Nilsson (1980), Mompn et al. (1987), Sturai & Tsujii (1987) y Companys (1989a) definen el algoritmo A como un algoritmo A* que no asegura la optimalidad de la solucin, mientras que muchos otros autores (Barr & Feigenbaum 1981, Korf 1990, Raphael 1990, Corts et al. 1993, Ginsberg 1993 y Rich & Knight 1994) consideran que slo existe el algoritmo A*, y que asegura o no la optimalidad de la solucin en funcin del cumplimiento de la propiedad de admisibilidad. Adems, en este caso tambin existen definiciones particulares del A*: Corts et al. (1993), adems de considerar los costes de los caminos en nmero de etapas, asumen la agrupacin de estados equivalentes y la conservacin nicamente del mejor camino hasta stos (como tambin hacen Rich & Knight 1994); por su parte, Pearl (1984) considera el algoritmo A* como una especializacin del Z* (tcnica especial de bsqueda primero el mejor que obtiene una solucin ptima, descrita por l mismo). Como comentan diversos autores (Pearl 1984, Mompn et al. 1987, Companys 1989a, Corts et al. 1993 y Greenberg 1996 entre otros), si no se dispone de informacin heurstica y el coste asociado a un vrtice se define como su profundidad, el algoritmo A o el A* correspondiente equivale a la exploracin en anchura. Si el coste asociado se define como menos la profundidad del vrtice, el algoritmo A* equivale a la bsqueda en profundidad (Pearl 1984). Para Nilsson (1971), Barr & Feigenbaum (1981) y Pearl (1984) si no se dispone de informacin heurstica, el algoritmo A* es el procedimiento de bsqueda primero el de menor coste; por su parte, Rich & Knight (1994) especifican un mayor nmero de posibilidades. Adems, Korf (1990) considera que el algoritmo A* es un procedimiento
de bsqueda primero el mejor. Segn Greenberg (1996), otro caso particular del A* en investigacin operativa es el branch and bound para programacin entera, en el que la funcin de evaluacin toma el valor objetivo de la relajacin lineal en el vrtice (sin comentar la caracterstica principal del B&B: el podado mediante cotas). Barr & Feigenbaum (1981) denominan ordered state space search a la bsqueda primero el mejor (best first search) y especifican que el breadth first, el uniform cost y el depth first son casos especiales de sta; por otro lado, estos mismos autores, Nilsson (1971) y Pearl (1984) definen especficamente la bsqueda primero el de menor coste (uniform cost search o cheapest first strategy), mientras que la mayora la consideran un caso especial de la bsqueda primero el mejor; por su parte, Pearl (1984) diferencia entre si slo se busca una solucin factible (estrategia de bsqueda primero el mejor) o si se busca una solucin ptima (algoritmo que Pearl denomina bsqueda primero el mejor*); Mompn et al. (1993) definen el procedimiento de bsqueda primero los mejores (best few), como una nueva tcnica que consiste en explorar un conjunto de alternativas en paralelo; adems, se han definido tcnicas que alternan bsquedas en profundidad con bsquedas primero el mejor (Ibaraki 1988). Corts et al. (1993) llaman ptimo por niveles a la bsqueda primero el mejor, B&B a lo que tal vez se podra denominar ramificacin sin acotacin y B&B con subestimacin a lo que la mayora conoce como B&B; por otro lado, consideran que el A* es el procedimiento ms general. Segn citan Kumar & Kanal (1983b), mientras que Pohl argumenta que los procedimientos de bsqueda heurstica son muy diferentes de los branch and bound, Hall e Ibaraki dicen que muchas tcnicas de bsqueda heurstica en representaciones en espacio de estados, son esencialmente B&B. Segn este mismo trabajo, Martelli & Montanari afirman que su algoritmo de bsqueda heurstica es diferente del B&B, ya que "(B&B) technique does not recognize the existence of identical subproblems"; por otro lado, Kumar & Kanal (1983b) comentan que el B&B de Ibaraki s reconoce la existencia de subproblemas idnticos. Tambin exponen que mientras Nilsson describe el procedimiento A*, considera que la programacin dinmica (PD) es esencialmente un procedimiento de bsqueda en anchura; por otro lado, dicen que Morin & Marsten permiten una computacin de PD con cotas, y para ellos esto indica que Morin & Marsten no consideran que la PD sea necesariamente una bsqueda en anchura. Las relaciones entre B&B y PD tambin han sido controvertidas. Ibaraki (1988) discute cmo un conjunto de procedimientos de PD pueden ser vistos en una estructura de B&B, aunque tambin comenta que los B&B pueden verse como un procedimiento de PD al que se le adiciona un test de acotado. Marsten & Morin (1978) y Dyer et al. (1995) describen un algoritmo hbrido entre la PD y el B&B, y lo consideran como un procedimiento de PD ms un test de acotado, o como un B&B ms una poda por
"
dominancias. Por su parte, Bautista et al. (1992, 1994) exponen un nuevo procedimiento hbrido, la programacin dinmica acotada, que tambin aprovecha las caractersticas de ambas tcnicas. Segn Kumar & Kanal (1983b), el trabajo de Ibaraki parece implicar que, para problemas de optimizacin combinatoria, la PD es un esquema de resolucin de problemas ms general que el B&B, pero en Ibaraki (1988) se describe un B&B muy general que incorpora diversos test de podado: cota, dominancias, infactibilidades, etc. De todas formas, tambin cabe comentar la existencia de algunos autores que parecen tener ms clara la conexin entre algunos de estos procedimientos: "A class of algorithms similar to A* is used in operations research under the name of branch-andbound algorithms", Barr & Feigenbaum (1981), p. 64.
1.2. Objetivos y alcance. El panorama descrito en la introduccin, muestra un escenario de los procedimientos de exploracin enumerativos en rboles y grafos de bsqueda, poco estructurado, disperso e insuficientemente formalizado. Considerando que aunque existen tcnicas especficas para resolver algunos problemas combinatorios concretos, la mayora deben solucionarse con procedimientos generales de exploracin del espacio de soluciones, la dispersin, confusin e incluso duplicidad que se ha dado en los ltimos aos entre los procedimientos desarrollados en el rea de la investigacin operativa y en el de la inteligencia artificial (e incluso entre los diseados en el seno de cada una de ambas disciplinas), dificulta en gran medida la seleccin de un procedimiento para resolver uno de los diferentes problemas de optimizacin combinatoria existentes. Por otro lado, actualmente se estn incorporando nuevos procedimientos (branch & reduce, branch & cut, branch & price, branch and cut and price, etc.), que en el fondo se pueden reducir a esquemas conocidos, as como nuevas tcnicas y herramientas (tcnicas de consistencia y de propagacin local de restricciones, y paralelismo), lo que puede acelerar el desarrollo de nuevos procedimientos, nuevas denominaciones o nuevos hbridos de los ya existentes, complicando todava ms la situacin actual. Partiendo del supuesto de representar el proceso de resolucin de los problemas de optimizacin combinatoria mediante un grafo de estados, los objetivos y aportaciones de esta tesis son los siguientes: Recopilacin, anlisis y crtica de diferentes procedimientos y estrategias de resolucin existentes, as como de las formulaciones generales de dichas tcnicas expuestas en la literatura.
Propuesta, formalizacin y desarrollo de un metalgoritmo de exploracin de grafos que englobe a los diversos procedimientos de bsqueda (branch and bound, programacin dinmica, A*, bsqueda en profundidad, bsqueda en anchura, IDA*, etc.), y que, adems, incorpore la posibilidad de utilizar las nuevas herramientas que se estn desarrollando en el campo de la inteligencia artificial (tcnicas de consistencia y de propagacin local de restricciones) y de la ingeniera informtica (paralelismo). Diseo y proposicin de nuevos procedimientos hbridos, resultado de la combinacin de los ya existentes. A continuacin se describen las principales hiptesis de trabajo bajo las que se desarrolla la presente tesis: Los procedimientos de bsqueda analizados presentan suficientes caractersticas comunes, como para poder desarrollar un metalgoritmo de exploracin de grafos que englobe las diversas tcnicas de exploracin expuestas. La formalizacin de dicho metalgoritmo es el objeto central de la tesis. Los valores de todos los datos de los ejemplares de los problemas son deterministas y estticos: los datos se conocen de partida y no se trabaja con problemas de solucin on-line en un entorno cambiante, como podran ser los juegos y los sistemas autnomos en tiempo real. nicamente se consideran procedimientos unidireccionales y no se abordan algoritmos bidireccionales como el perimeter search con A* (PS*) y con IDA* (IDPS*) (Dillenburg & Nelson 1994), el depth first iterative deepening (DFD) en bsqueda bidireccional (Korf 1985), el BIDA* (Manzini 1995), etc. Por otro lado, slo se utilizan representaciones del espacio de estados a travs de rboles o grafos OR; no son consideradas las representaciones mediante rboles o grafos AND/OR, ni, por tanto, los procedimientos enumerativos diseados para su resolucin. La adopcin de estas hiptesis de trabajo presenta las siguientes implicaciones. Por un lado no se resuelven problemas combinatorios con datos aleatorios (excepto que se trabaje con valores estimados), ni aqullos que deben resolverse dentro de un entorno dinmico. Y, por otro, tampoco se formalizan los procedimientos bidireccionales ni los basados en representaciones AND/OR (cabe destacar, sin embargo, que en este caso no se restringe de ninguna manera los problemas combinatorios que es posible resolver).
2.1. Definicin. Lawler (1996) define la combinatoria como la rama de la matemtica que trata de ordenar objetos usualmente finitos en nmero y sujetos a varias restricciones. Por otro lado, Gass & Harris (1996) definen la optimizacin como el proceso de bsqueda del mejor valor que puede llegar a ser obtenido (en programacin matemtica, ste es el valor mnimo o mximo de la funcin objetivo sobre la regin de soluciones factibles). Ibaraki (1988) proporciona una definicin formal de optimizacin combinatoria, que tambin es denominada optimizacin discreta, programacin combinatoria o programacin discreta. Ibaraki define un problema de optimizacin como:
P: MIN (MAX) f(x) x e S,
donde X es el espacio de soluciones y S c X es la regin factible dentro del espacio X (en el conocido problema de la mochila, X est formado por los diferentes conjuntos de objetos posibles y S por los conjuntos de objetos cuyo peso total no supera cierto valor). Como se ha descrito, S es el conjunto de soluciones factibles, y, por otro lado, la funcin f: S > R (o a veces N) es la funcin objetivo. Una solucin x e S es ptima, si no existe otra solucin y 6 S tal que f(y) < f(x) si se minimiza o f(y) > f(x) si se maximiza. Un problema de optimizacin es de optimizacin combinatoria, si X y S son combinatorios o discretos, es decir, si son conjuntos de un nmero finito de elementos o de infinitos elementos numerables. Por tanto, se puede decir que un procedimiento de resolucin de problemas de optimizacin combinatoria trata de encontrar una solucin, que optimice (minimizando o maximizando) una funcin objetivo sobre un espacio combinatorio o discreto. La definicin proporcionada por Ibaraki (1988) no es suficientemente general, ya que uno de los problemas de optimizacin combinatoria ms importantes, la programacin lineal mixta, no se ajusta a dicha formulacin debido a que los espacios de soluciones X y S no son numerables. Corominas (1996) propone una definicin de problema de optimizacin combinatoria general, en la que se formaliza que una vez definido el valor
de las variables discretas, se dispone de un procedimiento para resolver ptimamente el resto del problema: [OPT]z = f(x,y) (x, y) e S, donde x representa a un vector de variables discretas, y a un vector de variables continuas, y dada una x' se puede obtener una y' que proporciona la solucin ptima del problema para x'. A veces no se necesita la solucin ptima o se presenta la obligacin de alcanzar el ptimo de forma aproximada (por limitaciones en el tiempo de clculo, etc.); adems, se desea que la diferencia con la solucin ptima no sea muy grande, pero eso s, que est acotada. Corominas & Companys (1977) proponen una nueva definicin que recoge estos aspectos: [-OPT] z = f(x) x e S X, donde: x es una solucin, S es el conjunto de soluciones factibles, K es el conjunto de nmeros totalmente ordenado (reales, enteros,...), f: S K, es una correspondencia que a cada x e S le hace corresponder un nmero. Existe K' totalmente ordenado y existe g, tal que: g: K x K' K (K pueden ser los enteros y K' los reales, de forma que a cada pareja entero-real se le asigna un nmero entero), es de la forma: g(u,T|) > u y adems: V u K, V T e K',
Vu.u'eK, VueK,
*'
es decir, g incrementa el valor de u en T| o en un valor relacionado con T| (g(u,T|) puede ser: u + T|, u (1+T|), lu (l+r|)l, etc.). Una vez definido g, se puede definir S-minimizar como encontrar x* e S tal que f(x*) < g(f(x),8), V x e S; es decir, buscar una solucin que, en el caso de que g(u,T|) = u+T|, est como mucho 5 unidades lejos del ptimo (puede ser no ptima en, como mximo, unidades).
2.2. Ejemplos. Existe una gran cantidad de problemas industriales que son problemas de optimizacin combinatoria: problemas de inversiones, equilibrado o diseo de lneas de produccin o montaje, diseo de rutas de recogida de personas, basuras, etc., gestin de proyectos con recursos limitados, problemas de carga de camiones y contenedores, diseo de rutas de transporte y distribucin, diseo de redes elctricas y de telecomunicaciones, localizacin de servicios e instalaciones, secuenciacin de diferentes modelos de coches en las lneas de montaje, corte de bobinas para la fabricacin de neumticos, programacin de los movimientos de un robot o un puente gra, organizacin de horarios y turnos de trabajo, diseo de un almacn, localizacin de productos en un almacn, etc. Todos estos problemas pueden formalizarse de una forma ms estructurada y abstracta en una serie de problemas de optimizacin combinatoria, algunos de los cuales enumeran y describen Corominas et al. (1984), Ibaraki (1988), Bjorndal et al. (1995), Corominas (1996), Gass & Harris (1996) y Wang & Coleman (1996), aunque existen muchos otros. * Problemas de flujos: dado un grafo orientado, G = (V, A), con un vrtice origen, a, un vrtice destino, co, y con tres nmeros enteros asociados a cada arco (ly, uj, cy) (lmites inferior y superior del flujo y coste unitario), se trata de hallar un flujo compatible de coste mnimo. Existen muchos problemas que son casos particulares de ste: problema del transporte, del transporte con capacidades, de afectacin, de acoplamiento (matching problem), de flujo mximo, del camino mnimo entre un par de vrtices, etc. * Problema del cartero chino (Chinese postman problem: CPP): dado un grafo no orientado, G = (V, E), con unos valores cj asociados a cada arista, se trata de hallar un ciclo de coste mnimo que pase al menos una vez por cada arista. Tambin se puede plantear en un grafo orientado.
* Problema del viajante de comercio (travelling salesperson problem: TSP): dado un grafo completo no orientado, G = (V, E), con unos valores Cy asociados a cada arista, se trata de hallar un ciclo harniltoniano (que pase exactamente una sola vez por cada vrtice) de coste mnimo. Tambin se puede plantear en un grafo orientado. * Problema general de itinerarios (general routing problem: GRP): sea un grafo G = (V, A, E), es decir con arcos y aristas, con valores Cy asociados a cada arco o arista, y sean V V, A' A, E' E; se trata de hallar un itinerario que contenga todos los elementos de V, A' y E', en el que todos los arcos de A' tengan la misma orientacin y con un coste mnimo (este caso es el single vehicle routing problem). * Problema de afectacin generalizado (generalized assignment problem: GAP): dadas m mquinas (i = l, 2,..., m) y n trabajos indivisibles (j = 1,2,..., n), en el sentido de que cada trabajo se debe realizar ntegramente en una sola mquina, se trata de afectar los trabajos a las mquinas teniendo en cuenta que cada mquina tiene un tiempo disponible b, que realizar j en i representa un coste Cy y consume un tiempo ty, y con coste total mnimo. Es decir, encontrar una asignacin de los n trabajos a las m mquinas de mnimo coste, tal que todo trabajo se asigne a una mquina y se respeten sus restricciones de capacidad. El programa lineal binario asociado es el siguiente:
[MIN] Z = l<i<m, l<j<n Cy Xy
ty Xy < bj
Vi
xy=l x y e {0,1}.
Vj
* Problemas de scheduling: problemas en los que se trata de hallar una secuencia de trabajos y a veces sus instantes de inicio y finalizacin (un programa), considerando que dichos trabajos necesitan unos recursos usualmente limitados, y optimizando algn criterio como el tiempo total, el coste total, etc. * Problema de localizacin de plantas: sea un grafo G, orientado o no, en el que los vrtices (o algunos vrtices) representan centros de demanda y los arcos o aristas un sistema de comunicaciones; se trata de localizar uno o diversos puestos que proporcionen servicio a los centros de demanda, optimizando alguna funcin en la que intervienen usualmente las distancias (de todas formas existen problemas como el de cubrimiento, en los que las distancias no participan en la funcin objetivo al estar incluidas en las restricciones).
* Problema de cubrimiento (set-covering problem): problema de programacin entera definido como sigue:
[MIN] z = c x E x > e,
donde los componentes de E son o unos o ceros, los componentes del vector columna e son todos unos, y las variables estn restringidas a ser uno o cero. La idea del problema consiste en encontrar, a mnimo coste, un conjunto de columnas de E, tales que los unos del vector e estn "cubiertos" por al menos uno de los unos de las columnas seleccionadas. Notar que la cobertura mltiple est permitida. * Problema de particin (set-partitioning problem): problema de programacin entera definido como sigue:
[MIN] z = c x E x = e,
donde los componentes de E son o unos o ceros, los componentes del vector columna e son todos unos, y las variables estn restringidas a ser uno o cero. Problema similar al de cubrimiento excepto en que la cobertura mltiple no est permitida. * Problema de empaquetado (set-packing problem): problema de programacin entera definido como sigue:
[MIN] z = c x E x < e,
donde los componentes de E son o unos o ceros, los componentes del vector columna e son todos unos, y las variables estn restringidas a ser uno o cero. La idea del problema consiste en encontrar, a mnimo coste, un conjunto de columnas de E, tales que los unos del vector e estn "cubiertos" por como mximo uno de los unos de las columnas seleccionadas. * Problema de bin-packing: consiste en la determinacin del nmero mnimo de cajas necesarias para empaquetar un conjunto dado de elementos. El problema clsico en una dimensin se define como sigue: dada una caja de capacidad C y una lista de elementos L = (pi, p2, ..., pn), donde p tiene tamao s(p) satisfaciendo O < s(p) < C, determinar el menor nmero entero m tal que existe una particin L = BI u 82 u ... u Bm que
90
satisface s(p) < C, donde p e Bj, l < j < m. El conjunto Bj usualmente se asocia al contenido de una caja de capacidad C. * Coloreado de los vrtices de un grafo: dado un grafo G, se trata de determinar el nmero mnimo de colores necesarios para pintar cada vrtice del grafo de un color, de manera que dos vrtices adyacentes no tengan igual color. * Problema de la mochila (knapsack problem: KP): dados n elementos u objetos de valor Cj > O y peso a > O, y un valor b (lmite de peso total), se trata de hallar un conjunto formado con dichos elementos cuyo peso total no supere b, de valor total mximo:
[MAX] Z = !]<j<n Cj Xj l<j<n 3j Xj < b
Xj e {0,1} o entero no negativo, V j. Este problema ha sido extensamente estudiado por su aplicacin inmediata y porque surge como relajacin de diferentes problemas de programacin entera. * Problema de programacin entera mixta (mixed integer programming problem: MIP): problema de programacin matemtica en el que las restricciones y la funcin objetivo son lineales, pero varias variables estn restringidas a tener valores enteros. Las variables enteras pueden ser binarias o tomar cualquier valor entero. Estos problemas tienen gran importancia dentro de los problemas de optimizacin combinatoria, ya que muchos de stos pueden ser formulados como problemas de programacin entera mixta.
2.3. Complejidad de los problemas de optimizacin combinatoria. Existen algunos problemas de optimizacin combinatoria que disponen de algoritmos eficientes que los resuelven, en cambio otros no; esto es debido a que son de diferente complejidad. La teora de la complejidad se presenta de forma excelente en Garey & Johnson (1979) y en Papadimitriou & S tei glitz (1982). Aqu nicamente se relata una breve introduccin a varios conceptos generales, pero antes de comenzar a exponerlos conviene recordar algunas definiciones previas (Hall 1996): - Problema: descripcin abstracta (o estructura de datos para otros autores) asociada a una pregunta que requiere una respuesta (en el problema TSP y dado un grafo con sus costes asociados, cul es el ciclo hamiltoniano de menor coste?).
- Ejemplar de un problema: un ejemplar de un problema incluye la especificacin exacta de los datos (el grafo contiene 6 vrtices, el arco (1, 2) de coste 8, el (3, 4) de coste 10, etc.); por tanto, un problema puede presentar un nmero infinito de ejemplares. - Algoritmo: un algoritmo para un problema es un conjunto de instrucciones que garantiza encontrar la solucin de cualquier ejemplar en un nmero finito de pasos. - Paso en un algoritmo: en un ordenador consiste en una de las siguientes operaciones: suma, resta, multiplicacin, divisin en precisin finita o comparacin de dos nmeros; la valoracin del nmero de pasos en un algoritmo se expresa como una funcin del tamao del ejemplar correspondiente. - Tamao de un ejemplar: es el nmero de bits necesarios para codificarlo; para medirlo se requieren las dimensiones del ejemplar (en el TSP, el nmero de vrtices y arcos del grafo), que se denominan dimensiones inherentes, y el nmero mximo de bits necesarios para codificar cualquier dato (los arcos y sus costes). - Notacin de la O grande: sean dos funciones f(t) y g(t) de un parmetro t no negativo, se dice que f(t) = O(g(t)) si existe una constante c > O tal que, para todo t suficientemente grande, f(t) < c g(t); la funcin c g(t) es una cota asinttica superior de f. Papadimitriou & Steiglitz (1982), Nemhauser & Wolsey (1988) y Scholl (1995) proporcionan definiciones equivalentes. Hall (1996) define el termino complejidad computacional, sealando que tiene dos usos que se deben distinguir claramente: a) Por un lado, se refiere a un algoritmo para resolver ejemplares de un problema. Para Papadimitriou & Steiglitz (1982), la forma ms comnmente aceptada de medir la ejecucin de un algoritmo es mediante el tiempo necesario para alcanzar la respuesta final. Este tiempo puede variar en funcin del ordenador utilizado, y para evitarlo, se expresa en trminos del nmero de pasos necesarios para ejecutar el algoritmo en un ordenador hipottico (ordenador que ejecuta instrucciones secuencialmente y como mucho una en cada instante de tiempo), y se asume que cada paso consume una unidad de tiempo independientemente del tamao del ejemplar. Adems, el nmero de pasos que necesita un algoritmo no es el mismo para todos los inputs; as, se consideran todos los inputs del mismo tamao y se define la complejidad del algoritmo en funcin del tamao de la entrada y para el caso peor. b) Por otro lado, se refiere al problema en s mismo. La teora de la complejidad computacional clasifica los problemas de acuerdo a su inherente tratabilidad o intratabilidad (esto es, si son fciles o difciles de resolver); este esquema de
clasificacin incluye las clases P, NP, NP-completo y NP-duro (que posteriormente se definen). El nmero de operaciones de los algoritmos puede ser diferente para ejemplares de un mismo problema y del mismo tamao. Para Ahuja et al. (1989) existen tres procedimientos bsicos para medir la ejecucin de un algoritmo: 1. Anlisis emprico: mide el tiempo de computacin de un algoritmo utilizando una distribucin de ejemplares del problema. El principal objetivo del anlisis emprico consiste en estimar cmo se comporta el algoritmo en la prctica. 2. Anlisis del caso peor: tiende a buscar cotas superiores del nmero de pasos que un algoritmo puede necesitar en cualquier ejemplar de un problema, es, por tanto, la mxima complejidad de un ejemplar de tamao n. Este tipo de anlisis tiende a ser pesimista ya que el caso peor slo se presenta en muy pocos ejemplares. Gass & Harris (1996) proporcionan una definicin similar: para un algoritmo y su problema asociado, consiste en la determinacin de una cota superior del nmero de pasos que el algoritmo puede necesitar para cualquier ejemplar del problema. 3. Anlisis del caso promedio: consiste en estimar el nmero de pasos promedio que necesita un algoritmo, supuesta una distribucin de probabilidad de los ejemplares de un problema. Se diferencia del anlisis emprico en que el anlisis del caso promedio proporciona rigurosas propiedades matemticas de la ejecucin, ms que estimaciones estadsticas; es por tanto la media de la complejidad de todos los ejemplares de tamao n, y, por otro lado, presenta el inconveniente de que usualmente es difcil conocer la distribucin de probabilidad de la complejidad de los ejemplares. En general, los problemas de optimizacin combinatoria se clasifican segn la complejidad computacional del caso peor, ya que como exponen Nemhauser & Wolsey (1988): a) se garantiza absolutamente el tiempo de ejecucin, b) es independiente de la distribucin de probabilidad de los ejemplares, c) y parece ms fcil de medir para analizar. De todas formas, y como argumentan estos mismos autores y Bjorndal et al. (1995), este anlisis no siempre refleja la tratabilidad computacional real: en muchos casos existe una gran diferencia entre la complejidad del caso peor y el tiempo y/o espacio necesario promedio para resolver ejemplares del problema. As, parece imprescindible diferenciar el punto de vista terico y la realidad, ya que, en el entorno organizativo en el que se engloba dentro de un contexto industrial concreto, un algoritmo debera ser considerado
bueno o malo segn la relacin existente entre el tiempo que tarda en resolver el problema planteado y el tiempo disponible. Papadimitriou & Steiglitz (1982), Ibaraki (1988), Kernhuser & Wolsey (1988), Bondy (1995), Scholl (1995), Gass & Harris (1996) y Hall (1996) definen de manera similar los conceptos de algoritmo de tiempo polinomial, exponencial, fuertemente polinomial y pseudopolinomial, aunque Bondy (1995) slo lo hace en referencia a los grafos. Despus de introducir dichos conceptos, y como aclaracin de los mismos, se muestra la exposicin que realizan sobre el tema Ahuja et al. (1989) tomando como referencia un problema en redes. Para discutir si un problema es fcil o difcil, primero se debe precisar dnde est la frontera entre los problemas fciles y los difciles. Comnmente se dice que los problemas fciles, los que se resuelven eficaz y prcticamente, son aquellos que se solucionan con un algoritmo con complejidad del tiempo O(nk), donde n es el tamao del ejemplar (el nmero de bits necesarios para codificarlo) y k es una constante. Dicho algoritmo es de orden polinomial y se llama algoritmo de tiempo polinomial. Por otro lado, los problemas difciles son aquellos para los que no se dispone de un algoritmo acotado polinomialmente en n para su resolucin (por ejemplo: O(nlog(n)), O(kn)). Son los denominados algoritmos de tiempo exponencial y su complejidad est acotada inferiormente por una funcin exponencial en n. De todas maneras, se podra argumentar que un algoritmo O(c nk) es peor que uno O(kn) si las constantes c y k son grandes y n es pequea. Algunos autores como Ibaraki (1988) opinan que, aunque lo anterior es cierto, las definiciones se enfocan a destacar el comportamiento asinttico de un algoritmo O(kn) en funcin de n; sin embargo, Papadimitriou & Steiglitz (1982) exponen que existe una gran controversia sobre este tema que pone en duda la tesis de que tiempo polinomial sea sinnimo de prctico. Aunque la distincin ms importante se presenta entre algoritmos de tiempo polinomial y exponencial, tambin se han definido otras clases de algoritmos. Por un lado se definen los algoritmos de tiempo fuertemente polinomial, como aquellos cuyo tiempo de ejecucin est acotado polinomialmente por una funcin que slo depende de las dimensiones inherentes del problema (en el TSP, el tamao del grafo asociado) y es independiente del tamao de los datos numricos del ejemplar (nmero de bits necesarios para codificarlo). Y por otro lado existen los algoritmos de tiempo pseudopolinomial, que son aquellos que se ejecutan en tiempo polinomial de la dimensin del problema y de las magnitudes de los datos implicados, ms que en logaritmo en base dos de sus magnitudes; tales
algoritmos son tcnicamente funciones exponenciales del tamao de los datos de entrada, y por tanto, no se consideran polinomiales. Como dicen Garey & Johnson (1979), un algoritmo de tiempo pseudopolinomial mostrar comportamiento exponencial, slo cuando se enfrente con ejemplares que contengan nmeros exponencialmente grandes. A continuacin, se transcribe la exposicin que realizan Ahuja et al. (1989) sobre el tema tomando como referencia un problema en redes. Las definiciones siguientes se muestran para aclarar los trminos anteriores, y sobretodo el concepto de algoritmo de tiempo fuertemente polinomial y el de algoritmo de tiempo pseudopolinomial. El tiempo de ejecucin de un algoritmo en redes se acota en funcin de varios parmetros bsicos del problema: el nmero de vrtices (n), el nmero de arcos (m) y las cotas superiores del coste de los coeficientes y de las capacidades de los arcos (C y U, que se asume que toman valores enteros), y se determina contando el nmero de pasos realizados en la ejecucin. Se asume que tanto C como U estn polinomialmente acotados en n para varias constantes k, C = O(nk) y U = O(nk). Esta hiptesis, conocida como la hiptesis de similitud, es muy razonable en la prctica (por ejemplo, si los costes estn restringidos a ser menores que 100 n3, se pueden tener costes de hasta 100.000.000.000 para redes con 1.000 vrtices). Se dice que un algoritmo es de tiempo polinomial, si su tiempo de ejecucin est acotado por una funcin polinomial de la longitud de la entrada (nmero de bits necesarios para representarla), que para un problema de redes es una funcin de orden polinomial de n, m, log2C y log2U (por ejemplo: O((n + m) (logan + log2C + O(n2 m), O(n Iog2n), etc.). Consecuentemente, se dice que un algoritmo de redes es de tiempo polinomial, si su tiempo de ejecucin est acotado por una funcin polinomial de n, m, logaC y Se dice que un algoritmo es de tiempo fuertemente polinomial, si su tiempo de ejecucin est acotado por una funcin polinomial solamente de n y m, pero no de logaC o logaU. El inters de los algoritmos fuertemente polinomiales es principalmente terico; en particular, si se evoca a la hiptesis de similitud, todo algoritmo de tiempo polinomial es de tiempo fuertemente polinomial, ya que logaC ~ O(log2 n) y logaU 0(log2 n). Se dice que un algoritmo es de tiempo exponencial, si su tiempo de ejecucin crece como una funcin que no puede ser polinomialmente acotada, por ejemplo O(n C), O(2n), O(n!) y O(nlogn). (Obsrvese que n C no puede estar acotado por una funcin polinomial de n y de
Se dice que un algoritmo es de tiempo pseudopolinomial, si su tiempo de ejecucin est polinomialmente acotado por n, m, C y U -por ejemplo: O(m + n C) y O(m C)-. Los algoritmos pseudopolinomiales constituyen la subclase ms importantes dentro de los algoritmos exponenciales. Para los problemas que satisfacen la hiptesis de similitud, los algoritmos de tiempo pseudopolinomial son algoritmos de tiempo polinomial, pero los algoritmos no son atractivos si C y U son de grado polinomial grande en n. Para Ahuja et al. (1989), existen dos importantes razones para preferir los algoritmos polinomiales a los exponenciales: - cualquier algoritmo polinomial es asintticamente superior a cualquier algoritmo exponencial, incluso en casos extremos: n1'000 es menor que n0ll'log n si n es 1 n fwwi suficientemente grande (en este ejemplo n debe ser mayor que 2 , pero como se expone a continuacin estos casos no son frecuentes), - muchas experiencias prcticas han mostrado que, como regla, los algoritmos de tiempo polinomial se ejecutan mejor que los algoritmos de tiempo exponencial; adems, en la prctica los algoritmos polinomiales son de grado pequeo. Probar que un problema es fcil, es simple: es suficiente encontrar un algoritmo con complejidad de tiempo polinomial que lo resuelva; sin embargo para probar que un problema es difcil, no es suficiente con decir que no se ha encontrado ningn algoritmo con complejidad de tiempo polinomial, se debera probar que no es posible concebir ningn algoritmo que lo resuelva en tiempo polinomial. Segn Bondy (1995), actualmente existen muchos problemas para los que todava no se ha encontrado un algoritmo de tiempo polinomial, y podran no existir. Como comentan diferentes autores (Papadimitriou & Steiglitz 1982, Ibaraki 1988, Kernhuser & Wolsey 1989, Bondy 1995, Scholl 1995, Hall 1996, etc.), un problema de optimizacin combinatoria tiene un problema de reconocimiento asociado (tambin llamado de decisin o factibilidad), que es un problema cuya pregunta a solucionar requiere la respuesta "sf ' o "no" (en el TSP, el grafo contiene un ciclo hamiltoniano de longitud menor o igual que k?). Este problema no es ms difcil de resolver que el problema de optimizacin asociado, y adems, los resultados negativos probados para los problemas de reconocimiento son aplicables a los problemas de optimizacin. Por otro lado, el problema de reconocimiento y el problema original de optimizacin son equivalentes, en el sentido de que el algoritmo de reconocimiento se puede encajar en una bsqueda binaria para resolver el problema de optimizacin, con un nmero polinomial de llamadas a ste (un procedimiento de biseccin podra ser el ms efectivo). Consecuentemente, si un problema de reconocimiento requiere O(g(n)) el
problema de optimization requiere O(K g(n)), siendo K el nmero mximo de problemas de reconocimiento que se deben resolver para solucionar el problema de optimization asociado; de manera similar, si el problema de optimization puede ser resuelto en tiempo O(g(n)), el problema de reconocimiento se resuelve en el mismo orden de tiempo O(g(n)) -Ibaraki (1988)-. Por tanto, ambos problemas son equivalentes en el sentido del orden de magnitud necesario para su resolucin. Papadimitriou & Steiglitz (1982), Ibaraki (1988), Nemhauser & Wolsey (1988, 1989), Bondy (1995), Scholl (1995) y Hall (1996) proporcionan definiciones similares de los trminos: problema P, NP, NP-completo, NP-duro, fuertemente NP-completo y dbilmente NP-completo. A continuacin se introducen dichos conceptos y se remite a Garey & Johnson (1979) para un estudio ms profundo. En el momento de trabajar con complejidad de problemas, conviene distinguir claramente entre computacin determinista y no determinista. La computacin determinista es la que se realiza en un ordenador hipottico, entendido ste como el ordenador que ejecuta instrucciones secuencialmente y como mucho una en cada instante de tiempo. Mientras, la computacin no determinista se refiere a un concepto similar al de computacin paralela pero sin restringir el nmero de procesos que se ejecutan a la vez, adems, cada camino de computacin es independiente de los resultados de los otros (se obtiene el mismo efecto que si se realizaran computaciones deterministas para resolver cada uno un problema de reconocimiento, trabajando en paralelo y sin interaccionar entre ellas). Se dice que un problema de reconocimiento y de optimization es de clase P (tiempo polinomial), si en una computacin determinista existe un algoritmo de tiempo polinomial que lo resuelve. La clase P comprende aquellos problemas para los que existen algoritmos eficientes y que usualmente son considerados fciles. Se dice que un problema de reconocimiento es de clase NP (no determinista polinomial), si dispone de un algoritmo que en una computacin no determinista responde s en tiempo polinomial, si el problema tiene respuesta s. Dicho de otra manera, los problemas NP se caracterizan por poder ser resueltos por enumeracin, y por obtener una respuesta afirmativa, si existe, en tiempo polinomial de una computacin determinista. Por definicin, P es una subclase de NP (P NP). Sean dos problemas de reconocimiento A y B, tales que, todo ejemplar p de A de tamao n puede ser transformado en un ejemplar q de B en tiempo determinista
27
polinomial, y donde p y q satisfacen la condicin que p tiene solucin afirmativa si y slo si la tiene q. Entonces se dice que A es reducible (polinomialmente) a B. En este caso, cualquier ejemplar de A puede ser resuelto transformndolo en un ejemplar de B y aplicando un algoritmo para B. Ibaraki (1988) sugiere la relacin: (complejidad de A) < (complejidad de transformacin de A a B) + (complejidad de B), y que la complejidad de A no es mayor que la de B si la complejidad de transformacin es despreciable (lo que ocurre, cuando la complejidad de la transformacin es de tiempo polinomial y la de B no lo es). Otra forma ms compacta de expresar la relacin de complejidad anterior, tal vez sera: (complejidad de A) < MAX{ (complejidad de transformacin de A a B), (complejidad de B)}. Un problema de reconocimiento B se denomina NP-duro, si cualquier problema A de clase NP es reducible a B. Si un problema NP-duro pertenece a los NP, se llama NPcompleto (trmino introducido por Cook en 1971). Es decir, un problema es NPcompleto cuando es NP y todos los dems problemas NP pueden reducirse a l. Si un problema es NP-duro, es al menos tan difcil de resolver como cualquiera de los problemas de reconocimiento NP-completos. Por otro lado, el trmino NP-duro se puede extender a los problemas de optimizacin combinatoria, de forma que un problema de optimizacin es NP-duro si su versin de reconocimiento es NP-completo (esto es debido a que resolver el problema de optimizacin es al menos tan duro como resolver el problema de reconocimiento). De las definiciones anteriores se desprende que los problemas NP-completos son la interseccin de las clases de problemas NP y NP-duros. Por definicin, los problemas NP-completos son la clase que contiene los problemas ms difciles dentro de los problemas NP. Por otro lado, estos problemas presentan varias propiedades: a) Dos problemas A y B NP-completos satisfacen que A es reducible a B y que B es reducible a A. b) Si al menos un problema NP-completo fuera resoluble en tiempo polinomial en una computacin determinista, entonces todo problema NP sera resoluble en tiempo polinomial. Si lo enunciado en la propiedad b se cumple, entonces P = NP; actualmente se cree y se asume que P * NP, sin embargo, no se ha podido probar ni lo uno ni lo otro y sta es la cuestin fundamental todava no resuelta en la ciencia de la computacin terica. Se debe tener presente que el concepto NP-completo est basado en la complejidad del caso peor, y en varios problemas ocurre que, aun existiendo ejemplares de muy alta complejidad, stos pueden ser eficientemente resueltos en el sentido de la complejidad
media (por ejemplo, el problema de la mochila). De todas formas, y aun desde el punto de vista de la complejidad media, los problemas NP-completos son ms difciles que los problemas NP: el tamao mximo de los problemas NP-completos que pueden ser prcticamente tratados es mucho menor que los problemas NP, aun con ms sofisticados algoritmos. Por tanto, el concepto de NP-completo tambin es utilizado para medir la complejidad desde un punto de vista prctico (Ibaraki 1988). Aunque todava no se ha descubierto un algoritmo en tiempo polinomial para un problema NP-completo, algunos disponen de algoritmos pseudopolinomiales que los resuelven. Se dice que un problema es fuertemente NP-completo, si no puede tener un algoritmo pseudopolinomial que lo resuelva; un problema se dice que es dbilmente NP-completo, si puede disponer de algoritmos pseudopolinomiales que lo resuelvan (por ejemplo, el problema de la mochila 0-1). Ibaraki (1988) comenta que empricamente los problemas dbilmente NP-completos tienden a ser ms fciles de manejar mediante procedimientos enumerativos. Como expone Ibaraki (1988), en la dcada de los 80 la teora de la complejidad computacional ha revelado la existencia de una jerarqua infinita que contiene a las clases P y NP, entre sus miembros. Sean fj(n) y fa(n) funciones crecientes tales que 2(n) es asintticamente ms grande que fi(n) (por ejemplo: fi(n) = 1.000 n y 2(n) = 2"). Parece obvio que la clase de problemas resolubles en tiempo determinista fi(n), est contenida en la clase de problemas resolubles en tiempo determinista 2(n). En otras palabras, una secuencia de funciones:
22"
define una secuencia infinita de clases de complejidad. Como matiza Ibaraki (1988), la clase P viene dada por P = linik->~ clase (nk); por otro lado parece que NP c linik-. clase (2 n ), sin embargo, la localizacin exacta de NP en la secuencia anterior todava no se conoce exactamente y tampoco se puede descartar totalmente que P = NP. Segn Hall (1996), tambin se han definido clases para algoritmos paralelos y para algoritmos aleatorios. De todas formas, cabe recordar que la pregunta ms trascendental todava no resuelta es: P = NP?
A continuacin se ofrece una lista de diversos problemas P y NP-completos, citados por Even (1979), Papadimitriou & Steiglitz (1982), Corominas et al. (1984) y Kernhuser & \Volseyu988)1. Son problemas P, la resolucin de ecuaciones lineales (solving linear equations), la programacin lineal (the linear programming problem), la conexidad del grafo (graph connectedness), el camino en un grafo orientado (path in a digraph), etc., y las versiones de reconocimiento de los problemas de camino de mnimo peso con datos no negativos (the minimum-weight path problem with nonnegative data), camino de mnimo peso (the minimum-weight path problem), transporte (the transportation problem), rbol parcial mnimo (minimum spanning tree), mximo acoplamiento (maximum matching), etc. Son problemas NP-completos, el problema de camino hamiltoniano (the directed hamilton path problem), circuito hamiltoniano (the directed hamilton circuit problem), cadena hamiltoniana (the hamilton path problem), ciclo hamiltoniano (the hamilton circuit problem), condicin de satisfactibilidad (satisfiability condition), 3-coloracion (the 3-coloration problem), etc., y las versiones de reconocimiento de los problemas de afectacin generalizado (the generalized assignment problem), programacin de secuencias en procesadores en paralelo (multiprocessor scheduling), viajante de comercio (the travelling salesperson problem), empaquetado (the set packing problem), mochila 0-1 (the 0-1 knapsack problem), 2-particion (the 2-partition problem), cubrimiento de vrtices mnimo (the minimum vertex cover problem), nmero cromtico (the chromatic number), corte mximo (the maximum cut problem), etc.
2.4. Representacin de los problemas de optimizacin combinatoria. El objetivo de la exposicin siguiente consiste en identificar y especificar la forma en la que se representan los problemas de optimizacin combinatoria a lo largo del presente trabajo. Con tal fin se realiza un desarrollo argumentai que, aunque a primera vista puede resultar algo abstracto, se considera de gran utilidad en el momento de argumentar la representacin que se ha seleccionado: en forma de grafo o rbol de estados OR. Para Corts et al. (1993) solucionar un problema es partir de la salida y, recorriendo un camino, andar hasta la llegada; es una forma de construir caminos y andar por ellos. La solucin de un problema es el camino, el espacio de soluciones posibles es el problema y la representacin del espacio es la representacin del problema. El espacio est configurado por sus posibles resultados, por los lugares de partida y por los diferentes
1
Ibaraki (1988) ofrece una lista ms amplia, clasificndolos en problemas de grafos, redes, scheduling y otros.
30
caminos que se pueden trazar y recorrer. Como se puede comprobar, esta definicin encaja a la perfeccin con una representacin de estados en forma de rbol o grafo OR. Segn Salkin (1975), Mompn et al. (1987), Ibaraki (1988), Bjorndal et al. (1995), Grtschel & Lovsz (1995), etc., la optimizacin combinatoria estudia problemas caracterizados por tener un nmero finito de soluciones factibles (caminos para Corts et al. 1993), por tanto, se podra pensar en hallar la solucin ptima por enumeracin. Esta opcin es en la prctica usualmente imposible ya que se produce la temida explosin combinatoria, que como ya se ha comentado para el problema de lneas de montaje y Gass & Harris (1996) definen, es el fenmeno asociado a los problemas de optimizacin cuya dificultad computacional aumenta exponencialmente con el tamao del problema. Una vez est claro que para problemas de dimensiones interesantes no es posible enumerar todas las soluciones factibles y seleccionar la mejor, se debe pensar en cmo resolver los problemas de optimizacin combinatoria. Para Corts et al. (1993) y Rich & Knight (1994), el proceso de construccin de sistemas capaces de resolver problemas, y en particular problemas de optimizacin combinatoria, consta de los siguientes pasos: 1. Definir y describir el problema con la mayor precisin posible: estados iniciales, finales e intermedios, y operaciones de transformacin entre estados. 2. Analizar y evaluar el problema, a travs de caractersticas que pueden ser importantes: nmero de soluciones requeridas, ptimas o no, descomposicin del problema en subproblemas,... 3. Identificar, aislar y representar el conocimiento necesario para resolver el problema: de los estados y de los operadores posibles. 4. Escoger la mejor tcnica de solucin de problemas y aplicrsela. La definicin y descripcin precisa del problema implica el diseo de una representacin del mismo que lo modelice de forma que sea tratable sistemticamente. Winston (1994a) presenta una enumeracin de procedimientos generales de resolucin de problemas, que puede ayudar a definir una correspondencia entre representaciones y procedimientos de resolucin: a) Mtodo de generacin y prueba: consiste en generar soluciones factibles y evaluarlas, aceptndolas o rechazndolas (como se ha comentado este procedimiento es habitualmente impracticable). b) Mtodo de anlisis de medios y metas: basndose en el espacio de estados y conociendo el estado inicial, el estado meta y la diferencia entre ambos, el objetivo
consiste en reducir las diferencias aplicando los operadores posibles. Para ello la idea clave es explorar un rbol o grafo OR. c) Mtodo de reduccin del problema: procedimiento que parte de conocer las metas y convertirlas en submetas ms fciles de alcanzar (por ejemplo, [(/(*) + g(x))dx se puede sustituir por J f(x)dx por un lado y J g(x)dx por otro, y sumar el resultado).
Para ello la idea clave es explorar un rbol o grafo de metas, un rbol o grafo AND/OR. Como especifica Nilsson (1971), la divisin anterior no es estricta. El mtodo de reduccin de problemas consiste en hacer un anlisis del problema original para encontrar un conjunto de subproblemas, tales que, la resolucin de varios subconjuntos de subproblemas implique la resolucin del problema original; cada conjunto de subproblemas puede ser abordado por mtodos de espacio de estados (denominados por Winston (1994a) de anlisis de medios y metas) o puede ser analizado para producir nuevos subproblemas. Por tanto, estrictamente hablando la aproximacin de espacio de estados puede considerarse como un caso de reduccin de problemas. En la presente tesis nicamente se consideran aproximaciones en el espacio de estados, descartndose la divisin del problema original en problemas independientes de menor tamao o realizndose dicha divisin antes de utilizar el procedimiento de resolucin enumerativo. Tanto para la representacin en espacio de estados como la de reduccin de problemas, se suelen utilizar grafos y rboles, obtenindose los denominados OR si se utiliza una representacin mediante el espacio de estados, y los AND/OR si se trabaja con representaciones de reduccin de problemas. Como sealan Mompn et al. (1987) y Shirai & Tsujii (1987), el espacio de estados se puede representar grficamente por medio de un grafo, donde cada vrtice representa un estado del sistema y los enlaces entre ellos representan la accin de un operador para cambiar de un estado a otro; cuando los estados duplicados se representan por un slo vrtice, ya no se habla de rboles sino de grafos. Al trabajar con espacios de estados (como se hace de aqu en adelante) y para disponer de una representacin completa, se debe especificar claramente tres cosas (Nilsson 1971): - la descripcin de los estados y en particular la del estado inicial, - el conjunto de operadores y su efecto en los estados descritos, - las propiedades de un estado objetivo. En este punto existe cierta controversia ya que, mientras algunos investigadores en inteligencia artificial consideran disponer del estado objetivo (sobretodo en juegos), en investigacin operativa usualmente
no se conoce, aunque s alguna propiedad que lo describe: propiedades que debe o que no debe cumplir. Una vez se disea una representacin del problema en espacio de estados, el problema de encontrar un estado que cumpla una condicin de objetivo puede ser formulado como el problema de encontrar un vrtice en el grafo asociado cuyo estado asociado cumpla la condicin de objetivo. Como exponen Nilsson (1971), Shirai & Tsujii (1987) y Bautista et al. (1992), si un problema puede ser representado en el espacio de estados, solucionarlo se reduce a un proceso de bsqueda de un camino entre dos vrtices especficos de dicho espacio representado por un grafo. Mishkoff (1988) denomina al proceso de examen de las posibles soluciones alternativas, bsqueda; al conjunto de posibles caminos de exploracin, espacio de bsqueda; y a la forma de representar grficamente el espacio de bsqueda, rbol de bsqueda. Estos mismos autores junto a Companys (1989a), aunque es ampliamente aceptado, consideran que si se asocian unos costes a los arcos del grafo usualmente no slo se busca el camino que lleva del vrtice inicial al vrtice objetivo, sino que de entre todos los posibles se busca el camino ptimo, el de menor coste asociado (de todas formas existen excepciones: Pastor (1994) describe una aplicacin industrial en la que ms que optimizar simplemente se buscan soluciones factibles). Por otro lado, al ser la optimalidad muy costosa en tiempo y espacio, sta tiende a debilitarse, y, como comentan diferentes autores (Corts et al. 1993, Riera et al. 1995 y Corominas 1996), el esfuerzo de muchos investigadores se orienta hacia el diseo y anlisis de algoritmos aproximados que proporcionen soluciones factibles. Otro aspecto a destacar es el hecho de que hay que distinguir entre el grafo/rbol posible de bsqueda (llamado espacio de estados o espacio de bsqueda) y el grafo/rbol construido en el procedimiento de bsqueda (llamado grafo/rbol de bsqueda); uno es el grafo/rbol implcito y el otro el grafo/rbol explcito. Claramente el espacio de bsqueda puede ser infinito o, aun finito, muy extenso; por tanto, y debido a que un grafo puede ser especificado explcita o implcitamente, el problema de buscar soluciones se convierte en el de hacer explcita la mnima parte posible del grafo implcito que contiene el estado deseado. La dimensin del problema no es el nico factor que condiciona su resolucin, el diseo de su representacin tiene una gran influencia en el esfuerzo de bsqueda necesario para resolverlo: es fundamental seleccionar la formulacin ms fuerte, ms compacta, y obviamente se prefieren las representaciones con espacios de estados pequeos. El proceso requerido para el diseo de la representacin es poco conocido; segn Mompn et al. (1987) y Nemhauser & Wolsey (1988), es un arte ms que una metodologa formal, ya que no existen teoras y normas generales que ayuden a elegir correctamente, y as
"
depende de la experiencia que permite aprovechar las estructuras y caractersticas propias del problema (simplificar nociones como las simetras, etc.). Winston (1994a) expone el principio de la representacin segn el cual, una vez que el problema se describe mediante una buena representacin est casi resuelto, y describe un conjunto de caractersticas de las buenas representaciones. Por su lado, Shirai & Tsujii (1987) argumentan que la representacin adecuada de un problema simplifica su compresin. Actualmente, la comunidad cientfica internacional tiene muy presente la importancia de la representacin de los problemas; as, segn Hoffman & Padberg (1996), se estn realizando muchos esfuerzos en la reformulacin de problemas de programacin entera, considerando a veces ventajoso el hecho de incrementar el nmero de variables, el de restricciones o ambos a la vez -Alonso & Escudero (1995, 1997, 1998) resuelven un problema de planificacin del trfico areo mediante dos formulaciones equivalentes: la segunda necesita un mayor nmero de variables y restricciones, pero muchas de stas definen facetas de la regin factible; como consecuencia, es frecuente que en la solucin continua relajada del problema se obtengan muchas variables con valor entero, y, por consiguiente, el proceso de resolucin es mucho menor y ms rpido-. Adems y como comentan Johnson et al. (1997), es posible controlar el tamao del grafo explcito proporcionando una buena formulacin inicial. La mayora de investigadores consideran que antes de solucionar un problema se pueden aplicar sencillos test que permiten reformularlo compactando la solucin, al transformar, aadir y/o eliminar variables y/o restricciones -Johnson et al. (1997) proponen la disgregacin de restricciones y la reduccin de coeficientes-; estas tcnicas son conocidas usualmente como procedimientos de preproceso y se tratan en mayor profundidad en el apartado 3.8.1. Debido a los adelantos en el desarrollo de ordenadores multiprocesadores capaces de implementar en paralelo algoritmos de optimizacin, ste es otro aspecto a tener en cuenta en el momento de seleccionar una formulacin (Meyer 1989). Desde el punto de vista de la modelizacin, es importante formular el problema de forma que pueda ser descompuesto en zonas de exploracin casi independientes que se adapten a la arquitectura del ordenador donde ser resuelto. Los aspectos claves son la granularidad de la computacin, es decir, el tamao de las piezas que son ejecutadas en paralelo, y, por otro lado, la cantidad de informacin que se intercambia entre los procesadores.
34
35
3. PROCEDIMIENTOS DE RESOLUCIN ENUMERATIVOS. Como ya se ha comentado, la gran dificultad que presentan los problemas combinatorios reside precisamente en la combinatoria existente en la obtencin de soluciones, que hace que el nmero de soluciones, aunque finito, sea demasiado elevado como para poder evaluarlas todas y quedarse con la mejor. A pesar de la existencia de procedimientos especficos que resuelven algunos problemas combinatorios concretos, la mayora de ellos deben solucionarse con tcnicas generales de exploracin del espacio de soluciones factibles. A este tipo de problemas es posible asociarles un grafo OR cuyos vrtices corresponden, o a conjuntos de soluciones, o a estados que muestran la evolucin y construccin de las soluciones en curso. Basndose en esta idea existen diversos procedimientos de exploracin del grafo que se puede asociar al problema, aunque todos van explorando, o en general enumerando, diferentes estados del grafo asociado; debido a esta caracterstica comn se les suele denominar procedimientos de resolucin enumerativos. Segn seala Balczar (1993), el esquema general en el que se basan todos estos procedimientos enumerativos es conocido mediante la denominacin genrica "esquema divide y vencers". Su descripcin intuitiva es simple: los datos se descomponen en partes aproximadamente iguales, se resuelve recursivamente el mismo problema sobre estas partes, y se combinan las soluciones parciales para obtener la solucin del problema global (Nilsson 1971, Nemhauser & Wolsey 1989, Balczar 1993, Brunat 1996, etc.). En contrapartida a esta aparente sencillez, tanto la forma de descomponer los datos como la de combinar los resultados pueden ser relativamente complejas. Por otro lado, este esquema se basa en explorar un rbol o grafo AND/OR, pero como se expone en las hiptesis de trabajo, en esta tesis nicamente se consideran representaciones mediante rboles o grafos OR, descartndose la descomposicin del problema original en problemas independientes de menor tamao, o realizndose dicha divisin antes de utilizar el procedimiento de resolucin enumerativo considerado. Desde hace ms de 30 aos, en la literatura proveniente del rea de la investigacin operativa existen referencias que abordan tanto los problemas de optimizacin combinatoria, como los procedimientos enumerativos que se han ido desarrollando para su resolucin. De todas formas, la mayora de estas referencias exponen procedimientos de forma aislada y son escasas aqullas que presentan una formulacin comn que engloba a ms de un procedimiento. Adems, cabe destacar que algunos de estos procedimientos no son tan recientes. Por ejemplo, desde el siglo XIX se conoce un antecesor de lo que hoy se denomina bsqueda en profundidad (depth first search) como una tcnica para recorrer laberintos: como cita Even (1979), en 1.882 E. Lucas, en Rcrations Mathmatiques, relata el trabajo de Trmaux como sigue.
36
Disponiendo de un grafo conexo y comenzando en uno de los vrtices, se desea caminar a travs de todos los arcos, de vrtice a vrtice, de forma que se visiten todos los vrtices, se recorran todos los arcos y se finalice en el mismo vrtice donde se comenz. Claramente se necesita ir marcando los lugares por donde se va pasando, y para ello se utilizan dos tipos de marcas: F para la salida del arco por el que se visita por primera vez el vrtice y E para cualquier entrada en un arco cuando se usa para abandonar el vrtice; por tanto, un arco tiene una entrada y una salida, que se marcan por separado. Adems ninguna marca es cambiada o eliminada. Sea s el vrtice inicial y v el vrtice actual, el algoritmo de Trmaux es el siguiente: Fase 1. v 4- s. Fase 2. Si todos los arcos estn marcados, ir a la fase 4. Fase 3. Elegir un arco no marcado, marcar su entrada con E y atravesarlo hasta el vrtice u. Si u tiene algn arco marcado (si no se visita por primera vez), entonces marcar la salida del arco por el que se ha entrado en u con E, atravesar el arco hasta volver a v e ir a la fase 2. Si u no tiene ningn arco marcado (si es la primera vez que se visita), entonces marcar la salida del arco por el que se ha entrado en u con F, v < u e ir a la fase 2. Fase 4. Si no hay arcos marcados con F, fin (se ha vuelto a s y se ha recorrido el grafo completamente). Fase 5. Usar el arco marcado con F, atravesarlo hasta el vrtice u, v < u e ir a la fase 2.
El procedimiento de Trmaux constituye un antecesor de lo que hoy se conoce como bsqueda en profundidad, ya que siempre explora el vrtice ms profundo haciendo backtracking si se llega a un vrtice terminal. En el ejemplo anterior, la exploracin realizada se podra representar mediante un rbol de bsqueda, en el que las letras
37
asociadas a cada vrtice indican el vrtice del grafo explorado, y los nmeros el orden de la exploracin:
Los procedimientos de exploracin denominados de branch and bound (que como matizan Corominas et al. (1984) no es un algoritmo sino una familia muy numerosa), han sido una de las tcnicas mejor estudiadas realizndose numerosas formulaciones cada vez ms generales. Como comenta Mller-Merbach (1997), tienen una historia de 37 aos y comienzan con Land & Doig (An Automatic Method of Solving Discrete Programming Problems. Econometrica, vol. 28, 1960, pp. 497-520), quienes sugieren el principio del rbol de bsqueda para programacin entera; el mismo principio es aplicado al TSP por Little et al. (An Algorithm for the Traveling Salesman Problem. Operations Research, vol. 11, 1963, pp. 972-989), quienes sugieren el trmino branch and bound. En 1988, Ibaraki realiza una extensa y brillante exposicin acerca de los problemas de optimizacin combinatoria y su dificultad, los algoritmos de branch and bound y algunas aplicaciones en diversos problemas de optimizacin combinatoria, comenta el uso de stos y de nuevos procedimientos enumerativos de exploracin de grafos en el rea de la inteligencia artificial, y la posibilidad de disear algoritmos heursticos utilizando como base los algoritmos branch and bound descritos -Ibaraki (1988)r. De todas formas, aunque se puede considerar que Ibaraki es uno de los primeros autores que intenta disear un marco comn para varios de los procedimientos existentes, no logra formular un modelo general para todos ellos. Por otro lado, en la ltima dcada, y tanto en investigacin operativa como en inteligencia artificial, han surgido nuevos procedimientos enumerativos (como por ejemplo la bounded dynamic programming) y se han publicado diferentes trabajos en los que se utilizan nuevas tcnicas y herramientas (tcnicas de consistencia y paralelizacin), aunque tambin aplicadas a procedimientos singulares.
38
Es necesario destacar que al utilizar tcnicas de exploracin en rboles de bsqueda, la mayora de autores provenientes del rea de la investigacin operativa se han planteado desde siempre el objetivo de optimizar, mientras que entre los provenientes del rea de la inteligencia artificial el objetivo prioritario ha sido obtener soluciones factibles. Actualmente parece que, como mnimo en cuanto a problemas de optimizacin combinatoria, se coincide en el objetivo de optimizar. Conviene realizar la aclaracin anterior, ya que en el uso de los diferentes procedimientos de exploracin a veces se pasa del primero al segundo objetivo y viceversa, lo que puede dar lugar a confusiones. En el presente apartado, se enumeran diversas clasificaciones de los procedimientos de resolucin enumerativos (3.1.), se comentan las funciones de evaluacin de vrtices que presentan diversos autores (3.2.) y se definen las diferentes tcnicas identificadas en la literatura referenciada (3.3. a 3.9.).
3.1. Clasificacin de los procedimientos de resolucin enumerativos. Los procedimientos de resolucin enumerativos admiten varias clasificaciones en funcin del objetivo o caracterstica principal por la cual se realiza dicha clasificacin. Diferentes autores, entre ellos Nilsson (1971), Barr & Feigenbaum (1981), Pearl (1984), Mompn et al. (1987), Companys (1989a), Corts et al. (1993), Ginsberg (1993), Rich & Knight (1994) y Winston (1994a), realizan clasificaciones semejantes aunque con ciertas particularidades segn la exposicin concreta de cada autor. En el presente texto se exponen cuatro clasificaciones diferentes. Si la caracterstica a considerar es la forma de dirigir la exploracin utilizando la informacin que se dispone para la misma, se distingue entre procedimientos ciegos (o sin informacin) y guiados (o con informacin heurstica); si lo importante es la optimalidad de la solucin, se presentan los procedimientos heursticos y los exactos; si lo que se desea destacar es la factibilidad y calidad de las soluciones obtenidas, entonces existen procedimientos para la obtencin de una o todas las soluciones factibles o para demostrar la no existencia de ninguna solucin factible, o bien para obtener una solucin subptima, o bien para obtener una o todas las soluciones ptimas; en cambio, si el elemento de principal importancia es la conservacin o no de los estados equivalentes segn el coste de seguir las trayectorias para alcanzarlos, se presentan los procedimientos con o sin agrupacin de estados equivalentes. En la prctica, la clasificacin de estas tcnicas resulta ser complicada y confusa, ya que por un lado las clasificaciones presentadas resultan ser demasiado generalistas, y, por otro, los diferentes procedimientos desarrollados tienen muchas caractersticas comunes que no los especifican y diferencian claramente. Para exponer los diferentes
39
procedimientos referenciados, en el apartado 3.1.5. se realiza una enumeracin de diferentes conjuntos de tcnicas, que no se corresponde con ninguna de las clasificaciones presentadas y que tampoco aspira a ser una nueva clasificacin. Dicha enumeracin nicamente pretende agrupar estos procedimientos en la medida de lo posible y en referencia a alguna caracterstica comn. 3.1.1. Ciegos / guiados. Atendiendo a la manera de dirigir la bsqueda utilizando la informacin que se dispone para dicha misin, los procedimientos de resolucin enumerativos se clasifican en ciegos y guiados: Procedimientos ciegos (o sin informacin): la bsqueda con procedimientos ciegos se corresponde aproximadamente con la generacin y estudio sistemtico de los estados del espacio de bsqueda, hasta encontrar una solucin que cumple la condicin de objetivo. En estos procedimientos, la eleccin del vrtice a explorar slo depende de su posicin en el rbol de bsqueda y no de otras caractersticas, y por tanto, el orden en el que se explora para encontrar la solucin slo se basa en una estrategia de seleccin uniforme y esttica; por otro lado, se consideran impracticables para problemas no triviales al explorar intilmente una gran regin del espacio de soluciones factibles y producirse la temida explosin combinatoria. Las diferentes tcnicas difieren en el orden en el que se exploran los vrtices, y entre stas se encuentran: la generacin de todas las soluciones, la bsqueda en anchura, la bsqueda en profundidad con backtracking, la bsqueda no determinista (segn Winston 1994a, interesante cuando no se tiene la certeza de qu bsqueda es mejor si en profundidad o en anchura), el iterative deepening, el iterative broadening, y otros procedimientos que no son objeto de estudio del presente trabajo como la bsqueda en anchura y en profundidad para grafos AND/OR. Procedimientos guiados (o con informacin heurstica): la bsqueda con procedimientos guiados genera y explora estados del espacio de bsqueda aprovechando una cierta informacin sobre el problema especfico, llamada informacin heurstica, para (en muchas ocasiones) restringir drsticamente la exploracin, y hasta encontrar una solucin que cumple la condicin de objetivo. Los instantes en los que se puede aplicar la informacin heurstica son al seleccionar el prximo vrtice a explorar (usualmente se toma "el ms prometedor" segn una funcin de evaluacin o indicador), al elegir el sucesor o sucesores a generar en el curso de la expansin de un vrtice (pudiendo generar una expansin parcial) y al decidir qu vrtices deben ser descartados del rbol de bsqueda (garantizando la optimalidad de la solucin en algunas ocasiones y no pudindola garantizar en otras). Entre estos procedimientos destacan la bsqueda primero el mejor, la bsqueda en
40
anchura limitada, la bsqueda en profundidad-m, el algoritmo A, el algoritmo A* y el algoritmo EDA*. Companys (1989a) y Winston (1994a) opinan que la eficiencia de la bsqueda aumenta si existe una forma de ordenar los vrtices a explorar (en particular mediante informacin heurstica acerca del problema), de modo que los ms prometedores se exploren primero. Por su parte, Rich (1990) seala que la informacin heurstica no es necesaria para problemas triviales, ya que se pueden resolver por enumeracin exhaustiva, pero que en entornos ms complejos esta informacin juega un rol crucial en la resolucin de problemas de forma factible. Es importante no olvidar que para un problema dado puede haber ms de una funcin de evaluacin y que es difcil demostrar cul se comporta ms adecuadamente; adems, la eleccin de la funcin de evaluacin determina crticamente los resultados de la exploracin. Por otro lado, se debe tener en cuenta que el tiempo invertido en evaluar los vrtices para seleccionar el que se va a explorar, debe ser recompensado con una reduccin del tamao del espacio de bsqueda: en general existe un compromiso entre el coste de evaluacin de una funcin heurstica y el ahorro de tiempo de bsqueda que proporciona dicha funcin. Mompn et al. (1987) muestran este compromiso en la siguiente figura, de la que deducen que el coste total mnimo se encuentra en sistemas no totalmente informados y con un cierto componente de bsqueda:
Coste
(I ) Coste de la bsqueda
Informacin
Total
3.1.2. Heursticos / exactos. En funcin de la posibilidad de asegurar o no la optimalidad de la solucin o soluciones obtenidas, se distinguen los siguientes procedimientos: Procedimientos exactos: la bsqueda con procedimientos exactos se corresponde con la generacin y estudio de estados del espacio de bsqueda, hasta encontrar una o varias soluciones para las que se puede asegurar su optimalidad.
Procedimientos heursticos: procedimientos en los que se relaja la condicin de optimalidad de la solucin o soluciones a obtener. En numerosas ocasiones, se intenta reducir el esfuerzo de bsqueda sacrificando la garanta de encontrar soluciones ptimas; segn Nilsson (1971) y Barr & Feigenbaum (1981), en la prctica interesa minimizar una combinacin promedio de la calidad de la solucin y del coste de la bsqueda necesaria para obtenerla. Adems hay que tener presente que, como expone Mishkoff (1988), en general los procedimientos heursticos no garantizan encontrar una solucin factible a problemas especficos aunque stas existan. La mayora de procedimientos desarrollados en la literatura permiten disear una o diversas versiones exactas o heursticas del mismo, en funcin de, por ejemplo, la condicin de finalizacin de la bsqueda: las tcnicas de bsqueda branch and bound, de programacin dinmica y el algoritmo A*, usualmente son consideradas tcnicas exactas, aunque como exponen varios autores se pueden derivar diversos procedimientos heursticos a partir de stas. Concretamente, Nilsson (1971, 1980), Corominas et al. (1984), Companys (1989a) y Corominas (1996), presentan la posibilidad de convenir procedimientos exactos en algoritmos heursticos, prescindiendo de algunas de las condiciones que lo definen y realizando la bsqueda en un rea restringida: a) Limitar el tiempo mximo de ejecucin del procedimiento, con lo que se puede llegar a obtener ninguna solucin factible, la mejor solucin hallada (solucin preferible) y una cota del error, o incluso la solucin ptima y la confirmacin de que lo es. b) Eliminar vrtices mediante reglas "sensatas", como por ejemplo: - en cada paso, prescindir de los vrtices peores entre los sucesores de un vrtice o entre todos los generados, o guardar un nmero concreto de vrtices sucesores. - generar vrtices pero slo guardar el mejor o los mejores. - en caso de minimizar, eliminar los vrtices tales que z + e > z , siendo z el valor de una cota inferior de dicho vrtice, e > O una cota superior del error mximo que se permite cometer (que puede ser funcin de diversos parmetros, por ejemplo de la posicin del vrtice en la arborescencia y/o del tiempo que todava se dispone para resolver el problema) y z el valor de la solucin preferible. c) Limitar la memoria o ejecutar el procedimiento hasta que se excede la memoria disponible. d) Autolimitar la memoria: expulsar los vrtices de, por ejemplo, peor valor de una cota o indicador.
42
Ibaraki (1988) expone tres procedimientos heursticos derivados del branch and bound, en los que utiliza varias de las ideas expuestas anteriormente: mtodo de la e-asignacin, mtodo del T-corte y mtodo del M-corte; adems comenta que stos se pueden combinar para obtener nuevos procedimientos heursticos hbridos (tcnicas descritas con detalle en el apartado 3.9.1.). Los diferentes procesos de seleccin del vrtice a partir del cual ramificar en cada nivel, tambin permiten disear mltiples algoritmos heursticos: por ejemplo, se pueden disear diferentes heursticas a partir de una dada, tomando como criterio para elegir el vrtice a explorar: el valor de una cota superior, el valor de una cota inferior, el valor de un indicador, etc. (Alvarez et al. 1988). Algunos autores como Ibaraki (1988) y Rich & Knight (1994) proporcionan varios argumentos para justificar el uso de procedimientos heursticos frente a exactos: - sin ellos se est desesperadamente enredado en una explosin combinatoria: muchos problemas de optimizacin combinatoria son muy difciles de resolver exactamente e incluso con algoritmos muy sofisticados el tamao de los problemas resolubles es muy limitado, - para propsitos prcticos normalmente no se necesita una solucin ptima, con frecuencia una buena aproximacin es suficiente, - si bien las soluciones que se logran con una heurstica pueden no ser muy buenas en los peores casos, estos peores casos raramente se presentan en el mundo real, - intentar comprender por qu funciona una heurstica, o por qu no lo hace, normalmente sirve para profundizar en la comprensin del problema; adems se puede aadir que un procedimiento heurstico sirve para inicializar un proceso de eliminacin de estados "no objetivo" en un algoritmo exacto: dada la solucin preferible (que como mnimo al inicio coincide con la solucin heurstica), se eliminan aquellos estados para los que se puede asegurar, mediante una cota, que entre sus descendientes no existe ninguna solucin factible mejor que la solucin preferible. 3.1.3. Obtencin de una solucin factible / una solucin subptima / una o todas las soluciones ptimas. Atendiendo a la factibilidad y calidad de las soluciones buscadas, se presenta la siguiente clasificacin: Procedimientos para la obtencin de una o todas las soluciones factibles, o para demostrar la no existencia de ninguna solucin: la bsqueda se basa en la generacin y estudio de estados del espacio de bsqueda, hasta encontrar una o todas las
43
soluciones que cumplen las condiciones de factibilidad, o hasta poder asegurar que no existe ninguna solucin que cumple dichas condiciones. Procedimientos para la obtencin de una solucin subptima: procedimientos que se basan en generar y estudiar estados del espacio de bsqueda, hasta encontrar una solucin "de cierta calidad". Usualmente la calidad de una solucin se mide en relacin a una cota de la solucin ptima, lo que implica que, para que sea realmente significativa, la cota tambin debe ser "de calidad"; en un contexto industrial, la calidad de una solucin se puede medir en relacin a un valor que se desea obtener y que es considerado alcanzable. Procedimientos para la obtencin de una o todas las soluciones ptimas: la bsqueda se basa en la generacin y estudio de estados del espacio de bsqueda, hasta encontrar una o todas las soluciones para las que es posible asegurar su optimalidad. 3.1.4. Agrupando estados equivalentes / sin agrupar estados equivalentes. Winston (1994a) es uno de los pocos autores que presenta una clasificacin de las tcnicas de resolucin enumerativas, considerando como elemento de principal importancia, la agrupacin o no de estados equivalentes segn el coste de alcanzar dichos estados; as, se distinguen dos clases de procedimientos: Procedimientos sin agrupacin de estados equivalentes: la bsqueda se basa en la generacin y estudio de estados del espacio de bsqueda hasta encontrar uno o varios estados considerados objetivo, manteniendo los estados equivalentes (tambin denominados duplicados o redundantes) y las diversas trayectorias exploradas para alcanzarlos. Procedimientos con agrupacin de estados equivalentes: procedimientos en los que, en el momento de la generacin y estudio de estados del espacio de bsqueda, se van agrupando los estados equivalentes y slo se conserva la mejor de entre las diferentes trayectorias exploradas para alcanzarlos. Son tcnicas de este tipo la programacin dinmica, el branch and bound en combinacin con la programacin dinmica, etc., aunque en la prctica se disean procedimientos que permiten incorporar esta caracterstica a eleccin del usuario, haciendo muy difcil una clasificacin exhaustiva. 3.1.5. Conjuntos de procedimientos referenciados. Como ya se ha comentado, a continuacin se realiza una breve descripcin de los diferentes conjuntos de procedimientos en los que se agrupan las tcnicas referenciadas.
Esta pseudo-clasificacin se basa en citar en un mismo conjunto aquellas tcnicas que presentan ciertas caractersticas semejantes entre s, y nicamente se realiza para presentar los procedimientos enumerativos de una forma ms compacta que no una simple enumeracin y descripcin. Adems hay que tener presente que algunos de los procedimientos que se citan podran ser expuestos en varios de dichos conjuntos de tcnicas. Procedimientos de bsqueda basados en la "fuerza bruta": aqullos que para la generacin y exploracin de estados del espacio de bsqueda no utilizan ninguna tcnica de podado de dicho espacio, pudiendo llegar a generar, en el caso extremo y ms probablemente que con otros procedimientos, todos los estados. Entre stos se encuentran: la obtencin de todas las soluciones, la bsqueda aleatoria, la bsqueda en profundidad, la bsqueda en anchura, la bsqueda primero el de menor coste, la bsqueda primero el mejor, etc. Procedimientos de bsqueda basados en programacin dinmica: la caracterstica principal que presentan estas tcnicas de bsqueda y que las diferencian del resto, consiste en la agrupacin de estados equivalentes y en la conservacin de la mejor trayectoria hasta alcanzarlos segn una funcin de evaluacin objetivo. Procedimientos de bsqueda basados en la poda de vrtices mediante cotas: tcnicas de exploracin que identifican vrtices que no contienen soluciones ptimas y los eliminan de la enumeracin; para ello, se resuelve un problema relajado del original, cuya solucin ptima proporciona una cota del valor de la solucin del problema original. Entre los procedimientos basados en la poda de vrtices mediante cotas, ms conocidos como de ramificacin y acotacin, cabe destacar, entre otros, el procedimiento branch and bound, el branch and prune, el depth-first I breadth-first I best-first I... branch and bound, el branch and cut, el branch and price y el branch and cut and price. Procedimientos de bsqueda usualmente descritos en el rea de la inteligencia artificial: tcnicas de exploracin expuestas bsicamente en el rea de la inteligencia artificial y que forman parte de los procedimientos enumerativos de bsqueda en espacios de estados: dependency directed backtracking, iterative deepening, iterative broadening, algoritmos A y A*, algoritmo IDA*, algoritmos de potencia heurstica, bsqueda en profundidad-m, bsqueda en anchura limitada, etc. Procedimientos de bsqueda hbridos: aqullos que se basan en utilizar, de forma simultnea, las estrategias y/o caractersticas diferenciadoras de diversos procedimientos "puros": incorporan varias tcnicas que podran ser consideradas
"puras". Cabe destacar la programacin dinmica acotada y los procedimientos branch and bound con tcnicas de exploracin de entornos. Procedimientos de bsqueda basados en tcnicas de reduccin: procedimientos en los que la exploracin se basa en el uso sistemtico de tcnicas que reducen el espacio de estados. Se diferencia entre las tcnicas de reduccin procedentes del rea de la investigacin operativa (las tcnicas de preproceso) y las diseadas en el rea de la inteligencia artificial (las tcnicas de consistencia). Procedimientos heursticos: tcnicas que usualmente no son capaces de asegurar la optimalidad de la solucin o soluciones obtenidas, e incluso su factibilidad para problemas especficos. Existen procedimientos heursticos basados en el branch and bound (como el mtodo de la e-asignacin, del T-corte y del M-corte, entre otros), en el algoritmo A*, en la programacin dinmica, y otros como las estrategias de escalada, la bsqueda en haz de amplitud n, etc. En los apartados 3.3. a 3.9. se describen los procedimientos enumerativos que se engloban en cada uno de estos conjuntos de tcnicas, exponiendo las definiciones que se presentan en la literatura referenciada. Despus de consultar dichos apartados, el lector puede tener la sensacin de que se ha descrito un panorama poco estructurado y poco compacto, donde no hay casi nada claro y donde unos autores definen y utilizan unos elementos o procedimientos de una forma y otros de otra, que, aun semejante, no es igual. Por otro lado, parece que no se tienen muy claros los conceptos o que han sido utilizados entremezclados y tal vez de una manera poco formal. El estado del arte que aqu se describe es el entorno real al que se enfrenta cualquier investigador que trabaje en el campo de la resolucin de problemas de optimizacin combinatoria mediante rboles de bsqueda OR. Por este motivo, y a pesar de incorporar ya un gran esfuerzo de sntesis, se considera oportuno presentarlo de esta forma tan poco estructurada y formalizada.
3.2. Funciones de evaluacin. A lo largo del texto, en numerosas ocasiones se ha hecho referencia a los mejores y peores vrtices o estados del espacio de bsqueda. Para dirigir la exploracin se han definido diversas estrategias de bsqueda, que tienen en comn el disponer de un procedimiento para seleccionar el prximo vrtice a explorar entre todos los candidatos. Como ya se ha comentado, para evaluar dichos vrtices, ordenarlos y poder decir cul es el considerado como mejor o peor, usualmente se utiliza una funcin de evaluacin (tambin llamada indicador) que, a veces, incorpora informacin heurstica relativa al
problema. La informacin que pueden incorporar las funciones de evaluacin puede ser muy variada: la probabilidad de que un vrtice se encuentre en el mejor camino, medidas o cotas de la distancia a un vrtice objetivo, medidas aditivas de coste, etc., pero como comenta Nilsson (1971), habitualmente se les suele asociar una estimacin del camino mnimo desde el vrtice raz a un vrtice objetivo, pasando por el vrtice evaluado. La funcin de evaluacin de los vrtices es de vital importancia en la definicin y especificacin de los diferentes procedimientos de bsqueda, ya que en funcin de la concrecin de sta se pueden definir varios de los procedimientos existentes. En la literatura se han expuesto diversas funciones de evaluacin y seleccin de vrtices, con diferentes grados de generalidad. A continuacin se detallan algunas de las funciones ms generales, aplazando la especificacin de las funciones ms particulares a la definicin del procedimiento en el que son utilizadas (apartados 3.3. a 3.9.). Diversos autores (Nilsson (1971, 1980), Barr & Feigenbaum 1981, Pearl (1983, 1984), Mompn et al. 1987, Ibaraki 1988, Companys 1989a, Korf 1990, Corts et al. 1993, Ginsberg 1993, Kusiak et al. 1993, Rich & Knight 1994, Greenberg 1996, etc.) exponen funciones de evaluacin para procedimientos enumerativos, cada vez ms generales. Sea un problema de minimizacin; una de las formas ms habitualmente utilizadas de caracterizar la bondad de un vrtice en vistas a su distancia a un vrtice considerado como objetivo (que puede ser un estado que proporcione una solucin factible, una solucin subptima o una solucin ptima), es mediante la siguiente funcin de evaluacin: f*(n) = g*(n) + h*(n), donde: - n es el vrtice considerado, - g (n) es el coste del camino de mnimo coste (en nmero de arcos o como una funcin aditiva de los costes asociados a dichos arcos) desde el vrtice raz s hasta el citado vrtice n, y est definido para todos los vrtices accesibles desde s, - h*(n) es el coste del camino de mnimo coste (de nuevo en nmero de arcos o como una funcin aditiva de los costes asociados a dichos arcos) desde el vrtice n hasta un estado objetivo, - f*(n) es el valor que adopta la funcin de evaluacin y se corresponde con el valor del camino de mnimo coste desde el vrtice raz s hasta un vrtice objetivo, condicionado a pasar por el vrtice n (por tanto f*(s) = h*(s)).
Como se puede comprobar, f*(n) es un evaluador perfecto que nos indica siempre el camino de mnimo coste desde el vrtice raz hasta un vrtice considerado objetivo; por tanto, la seleccin del vrtice de mnimo valor de f*(n) conduce directamente a la solucin ptima. Lamentablemente, es habitual desconocer f*(n) y se dispone nicamente de f(n), una estimacin de dicho valor. La precisin de f(n) respecto a f*(n) depende en su totalidad de la calidad del estimador de g*(n), g(n), y del estimador de h (n), h(n). Se define f(n) como sigue:
que se seleccionan los vrtices sin considerar el coste acumulado hasta alcanzarlos. Intentando generalizar la funcin de evaluacin para permitir ajustar el balance entre ambas tendencias, Barr & Feigenbaum (1981) exponen que en 1969 Pohl define el heuristic path algorithm (HPA), que es un procedimiento de bsqueda enumerativo que incorpora la siguiente funcin de evaluacin: f(n) = (1 - co) g(n) + co h(n), donde co [0, 1]. Fijando co = 1 se obtiene la funcin de evaluacin f(n) = h(n), haciendo = O la funcin de evaluacin resultante es f(n) = g(n) y fijando co = 0,5 se consigue la funcin de evaluacin descrita inicialmente f(n) = g(n) + h(n). Variando co entre 0 y 1 se pueden encontrar infinitas variantes de un mismo procedimiento que incorpore esta funcin de evaluacin. Segn Pearl (1984), en cuanto al nmero de vrtices expandidos, algunos experimentos parecen indicar que se obtienen los mejores resultados con co = 0,5. Ibaraki (1988), basndose en su propia experiencia computacional, matiza que en general co = 0,5 va mejor que co = 1 y stos mejor que co = O, aunque tambin especifica que si h(n) es un buen estimador co debe tender a 1 y si contiene errores co < 1 . Para valorar la influencia de la informacin heurstica h(n) en la bsqueda, algunos autores como Nilsson (1971, 1980) y Companys (1989a) comentan el concepto de poder o potencia heurstica de un algoritmo de exploracin que incorpora la funcin de evaluacin descrita por Pohl. As, la seleccin del valor de u) es esencial para calibrar la potencia heurstica de un algoritmo: - con valores pequeos de co predomina la exploracin en anchura y se intenta garantizar que ninguna parte del grafo queda inexplorada para siempre, - con valores grandes de co predomina la componente heurstica y se busca encontrar rpidamente un camino hasta un vrtice objetivo, aunque no sea ptimo. Segn Companys (1989a), la eficiencia de la exploracin aumenta en muchos casos si el valor de co vara con la profundidad del vrtice: a poca profundidad se utiliza un valor de co grande, y a grandes profundidades se toman co menores para explorar ms en anchura e intentar encontrar algn camino hasta un estado objetivo. Barr & Feigenbaum (1981) relatan un nuevo algoritmo propuesto por Pohl, llamado de pesos dinmicos (dynamic weighting), en el se que utiliza una generalizacin de la funcin de evaluacin definida para el HPA:
49
donde la funcin (u(n) puede ser mayor o igual a 1 y vara con la profundidad del vrtice n, reduciendo su valor a medida que la profundidad aumenta. Barr & Feigenbaum (1981) tambin describen el procedimiento heurstico propuesto por Harris, llamado bsqueda con ancho de banda (bandwidth search), que se basa en asumir que no es posible encontrar ninguna buena funcin f(n) que satisfaga la condicin de admisibilidad; as introduce la condicin de ancho de banda, que requiere una funcin que, en todos los vrtices no objetivo, cumpla h(n) < h (n) + e, y como consecuencia define un algoritmo e-admisible y encuentra soluciones e-ptimas. Como es lgico y comentan diversos autores (Nilsson 1971, Barr & Feigenbaum 1981, Harmell 1986, Kusiak et al. 1993, etc.), la eficiencia de los procedimientos enumerativos depende de la seleccin de la funcin de evaluacin f(n), que determina crticamente el resultado de la bsqueda y debe depender del objetivo perseguido: obtener soluciones ptimas, buenas soluciones o soluciones factibles. En la prctica, aunque puede parecer un proceso sencillo, el diseo de una buena funcin de evaluacin puede llegar a ser muy complejo, tal y como seala Hartnell (1986). Por otro lado y debido a que la informacin tiene un coste, Nilsson (1980) recuerda que se debe llegar a un compromiso entre el coste de obtener f(n) y el coste de la computacin, tal y como ya se ha comentado en el apartado 3.1.1, para los procedimientos guiados. A falta de especificar otras caractersticas de los procedimientos enumerativos de bsqueda en grafos OR, como por ejemplo el agrupar o no los estados equivalentes o el podar o no vrtices, la concrecin de la funcin f(n) permite diferenciar entre s varios de los procedimiento descritos en la literatura referenciada: por ejemplo, segn Greenberg (1996) un caso especial es la bsqueda en profundidad, donde h(n) = O, g(n) se define como la profundidad del vrtice n y donde se selecciona el vrtice de mayor f(n) (o para no perder el criterio de optimizacin utilizado -la minimizacin-, definiendo g(n) como menos la profundidad del vrtice n y seleccionando el vrtice de menor f(n)); otro caso particular que comenta Greenberg (1996) es el branch and bound para programacin entera, donde g(n) + h(n) es el valor objetivo de la relajacin lineal en el vrtice; como exponen Mompn et al. (1987) y Companys (1989a), si no se dispone de informacin heurstica, esto es si h(n) = O, el procedimiento resultante pertenece a los algoritmos de bsqueda en anchura, si se define g(n) como la profundidad del vrtice y se selecciona el vrtice de menor f(n); si slo interesa alcanzar un vrtice objetivo sea de la forma que sea, Rich & Knight (1994) proponen definir g(n) = O, as se elige el vrtice que parece ms cercano al objetivo, y, segn Barr & Feigenbaum (1981), se minimiza el esfuerzo de exploracin a expensas de no buscar una solucin de mnimo coste (idea que segn estos autores fue utilizada por primera vez por Doran y Michie en 1966 en su algoritmo graph traverser); de todas formas y como exponen Nilsson (1971) y Pearl (1984), aunque no sea esencial encontrar un camino de coste mnimo, g(n) se debe
50
incluir en f(n) ya que es mejor trabajar con g(n) que si ella. Vistas las numerosas posibilidades existentes, parece evidente que el desarrollo de eficientes y efectivas funciones de evaluacin es una tarea difcil, llegando a constituir, segn Shih et al. (1992), un arte ms que una ciencia. Hartnell (1986) expone la posibilidad de introducir en los procedimientos de bsqueda la seleccin de los vrtices en funcin del cumplimiento o no de una jerarqua de criterios: primero se selecciona para expandir el vrtice que cumple el primer criterio, si hay empate o no existe ninguno, el que cumple el segundo criterio y as sucesivamente. De todas formas, si los criterios son cuantificables se presenta la misma situacin que si se dispone de ms de una funcin heurstica: se puede evaluar lo prometedor que es un vrtice ponderando los valores de dichas funciones y luego seleccionando el de mejor valor ponderado. Este tipo de procedimientos permiten introducir una mayor flexibilidad, al incorporar dichos criterios cuantificables a la funcin de evaluacin mediante coeficientes de ponderacin suficientemente diferentes. Si de todas maneras persiste el empate, Hartnell (1986) propone desempatar al azar. Parece conveniente disear los coeficientes utilizados para ponderar las diversas funciones heursticas y/o criterios, dinmicos y en funcin de las caractersticas de dichos criterios, de la profundidad del vrtice, etc. En un primer anlisis se puede comprobar, cmo la mayora de estrategias de seleccin que se proponen en la literatura nicamente son funcin del vrtice considerado y no tienen en cuenta ni el estado de evolucin de la exploracin ni las condiciones de entorno en las que se resuelve el problema. Recopilando dichas estrategias de seleccin y teniendo presente varias caractersticas no consideradas, en el apartado 7.4.4. se define la siguiente funcin general de evaluacin y seleccin de vrtices: f(n, t, a,, e) = (p[g(n), h(n), c(n), li(n), ..., ls(n), r(n); t; 2 , h,*, v va m R F,; T, V, VA,, Mt, TGk; a(n, t, a,, e), (n, t, a,, e), S(n, t, a,, e), y(n, t, a,, e), ..., ys(n, t, a,, e), t(n, t, at, e)],
que es funcin de n (el vrtice considerado), t (el tiempo de ejecucin hasta el momento), a, (el estado de evolucin de la arborescencia en el instante t) y e (las condiciones de entorno en las que se resuelve el problema).
3.3. Procedimientos de bsqueda basados en la "fuerza bruta". Los procedimientos de bsqueda basados en la "fuerza bruta" son aqullos que para la generacin y exploracin de estados del espacio de bsqueda, y hasta encontrar una o diversas soluciones que cumplan la condicin de objetivo, no utilizan ninguna tcnica
51
de reduccin de dicho espacio, pudiendo llegar a generar en el caso extremo y ms probablemente que con otros procedimientos, todos los estados. Segn Corts et al. (1993), el espacio de estados ha de ser explorado de forma progresiva y sistemtica: se ha de establecer un orden para explorar los vrtices factibles y un procedimiento para retroceder cuando se descubre un camino sin salida (un vrtice terminal no objetivo). Las diferentes tcnicas que se pueden denominar como de "fuerza bruta" se diferencian en el orden en el que se explora el espacio de estados hasta alcanzar un estado objetivo, y difieren entre s en cuanto a optimalidad, coste computacional, etc. Entre stas se encuentran tanto procedimientos que no utilizan ningn tipo de informacin heurstica acerca del problema (obtencin de todas las soluciones, bsqueda aleatoria, bsqueda en profundidad, bsqueda en anchura, etc.), como procedimientos que s utilizan informacin heurstica (bsqueda primero el de menor coste, bsqueda primero el mejor, etc.). Como comenta Companys (1989a), estos procedimientos no suelen ser muy interesantes, ya que usualmente resultan ser impracticables para problemas de dimensiones industriales al explorar intilmente grandes regiones del espacio de soluciones factibles. Su gran ventaja es el hecho de ser universalmente aplicables, pero a costa de ser potencialmente ineficientes (Bruynooghe & Venken 1990). Los procedimientos que se describen a continuacin tienen la caracterstica comn de utilizar la "fuerza bruta" para encontrar la solucin o soluciones buscadas. Estos procedimientos han sido descritos por diferentes autores, algunos como algoritmos por s mismos y otros como estrategias para seleccionar el siguiente vrtice a expandir dentro de un procedimiento de bsqueda. A veces las definiciones que exponen no son lo suficientemente precisas para saber si se refieren a una estrategia de seleccin o a un algoritmo concreto, y si es as, qu otras caractersticas incorpora el algoritmo de bsqueda. As por ejemplo, existe el algoritmo depth first search que es un algoritmo de ramificacin que selecciona como vrtice a explorar el creado ms recientemente, y tambin puede existir un algoritmo depth first search como el anterior, al que adems se le incorpora un procedimiento de agrupacin de vrtices equivalentes. Otro ejemplo se encuentra en Corts et al. (1993): despus de exponer una serie de procedimientos de bsqueda, comenta que todos se pueden referir a la bsqueda de una solucin factible, subptima u ptima, aunque tambin a la bsqueda de varias o todas las soluciones, y que la nica diferencia la constituye las soluciones que se van guardando. 3.3.1. Procedimiento del Museo Britnico (British Museum). Corts et al. (1993) y Winston (1994a) definen de forma semejante el procedimiento llamado del Museo Britnico (British Museum), como la tcnica que consiste en encontrar todas las soluciones factibles y seleccionar la de mejor funcin de evaluacin. Por tanto es una estrategia de bsqueda de la solucin ptima, aunque tambin se puede utilizar para hallar todas las soluciones ptimas, o una o varias soluciones factibles. Para
co
generar todas las soluciones factibles se puede recurrir a cualquier procedimiento que genere todos los estados del rbol de bsqueda, y en particular usualmente se cita, debido a su sencillez, la bsqueda en profundidad o en anchura (tcnicas que se describen en los apartados 3.3.3. y 3.3.4.). Como es previsible, al explorar todos los estados se produce la temida explosin combinatoria que hace que el procedimiento sea muy ineficiente. Por su parte, Rich & Knight (1994) definen el procedimiento, al que tambin denominan generacin y prueba (generate-and-ext), como una tcnica que consiste en generar una posible solucin y verificar si es una solucin objetivo: si lo es el procedimiento finaliza y si no lo es se generan ms soluciones. Si se generan soluciones de forma sistemtica y la solucin existe, el procedimiento es capaz de encontrarla. Como se puede comprobar es una forma exhaustiva de bsqueda en el espacio de estados del problema, y para estos autores la forma ms sencilla de implementacin es mediante una bsqueda en profundidad con backtracking. 3.3.2. Bsqueda aleatoria. La bsqueda aleatoria ha sido definida por Shirai & Tsujii (1987) (quienes la denominan bsqueda por prueba y error), por Rich & Knight (1994) y por Winston (1994a) (quien la llama bsqueda no determinista), y consiste en un procedimiento que selecciona al azar el prximo vrtice a expandir, es, por tanto, la generacin y exploracin arbitraria y aleatoria de estados hasta alcanzar un vrtice objetivo. Rich & Knight (1994) comentan que este procedimiento es igual que un algoritmo del Museo Britnico en el que la seleccin de vrtices, y finalmente la generacin de soluciones, se realiza de forma aleatoria. Por otro lado, para Winston (1994a) es interesante cuando no se tiene la certeza de qu bsqueda es mejor: la bsqueda en profundidad o en anchura. 3.3.3. Bsqueda en profundidad (depth first search o DFS). Entre otros, Musson (1971), Ibaraki (1976b, 1988), Even (1979), Barr & Feigenbaum (1981), Pearl (1984), Mompn et al. (1987), Shirai & Tsujii (1987), Mishkoff (1988), Companys (1989a), Gormen et al. (1990), Korf (1990), Corts et al. (1993), Ginsberg (1993), Liao (1994), Rich & Knight (1994), Winston (1994a) y Brunat (1996), definen el algoritmo de bsqueda en profundidad o bsqueda primero en profundidad (depth first o depth first search o DFS), tambin llamado linear search o single branch search por Ibaraki (1976b), estrategia de bsqueda LIFO por Pearl (1984) e Ibaraki (1988), bsqueda hacia el fondo por Mompn et al. (1987), bsqueda vertical por Shirai & Tsujii (1987), o estrategia en profundidad por Corts et al. (1993).
53
La bsqueda en profundidad consiste en explorar siempre un vrtice hijo del vrtice expandido ms recientemente (aunque no se especifica cmo se selecciona dicho vrtice hijo), y si ste no tiene sucesores, se realiza un proceso de backtracking reinicializando la bsqueda en el vrtice antecesor ms cercano que posea vrtices hijos sin explorar (aunque tampoco se especifica cmo se selecciona el nuevo vrtice hijo a explorar si existen varios candidatos); por tanto, primero se expande el vrtice generado ms recientemente (que coincide con el vrtice ms profundo en el rbol de bsqueda) y que todava no ha sido explorado. El procedimiento finaliza cuando se ha generado un vrtice objetivo o cuando se ha explorado sin xito todo el rbol de bsqueda. El grfico siguiente muestra un ejemplo de cmo acta la bsqueda en profundidad, en la generacin y exploracin de los estados de un espacio de bsqueda. Los nmeros asociados a cada estado especifican el nmero de orden en el que se explora el vrtice referenciado:
10
11
13
14
15
16
18
19
20 21
Algunos autores (Barr & Feigenbaum 1981, Mompn et al. 1987, Companys 1989a, etc.) proponen poner un lmite a la profundidad alcanzada por la exploracin, llamado profundidad de corte, ya que algunos espacios de bsqueda pueden tener una profundidad infinita; as, una vez se alcanza dicha profundidad, se retrocede y se contina por el vrtice ms cercano. Para Winston (1994a) este procedimiento constituye una buena idea cuando se tiene la confianza de que todas las trayectorias parciales llegan a callejones sin salida (vrtices terminales no objetivo) o conducen a un vrtice objetivo, despus de un nmero razonable de etapas. Mompn et al. (1987), Ibaraki (1988) y Corts et al. (1993) opinan que es un algoritmo ventajoso y eficaz cuando existen muchas soluciones aceptables, y que puede proporcionar rpidamente soluciones factibles aunque rara vez encuentra la solucin ptima.
Entre las posibles cualidades que presenta este procedimiento destacan dos (Ibaraki 1988, Korf 1990, Liao 1994 y Rich & Knight 1994): - es el ms econmico desde el punto de vista de la cantidad de memoria que se utiliza, aunque experimentalmente Liao (1994) ha encontrado que se tarda mucho ms que con otros procedimientos, como por ejemplo el best bound search (descrito en el apartado 3.3.6.), - si se tiene suerte puede encontrar una solucin sin tener que explorar gran parte del espacio de estados. Entre los inconvenientes se deben comentar los siguientes: - experimentalmente se ha encontrado que suele ser ms largo, en cuanto a tiempo de computacin y nmero de vrtices explorados, que otros procedimientos como por ejemplo el best bound search (descrito en el apartado 3.3.6.), - rara vez encuentra la solucin ptima, - usualmente necesita una profundidad de cne para evitar entrar en bucles infinitos. Varios autores comentan que un vrtice se puede evaluar mediante la distancia, en nmero de pasos, desde ste al vrtice inicial, y que entonces se selecciona para expandir aquel vrtice factible de mayor distancia. 3.3.4. Bsqueda en anchura (breadth first search o BFS). Diversos autores (Nilsson 1971, Even 1979, Barr & Feigenbaum 1981, Pearl 1984, Mompn et al. 1987, Shirai & Tsujii 1987, Ibaraki 1988, Mishkoff 1988, Companys 1989a, Gormen et al. 1990, Korf 1990, Corts et al. 1993, Ginsberg 1993, Rich & Knight 1994, Winston 1994a, Brunat 1996, etc.) han definido el algoritmo de bsqueda en anchura o bsqueda en amplitud o bsqueda primero en anchura (breadth first o breadth first search o BFS), tambin llamado estrategia de bsqueda FIFO por Pearl (1984) e Ibaraki (1988), bsqueda a lo ancho por Mompn et al. (1987), bsqueda horizontal por Shirai & Tsujii (1987), o estrategia en amplitud por Corts et al. (1993). La bsqueda en anchura consiste en explorar siempre un vrtice del nivel d (de profundidad d) antes que cualquiera del nivel d + 1; para ello, se expanden los vrtices en el orden en el que han sido generados (que coincide con la regla de examinar primero los vrtices ms superficiales); de todas formas, no se especifica el orden en el que se generan los vrtices sucesores de uno dado, y por tanto, no se especifica el orden de exploracin de los vrtices de un mismo nivel d. El procedimiento finaliza cuando se ha
55
generado un vrtice objetivo o cuando se ha explorado sin xito todo el espacio de bsqueda. El grfico siguiente muestra un ejemplo de cmo acta la bsqueda en anchura, en la generacin y exploracin de los estados de un espacio de bsqueda. Los nmeros asociados a cada estado especifican el nmero de orden en el que se explora el vrtice referenciado:
6 7
8 9
10 11
12 13
14 15
16 17
18 19
20 21
Para Winston (1994a), este procedimiento constituye una buena idea cuando se tiene la certeza de que el factor de ramificacin (nmero medio de vrtices descendientes de un vrtice no terminal) es pequeo. Por otro lado, Mompn et al. (1987) comentan que esta tcnica se adapta a problemas con pocos caminos de solucin. Entre las posibles cualidades que se presentan de este procedimiento (Barr & Feigenbaum 1981, Corts et al. 1993 y Rich & Knight 1994), destacan las siguientes: - no se queda atrapado explorando callejones sin salida, - si existe solucin se garantiza encontrarla, y si existen varias y slo se busca una, esta estrategia encuentra la de mnimo nmero de pasos (niveles). Entre los inconvenientes se debe comentar que si el factor de ramificacin es alto, la ocupacin de memoria y el tiempo de computacin son muy altos (Ibaraki 1988, Korf 1990, Corts et al. 1993 y Ginsberg 1993). Korf (1990) seala que un vrtice se puede evaluar mediante la distancia, en nmero de pasos, desde ste al vrtice inicial, y que entonces se selecciona para expandir aquel vrtice factible de menor distancia. Desde este punto de vista y como comentan Corts et al. (1993), este algoritmo es semejante a la bsqueda en profundidad excepto en la estrategia de ordenar para explorar los vrtices generados: en la bsqueda en
56
profundidad los vrtices acabados de generar se colocan al inicio de una lista ordenada, y en la bsqueda en anchura se aaden al final de dicha lista. 3.3.5. Bsqueda primero el de menor coste (uniform cost search o cheapest first strategy). La bsqueda primero el de menor coste (uniform cost search, uniform cost method, uniform cost procedure o cheapest first strategy), definida por Nilsson (1971), Barr & Feigenbaum (1981) y Pearl (1984) entre otros, consiste en un procedimiento de bsqueda en un rbol, en el que los arcos tienen asociados unos costes no negativos, que se basa en seleccionar los vrtices para expandir en orden no decreciente de g(n) (coste mnimo del camino desde el vrtice raz al vrtice n); es, por tanto, un algoritmo de bsqueda en anchura asociando a los arcos un coste no negativo y buscando el camino ms corto segn este coste. As, y segn Nilsson (1971) y Barr & Feigenbaum (1981), si los arcos del rbol de bsqueda tienen igual coste asociado, el algoritmo primero el de menor coste es el algoritmo de bsqueda en anchura; o ms en general, la bsqueda en anchura siempre se puede considerar un caso particular de la bsqueda primero el de menor coste. 3.3.6. Bsqueda primero el de mejor cota (best bound search). La bsqueda primero el de mejor cota (best bound search), citada por Ibaraki (1976b, 1988) (quien tambin la denomina minimum value search), Liao (1994), etc., consiste en un procedimiento de exploracin del rbol de bsqueda en el que se selecciona para expandir el vrtice de mejor cota global, que en la terminologa utilizada es el de mejor valor de g(n) + h(n), donde g(n) = g*(n) y h(n) nunca sobrestima a h*(n) y por tanto satisface la propiedad de admisibilidad. As, y como ocurre en todos los procedimientos anteriores, el movimiento de avance se realiza seleccionando para expandir el vrtice que parece ms prometedor de entre todo el conjunto de vrtices abiertos (vrtices generados pero no explorados) que se tiene hasta ese momento. Liao (1994) comenta que con la regla best bound search el nmero de vrtices tiende a incrementarse a medida que el programa se ejecuta, y que se requiere tanta cantidad de memoria central para recordar todos los vrtices del rbol, que limita el tamao de los problemas resolubles con esta regla. De todas formas, tambin expone que dicha regla es todava la estrategia de seleccin de vrtices ms usualmente utilizada. En este momento cobra mas sentido, si cabe, el comentario realizado en la introduccin del apartado 3.3., referente a lo poco precisas que son definiciones expuestas en la literatura para saber si se est refiriendo a un algoritmo concreto o a una regla de seleccin del siguiente vrtice a expandir dentro de un procedimiento general de
57
bsqueda. Adems, las denominaciones de los procedimientos existentes tampoco parece ser uniformes y nicas, ya que, por ejemplo, Ibaraki (1988) tambin denomina a este procedimiento bsqueda primero el mejor (best first search) cuando para la mayora esta denominacin corresponde a un procedimiento diferente, al que, por su parte, Ibaraki denomina bsqueda heurstica (heuristic search). 3.3.7. Bsqueda primero el mejor (best first search o BF). Varios autores, Barr & Feigenbaum (1981), Pearl (1984), Mompn et al. (1987), Ibaraki (1988), Korf (1990), Shapiro (1990), Corts et al. (1993), Ginsberg (1993), Rich & Knight (1994), Winston (1994a), etc., han definido el algoritmo de bsqueda primero el mejor (best first o best first search o BF), tambin llamado ordered state-space search por Barr & Feigenbaum (1981), bsqueda heurstica (heuristic search) por Ibaraki (1988), bsqueda ordenada por Shapiro (1990), u ptimo por niveles por Corts et al. (1993). El procedimiento de exploracin consiste en una bsqueda en el espacio de estados, en la que el movimiento de avance se realiza seleccionando para expandir el vrtice que parece ms prometedor de entre todo el conjunto de vrtices abiertos que se tiene hasta ese instante, y donde se utiliza para evaluar lo prometedor de un vrtice una funcin de evaluacin f(n) de la que se selecciona el valor mnimo. Como aclara Winston (1994a), el movimiento de avance se realiza sin importar donde est el vrtice seleccionado en el rbol parcialmente desarrollado, nicamente se tiene en cuenta el valor de f(n). Para Mompn et al. (1987) este tipo de estrategias pueden ser consideradas estrategias generales de bsqueda heurstica. Esta afirmacin es apoyada por la exposicin de Barr & Feigenbaum (1981) y Korf (1993), en la que destacan que la bsqueda en profundidad (depth first search), la bsqueda en anchura (breadth first search) y la bsqueda primero el de menor coste (uniform cost search), son casos especiales de la bsqueda primero el mejor (best first search): a) Para la bsqueda en profundidad (depth first search) se selecciona f(n) como menos el valor de la profundidad del vrtice n. b) Para la bsqueda en anchura (breadth first search) se toma f(n) como la profundidad del vrtice n. e) Para la bsqueda primero el de menor coste (uniform cost search) se elige f(n) como el coste del camino del vrtice inicial al vrtice n. Rich & Knight (1994) comentan que en ocasiones es interesante realizar la bsqueda de forma que los estados equivalentes no se exploren. Este comentario pone de manifiesto que, al menos, existen dos procedimientos de bsqueda primero el mejor que se
58
diferencian en el hecho de agrupar o no los estados equivalentes, o que existen dos tipos de procedimientos (aqullos que agrupan los estados equivalentes y aqullos que no los agrupan) que utilizan una estrategia de exploracin del rbol de estados del tipo primero el mejor. Korf (1993) estudia esta posibilidad como un mtodo para aumentar la eficiencia, por lo que puede deducir que, para este autor, el procedimiento de bsqueda primero el mejor original no incluye la agrupacin de estados equivalentes. Segn sea la funcin de evaluacin existen diferentes estrategias primero el mejor, que, como expone Pearl (1984), tienen en comn que el espacio de bsqueda es un grafo de estados, el vrtice seleccionado para la expansin es el de menor valor de f(n), y si existen dos caminos hasta el mismo vrtice se descarta el de peor valor de f(n); de todas formas, Pearl (1984) tambin realiza un comentario parecido al anterior, exponiendo variantes del algoritmo primero el mejor segn se realice o no la agrupacin de vrtices equivalentes y se manejen o no dichos vrtices. El procedimiento de bsqueda primero el mejor (best first search) presenta una serie de limitaciones, de las cuales Korf (1993) destaca las dos siguientes: por un lado, la gran cantidad de memoria necesaria para almacenar la parte de la arborescencia ya explorada, y, por otro, el elevado tiempo que se precisa para generar nuevos vrtices e insertarlos de forma ordenada en la lista de vrtices activos. 3.3.8. Bsqueda primero el mejor* (best first search* o BF*). Para Pearl (1984), la estrategia de bsqueda primero el mejor (best first search o BF) termina cuando encuentra una solucin factible; si se busca una solucin ptima se debe cambiar la condicin de finalizacin del procedimiento, y, al algoritmo resultante, Pearl lo denomina bsqueda primero el mejor* (bestfirst search* o BF*). 3.3.9. Bsqueda primero los mejores (best few). Mompn et al. (1987) definen el procedimiento de bsqueda primero los mejores (best few), como una tcnica que consiste en explorar un conjunto reducido de alternativas en paralelo, elegidas de acuerdo con la funcin heurstica f(n). Aunque Mompn et al. (1987) no especifican qu quieren decir con explorar alternativas en paralelo, existen dos posibles interpretaciones igualmente vlidas como procedimientos de bsqueda: por un lado, se pueden referir a que en cada etapa del procedimiento se explora el conjunto de los mejores vrtices segn el valor de la funcin de evaluacin f(n); y por otro, se pueden referir a explorar mediante procesadores en paralelo dicho conjunto de vrtices.
3.3.10. Parallel depth first search (PDFS). Tcnica de bsqueda descrita por Ibaraki (1988) que consiste en considerar en cada iteracin los p vrtices ms profundos, y en caso de empate los de mejor valor de f(n), y seleccionar para expandir aqul de mejor indicador f(n). Ibaraki comenta que si p = 1 este procedimiento equivale a la bsqueda en profundidad. Por tanto, parece ser que Ibaraki define ms especficamente que otros autores la bsqueda en profundidad, ya que segn se puede deducir, a igual profundidad selecciona para explorar aquel vrtice de mejor valor de f(n). 3.3.11. Floating down search (FDS). Procedimiento descrito por Ibaraki (1988) que consiste en dividir los vrtices activos (vrtices generados pero todava no explorados) en dos grupos: el conjunto S, formado por los vrtices con igual o mejor indicador f(n) que sus padres, y el conjunto L, compuesto por los vrtices con peor indicador que sus vrtices padres; y, a continuacin, seleccionar el mejor vrtice de S y aplicarle una bsqueda en profundidad sin backtracking, o, si S = 0, el mejor de L; y as sucesivamente. 3.3.12. Jump backtracking. Tcnica descrita por Ibaraki (1988) que consiste en alternar la bsqueda en profundidad con la bsqueda primero el mejor: se aplica una bsqueda en profundidad sin backtracking a un vrtice y, cuando sta acaba, se elige el siguiente a expandir mediante la bsqueda primero el mejor. 3.3.13. Procedimientos de bsqueda usualmente descritos en el rea de la inteligencia artificial. En el rea de la inteligencia artificial se han descrito un conjunto de tcnicas de bsqueda en espacios de estados, muchas de las cuales se pueden considerar procedimientos de bsqueda basados en la "fuerza bruta". En el apartado 3.6. se definen varias de estas tcnicas: iterative deepening (3.6.2.), iterative broadening (3.6.6.), los algoritmos Z y Z* (3.6.7.), los algoritmos A y A* (3.6.8.), el algoritmo IDA* (3.6.9.). los algoritmos de potencia heurstica (3.6.13.), los algoritmos B y B' (3.6.16.), etc.
60
3.4. Procedimientos de bsqueda basados en programacin dinmica (dynamic programming o DP). En pocas palabras y a modo de sntesis, la caracterstica ms importante que de cara a los procedimientos de resolucin enumerativos presentan las tcnicas de bsqueda basadas en programacin dinmica determinista finita (con un nmero finito de estados y de etapas), consiste en la agrupacin de estados equivalentes y la conservacin de la mejor trayectoria hasta alcanzar dicho estado segn una funcin de evaluacin objetivo. De todas formas, cabe destacar que la programacin dinmica (dynamic programming o DP), procedimiento que comienza a ser formalizado en 1957 por Bellman, es una tcnica mucho ms amplia y que un estudio riguroso de la misma requerira uno o diversos textos adhoc. Para exponer las bases y el funcionamiento de la programacin dinmica, se sigue a grandes rasgos el hilo argumenta! utilizado por Kaufmann & Cruon (1967), completado con diversos matices introducidos por otros autores que tambin han estudiado este tema: Morin (1978), Prawda (1981), Companys (1982), Kumar & Kanal (1983b), Pearl (1984), Ibaraki (1988), Gormen et al. (1990), Millier & Lieberman (1991), Taha (1991), Bautista et al. (1992), Corts et al. (1993), Winston (1994b), Dyer et al. (1995), White (1996), etc. Como ya se ha comentado, la forma que se utiliza en el presente texto para representar problemas de optimizacin combinatoria es mediante un grafo o rbol de estados OR. En terminologa propia de programacin dinmica, una decisin provoca la transicin de un estado a otro y una secuencia de decisiones constituye una poltica (una trayectoria) que determina una secuencia de estados. Toda poltica tiene un slo estado inicial y un slo estado final, y es factible si conduce del inicial al final. Por otro lado, cada poltica aplicada a un estado tiene un coste, y una poltica factible de mnimo coste se llama poltica (trayectoria) ptima. Entonces parece claro que resolver un problema de optimizacin combinatoria puede verse como el problema de encontrar polticas ptimas en una representacin en espacio de estados, es decir, hallar el camino extremo en una representacin en espacio de estados. Segn Kaufmann & Cruon (1967), para los problemas que se pueden representar en un espacio de estados polietpico (aunque como se matiza posteriormente slo es necesario que sea un espacio de estados sin circuitos) se puede aplicar el principio del ptimo (o de Bellman). Este principio se basa en la siguiente propiedad: considrese una trayectoria ptima entre dos puntos A y B, bajo ciertas condiciones, y en particular si se ha elegido adecuadamente el espacio en el cual se representan las evoluciones del sistema, toda porcin MN de esta trayectoria es ptima entre todas las trayectorias
61
posibles de M a N. Por tanto, el estado del sistema se debe caracterizar por completo: en cuanto a la evolucin futura del sistema, no debe haber lugar a distinguir entre dos transformaciones diferentes entre los periodos 1 a n, mientras stas conduzcan a una mismo estado xn. Principio del ptimo (o de Bellman): toda subpoltica Wjj(x, Xj) extrada de una poltica ptima ws,n*(xs, x n ) es ptima de x a Xj (Kaufmann & Cruon 1967); o dicho de otra forma, si el camino ptimo del vrtice xs al x n pasa por los vrtices x y Xj (xs, ..., x, ..., xi, ..., Xj, ..., xn), la parte del camino entre x, y Xj (x ..., xj, ..., Xj,) es el camino ptimo desde el vrtice x al vrtice Xj (Companys 1982). La consecuencia de este principio parece evidente: entre el conjunto de polticas que contienen a una subpoltica ws-k(xs, x^) dada (ptima o no), la mejor es aqulla que se obtiene al completar la subpoltica dada por una subpoltica ptima Wk,n*(Xk, xn), y, por tanto, si existen varias trayectorias para ir del estado x al estado Xj slo es necesario conservar la mejor de todas, que ser la que forme parte de la trayectoria ptima del estado x s al xn y que pase por x y Xj. De todas formas este principio no servira de nada si no fuese por el hecho de que las trayectorias pueden construirse mediante concatenacin de trayectorias ms cortas, y que cuanto ms corta es una trayectoria, ms fcil es saber si es ptima o no entre sus extremos. De aqu surge la necesidad de trabajar con una representacin del problema mediante un espacio de estados polietpico, aunque en realidad slo es necesario que dicho espacio no tenga circuitos, permitindose que algunos estados de una etapa no conduzcan a la siguiente sino a una etapa posterior en ms de un solo nivel. El principio de Bellman constituye la base del mtodo de la programacin dinmica y permite, considerando sucesivamente 1, 2, 3, ..., n periodos o etapas, construir progresivamente una poltica ptima resolviendo un problema al que se le hace corresponder una representacin en un grafo sin circuitos, con un coste asociado a cada arco y mediante la unificacin de los estados equivalentes. As, y como comenta Ibaraki (1988), si nicamente se busca un camino ptimo desde el vrtice inicial a un vrtice objetivo, en cada estado slo es necesario guardar el camino de mnimo coste desde el estado inicial hasta l mismo, pudindose eliminar todos los dems. Para este mismo autor, la programacin dinmica es el nombre general de los procedimientos que mejoran su eficiencia explotando esta propiedad. En programacin dinmica determinista el estado en la siguiente etapa est completamente determinado por el estado y la decisin de la etapa actual; en el caso probabilistico (que en este texto no se utiliza ni estudia) existe una distribucin de probabilidad para el valor posible del siguiente estado (Hillier & Lieberman 1991).
La programacin dinmica comnmente resuelve el problema en etapas, en cada una de las cuales interviene exactamente una variable de optimizacin (Taha 1991). Los clculos en las diferentes etapas se enlazan a travs de clculos recursivos de manera que se genera una solucin ptima factible a todo el problema, y, segn Companys (1982), dicha ecuacin funcional recurrente puede ser progresiva (dado un vrtice se decide a donde se va) o regresiva (dado un vrtice se decide de donde se viene). Dicha relacin recursiva identifica la poltica ptima para la etapa n, dada la poltica ptima para la etapa (n + 1) (Millier & Lieberman 1991). Como ya se ha comentado, la teora unificadora fundamental en la programacin dinmica es el principio de Bellman, que dice cmo se puede resolver un problema adecuadamente descompuesto en etapas a travs del uso de clculos recursivos. Por tanto, se puede definir la programacin dinmica como lo hace Ibaraki (1988): principio computacional que obtiene polticas ptimas resolviendo ecuaciones funcionales resultantes del principio de Bellman. Sin embargo, segn Taha (1991), aunque ofrece una estructura bien definida para resolver el problema en etapas, es "vago" en cuanto a la forma en que se debe optimizar cada etapa. En este momento se puede exponer la definicin que realiza Pearl (1984) de programacin dinmica: formulacin recursiva de una bsqueda en anchura que, para espacios de bsqueda con estructuras regulares, puede dar expresiones analticas para el coste o la poltica ptima. Companys (1982), Hillier & Lieberman (1991) y Winston (1994b) coinciden a grandes rasgos al exponer las caractersticas comunes que se presentan en la mayor pane de las aplicaciones resueltas mediante programacin dinmica; stas son: 1) En lugar de enfocar directamente el problema, optimizando su funcin econmica globalmente, se divide en N etapas, en cada una de las cuales se adopta una decisin que consiste en dar a una variable uno de sus posibles valores. 2) A cada etapa estn asociados unos estados. La decisin tomada en cualquier etapa ocasiona la transicin del estado de la etapa actual a otro estado de la etapa siguiente. A las transiciones (y a los estados) estn asociados valores econmicos cuya agrupacin constituye la funcin econmica global del problema. 3) Dado el estado en curso, la poltica o secuencia de decisiones ptima para las etapas que faltan es independiente de las decisiones adoptadas en las etapas ya consideradas. A esta idea se la conoce como principio de Bellman. 4) Se puede establecer una ecuacin de recurrncia que permita obtener la poltica ptima a partir de cada estado con N etapas pendientes, supuesta la poltica ptima a partir de cada estado con N - 1 etapas.
63
5) El problema es trivial para N = O N = 1,1o que permite inicializar la secuencia. 6) Cuando el nmero de etapas no est acotado, se puede introducir, a partir de la ecuacin de recurrncia descrita en 4), su equivalente en el lmite (generalmente una ecuacin funcional), que se resuelve mediante procedimientos iterativos (de todas formas, en este texto slo se considera un nmero de etapas finito). Segn Hillier & Lieberman (1991), una forma de clasificar los problemas de programacin dinmica determinista es por la forma de la funcin objetivo; se puede hacer otra clasificacin en trminos de la naturaleza del conjunto de estados, que pueden estar representados por variables continuas o discretas. Directa o indirectamente, otros autores (Prawda 1981, Companys 1982, etc.) proponen clasificaciones ms amplias y completas de los programas dinmicos; a continuacin se relata la clasificacin expuesta por Prawda en 1981 : - en cuanto a la forma cmo se combinan las eficiencias parciales del sistema, stas pueden aadirse en forma de suma, multiplicarse, o bien se puede calcular el mximo o mnimo de las mismas, - en cuanto a la optimizacin total de las eficiencias, se puede maximizar o minimizar, - en cuanto a la eficiencia en s, sta puede ser una funcin discreta o continua, - en cuanto al sistema que se est optimizando, ste puede tener restricciones o no tenerlas, - en cuanto al nmero de etapas, ste puede ser finito o infinito, - en cuanto a la certeza de la funcin de eficiencia, sta puede ser determinista o estocstica, - en cuanto a la manera de resolver el problema, sta puede ser en direccin de la entrada a la salida o de la salida a la entrada. Para Kaufmann & Cruon (1967), la programacin dinmica proporciona un mtodo de enumeracin particularmente ventajoso si se evita la repeticin de estados iguales; pero para Corts et al. (1993), aunque presenta la ventaja de eliminar trayectorias redundantes y agrupar estados equivalentes, el coste computacional de la deteccin de vrtices comunes a ms de un camino puede ser muy alto. Segn Winston (1994b), respecto a la enumeracin explcita, el nmero de clculos que hace la programacin dinmica es mucho menor. De todas maneras y como tambin comenta Ibaraki (1988), para problemas de dimensiones industriales el espacio de estados se hace tan grande que se necesita demasiado tiempo para resolver el problema exclusivamente con programacin dinmica. Por otro lado, Hillier & Lieberman (1991) comentan que como todo problema acotado de programacin entera pura tiene slo un nmero finito de soluciones factibles, resulta natural considerar el uso de algn tipo de procedimiento de enumeracin, y que
64
la programacin dinmica proporciona un procedimiento de este tipo aunque no es especialmente eficiente para la mayor parte de este tipo de problemas. Siendo clave la idea de detectar y agrupar estados equivalentes, existen formulaciones de algunos problemas mediante programacin dinmica en las que la deteccin de dichos estados es ms fcil que en otras formulaciones y en otros problemas. Este hecho explica que tradicionalmente se hayan tratado unos problemas mediante programacin dinmica (por ejemplo, el problema de la mochila) y otros no. Otro aspecto que influye en la utilidad de los procedimientos de programacin dinmica, adems de la fcil deteccin de estados equivalentes, es la frecuencia con la que se presentan estos estados. Un problema para el que funciona extraordinariamente bien la programacin dinmica es el problema de la mochila, caracterizando un estado con la capacidad de la mochila ya utilizada; en un ejemplar con 50 objetos y una capacidad mxima de 1.000, la programacin dinmica genera una arborescencia con una anchura mxima de 1.001 estados; en cambio, si este problema se resuelve mediante una exploracin exhaustiva del rbol formado, se puede alcanzar una anchura mxima de 250 estados. En este problema, adems de presentarse muy frecuentemente estados equivalentes, su deteccin es tambin muy sencilla.
3.5. Procedimientos de bsqueda basados en la poda de vrtices mediante cotas. Como ya se ha comentado en diversas ocasiones, se puede llegar a invertir mucho tiempo en la resolucin de problemas de optimizacin combinatoria mediante la enumeracin explcita: esta tcnica no es eficiente. Los algoritmos de resolucin deben identificar qu soluciones no son ptimas para eliminarlas de la enumeracin, y, as, surgen los procedimientos enumerativos basados en la poda de vrtices mediante cotas. En la resolucin de problemas de optimizacin combinatoria mediante este tipo de procedimientos, la mayor suposicin algortmica realizada es que existe otro problema de optimizacin, la relajacin o el problema relajado, cuya solucin ptima proporciona una cota inferior, en caso de minimizar, del valor de la solucin del problema original. Tambin se asume que es posible el uso de programas de optimizacin standard, o al menos ms sencillos, para resolver el problema relajado. Entre los procedimientos de bsqueda basados en la poda de vrtices mediante cotas, ms conocidos como de ramificacin (o de separacin) y acotacin, cabe destacar el procedimiento branch and bound, el branch and search, el branch and relax, el branch and reduce, el branch and prune, el depth-first I breadth-first I best-first I... branch and bound, el branch and bound con estrategia primero el de mejor cota local (locally best bound rule), el branch and cut, el branch and price y el branch and cut and price.
65
Como introducen Balas et al. (1996), con el objetivo de aprovechar al mximo la formulacin y la estructura combinatoria de los problemas de optimizacin combinatoria, la lnea ms usualmente seguida por los investigadores en los ltimos aos ha sido considerar clases de problemas con estructuras especiales e inventar procedimientos que obtengan el mximo provecho en cada caso. As se estn diseando y probando multitud de procedimientos de clculo de cotas superiores, procedimientos de acotacin, estrategias de ramificacin, etc., que intentan aprovechar las estructuras, dominancias y simetras propias de cada problema. 3.5.1. Branch and bound. El procedimiento de bsqueda en espacios de estados que se detalla a continuacin, la tcnica branch and bound, se puede considerar el procedimiento de bsqueda ms general expuesto hasta este punto, que utiliza la ramificacin (branch) y la acotacin (bound) en la exploracin del espacio de soluciones factibles. Cabe destacar que este procedimiento constituye la base sobre la que se sustentan gran pane de las dems tcnicas consideradas, y, por tanto, definiendo el branch and bound se estn definiendo muchas caractersticas de otros procedimientos. Como es ampliamente conocido, no se trata de un algoritmo, consiste en una forma general de enfocar la optimizacin de problemas de optimizacin combinatoria, y, de esta forma, se puede comenzar a hablar de un meta-algoritmo. De manera muy amplia y como comentan diversos autores (Bruin et al. 1988, Kernhuser & Wolsey 1989, Kumar 1990, Roca 1992, Jnger et al. 1994, Grtschel & Lovsz 1995, Gass & Harris 1996, Hoffman & Padberg 1996, Sierksma 1996, etc.), se puede definir el branch and bound como un procedimiento de resolucin de problemas de optimizacin, que consiste en la particin (ramificacin o separacin) sucesiva del conjunto de soluciones posibles en subconjuntos ms pequeos y en la resolucin del problema sobre cada subconjunto. Los problemas resultantes son llamados subproblemas o vrtices en el rbol de enumeracin y la idea consiste en que la solucin ptima del problema es la mejor entre las soluciones ptimas de los subproblemas. El procedimiento parcial descrito en el prrafo anterior constituye una tcnica de ramificacin (separacin) y exploracin del rbol de bsqueda casi siempre muy ineficaz debido al peligro que se produzca la temida explosin combinatoria. Para reducir el nmero de subproblemas a resolver, en el branch and bound habitualmente primero se calcula una solucin factible inicial mediante heursticas, que pasa a constituir la solucin preferible, para, posteriormente, calcular cotas del valor de la solucin ptima de los subproblemas definidos en los vrtices mediante la resolucin de unos problemas relajados (que son ms fciles de solucionar): si el valor de la cota de la solucin ptima de un subproblema no es mejor que el valor de la funcin objetivo de la
solucin preferible, el subproblema es descartado (podado). El procedimiento finaliza cuando todas las cotas calculadas para los subproblemas no son mejores que el valor de la solucin preferible. La utilidad del branch and bound (tcnica que debe su nombre al uso de cotas superiores e inferiores para podar) deriva en que, en general, muchas de las soluciones son podadas y slo se necesita enumerar y explorar una pequea fraccin del espacio de soluciones factibles (Pearl 1984, Ibaraki 1988, Kumar 1990 y Hoffman & Padberg 1996). Una vez se ha definido a grandes rasgos el funcionamiento bsico de los procedimientos branch and bound, a continuacin se procede a su descripcin detallada para un problema de minimizacin, tomando como hilo conductor, aunque no exclusivamente, la exposicin que realiza Toshihide Ibaraki en Ibaraki (1988). De todas formas cabe destacar que son muchos los autores que han definido y trabajado los algoritmos de bsqueda branch and bound: Corominas & Companys (1977), Corominas et al. (1984), Mompn et al. (1987), Ibaraki (1988), Companys (1989a), Kernhuser & Wolsey (1989), Corts et al. (1993), Ginsberg (1993), Jnger et al. (1994), Franco & Lpez (1995), Gangonells & Gmez (1995), Sierksma (1996), etc., y que tambin son referenciados en este texto. 3.5.1.1. Formalizacin. Como ya se ha introducido, para poder utilizar un algoritmo branch and bound en la resolucin de un problema de optimizacin combinatoria, el problema original, denominado PO segn la terminologa utilizada en Ibaraki (1988), se debe poder separar (en el sentido definido en el apartado 3.5.1.3.) en un conjunto de problemas parciales ms pequeos, denominados P, cuya resolucin equivalga a resolver el problema original PO; y esta idea debe aplicarse iterativamente hasta que la separacin resulte imposible (as por ejemplo, en el problema de la mochila 0-1 al fijar una variable a O a 1 se obtienen dos problemas parciales cuya resolucin equivale a resolver el problema original). Si slo se separa el rbol, se est realizando una enumeracin total del espacio de soluciones factibles; para construir un procedimiento que nicamente enumere y examine una pequea porcin del rbol de bsqueda, siendo podado todo el resto, se deben utilizar las siguientes propiedades: a) Si se llega a saber que un problema parcial P no contiene ninguna solucin mejor que la solucin preferible, no se separar ni se explorar.
67
b) Si la solucin ptima de un problema parcial P se puede obtener por otros medios, no es necesario seguir separando dicho subproblema P. c) Si ninguna de las soluciones contenidas en un subproblema P cumple las propiedades de obligado cumplimiento para toda o alguna solucin ptima del problema (en el sentido definido en el apartado 3.5.1.4.), P no se separar ni se explorar. Para implementar las dos primeras operaciones de podado, Ibaraki (1988) comenta que existen dos mtodos bsicos (descritos a continuacin como los expone dicho autor, aunque con ciertos matices): por un lado presenta el podado por cotas y por otro generaliza el concepto incluyendo el podado por dominancias. 1. Test de cota inferior2. Sean f(P) y g(P) los valores ptimos de los problemas P y "p , respectivamente, donde P es el problema relajado de P. Se describe un problema parcial P como el siguiente problema de optimizacin:
P: [MIN] (MAX) f(x)
X 6 S,
donde: S es el conjunto de soluciones factibles. X! es el conjunto de soluciones. S Xi, X, c X y Si = S n X. Cabe destacar que, como se puede comprobar aunque no es explcitamente expuesto en Ibaraki (1988), las separaciones se realizan en el conjunto de soluciones X. Por otro lado, se describe un problema relajado P de un problema parcial P como el siguiente problema de optimizacin:
' En el apaado 3.5.1.6. se expone con mayor precisin este test, asf como los procedimientos de relajacin utilizados.
68
El valor ptimo del problema relajado P constituye una cota inferior de f(P) -por ejemplo, en un programa entero se puede prescindir de la restriccin de integridad de las variables y obtener un programa lineal cuya solucin ptima constituye una cota inferior de la solucin ptima del programa entero-. Adems, se cumplen las propiedades siguientes (considerando desde este puntoo que la expresin g(P) se refiere a g(x)): 1. Si la solucin ptima de F cumple todas las restricciones de P -en el ejemplo propuesto, todas las variables son enteras-, entonces tambin es la solucin ptima dePj. 2. Si p i no tiene solucin factible, entonces P tambin es infactible. 3. Sea Z el valor de la mejor solucin conocida (solucin preferible) de P0; si g(P) > Z , entonces P seguro que no es mejor que Z , y, por tanto, se puede podar el problema parcial (subproblema) P. 2. Test de dominancia3. Supngase que los subproblemas se obtienen fijando las variables a sus posibles valores. Sean Pk y Pn dos problemas parciales obtenidos de PO al fijar las mismas variables a sus posibles valores, por tanto, Pk y Ph tienen el mismo conjunto de variables libres. Si cualquier solucin factible en Ph tambin es factible en Pk, y el valor de la funcin objetivo de Pk no es mayor que el valor de la funcin objetivo de Pn (f(Pk) ^ f(Ph)X entonces se dice que Pk domina a Ph. De esta manera, si existe un problema parcial Pk que domina a Ph y que ya ha sido generado, entonces Ph puede ser podado. A primera vista puede parecer que la definicin que se expone en Ibaraki (1988) del concepto de test de dominancia est incompleta, ya que no se comenta que, adems, se deben dar las mismas condiciones de contorno. La definicin que se realiza en prrafo anterior es correcta ya que las condiciones de contorno estn implcitas en la frase "... Si cualquier ...". Lo realmente difcil es poder comprobar dichas relaciones de dominancia; de todas formas, cabe destacar que para poder asegurar que un problema parcial Pk domina a otro Ph, basta con demostrar que el valor de la solucin ptima de PR no es mayor que el valor de la solucin ptima de Ph; pero es probable que para demostrar una cosa se necesite la otra. Existen otros autores, por ejemplo Bruin et al. (1988), quienes adems consideran con entidad propia el test de factibilidad, de forma que un subproblema puede ser eliminado si se puede probar que no contiene ninguna solucin factible. De todas maneras, esta forma de podar se puede considerar implcitamente tanto en el test de cota inferior como el momento de generar dichos subproblemas.
"9
Segn Ibaraki (1988), la descripcin del cuerpo de un algoritmo branch and bound consiste en especificar claramente todos los componentes que lo forman (el operador de ramificacin, el procedimiento de clculo de una cota inferior (g), el clculo de una cota superior (u), las relaciones de dominancia (D) y la funcin de seleccin del prximo vrtice a explorar) y las relaciones existentes entre ellos en el proceso de exploracin del espacio de soluciones factibles. Durante la computacin del algoritmo se generan y exploran vrtices (que se corresponden con problemas parciales o subproblemas) que pueden ser activos o no activos. Continuando con la nomenclatura expuesta en Ibaraki (1988), se debe definir: A: conjunto de vrtices activos. N: conjunto de vrtices generados hasta el momento. O: mejor solucin obtenida hasta el momento: solucin preferible. Z : valor de la solucin preferible. s(A): funcin de seleccin del prximo vrtice a explorar. g(Pj): cota inferior del vrtice Pj. u(Pj): cota superior del vrtice P. PjDP,: relacin de dominancia entre los vrtices Pj y P, por la que el vrtice Pj domina al vrtice P. G: conjunto de vrtices P para los que se ha calculado g(P). Una vez definida la nomenclatura bsica, a continuacin se expone un algoritmo branch and bound para la obtencin de la primera solucin ptima:
'^
Si existe Pk (* P) e N tal que PkDP ir a A8; si no ir a A7. Fase A7. Separacin. Separar P en P, P2, ..., Pik y hacer A = A u {P,, P2, ..., P ik } - {Pi} y N = N u {Pu, P 2 ,..., Pik}. Volver a A2. Fase A8. Finalizar P. Hacer A = A - {P}. Volver a A2. Fase A9. Fin. Si z < el mejor valor hallado es Z (que es igual a f(Po)) y O guarda la solucin ptima de PO; si no f(Po) = oo y PO es infactible. Para obtener todas las soluciones ptimas, el nico cambio a introducir es que en el test de cota inferior y en el de dominancia slo se deben eliminar los vrtices peores y no los que son de igual valor. A continuacin se incluye el diagrama de flujo del algoritmo branch and bound que se propone en Ibaraki (1988), para la obtencin de una nica solucin ptima en un problema de minimizacin.
71
Al
A={P0};N={P0};
Z =00; 0 = 0
1p
A2
A=0?
No
A2 P, = SA)
A3
Calcular u(P)
A8
Siu(P,)<Z : Z = u(P)yO={x}
Si
A4 Pi e G?
No
Si
AS
Calcular g(P) g(P)>Z?
No
Si
A6
3 Pk (* P) e N
tal que PkDP?
No
A7
Descomponer Pj = Au{Pi,,P i2 Pik-fPi N = Nu{Pil,P2,...,Pik}
Diagrama de flujo del algoritmo branch and bound para la obtencin de una nica solucin ptima en un problema de minimizacin. de Ibaraki (1988).
El algoritmo branch and bound propuesto permite disear multitud de variantes en funcin del orden en el que se ejecuten las diferentes fases, as como en la concrecin de stas. En cuanto al orden de ejecucin, en Ibaraki (1988) se proponen diversas variaciones:
79
- Si el test de dominancia es potente y su clculo es corto, se puede realizar la fase A6 antes de las fases A4 y A5. - Calcular g(P) y u(P) despus de la fase A7 y para todos los vrtices creados, en vez de hacerlo despus de seleccionar el vrtice a explorar; de esta manera se facilita el proceso de seleccin y acotado. - Aplicar el test de cota inferior a todos los vrtices activos, cuando stos son generados. - Trabajar con varias cotas inferiores y, por ejemplo, aplicar una sencilla en el momento de la seleccin (fase A2) y una cota ms sofisticada en el test de cota inferior (fase A5). - Verificar relaciones de dominancia slo con un subconjunto de los vrtices generados; segn Ibaraki (1988), esta tctica resulta ser ms rpida pero menos efectiva. Por otro lado, tambin se pueden disear diversas variantes en funcin de la concrecin de las diferentes fases (Corominas et al. 1984 y Corts et al. 1993). En los apartados 3.5.1.3. al 3.5.1.8. se exponen diferentes desarrollos expuestos en la literatura. A modo de ejemplo se puede comentar que la definicin de la fase de ramificacin (fase A7) es nicamente una posibilidad: tambin es posible no generar todos los problemas parciales sino slo algunos, con lo que, por un lado no se puede eliminar el vrtice precedente hasta que se hayan generado todos sus sucesores, y por otro, se debe registrar que descendientes han sido generados. Cabe destacar que en el algoritmo propuesto no se ha detallado ninguna fase de preproceso que ajuste y reduzca la formulacin. Adems se propone calcular cotas superiores en cada uno de los vrtices generados y no slo calcular una primera cota superior inicial nicamente en el vrtice PO, como ocurre en gran parte de la literatura. Companys (1989a) presenta un conjunto de caractersticas de los procedimientos branch and bound, entre las que cabe destacar las dos siguientes: por un lado, la definicin de los vrtices objetivo es dinmica y se modifica a lo largo de la exploracin: podemos alcanzar un vrtice objetivo y no saberlo hasta mucho ms tarde; y, por otro, un vrtice puede pasar de estar activo a estar cerrado en virtud de la informacin obtenida a lo largo de la exploracin en ramas totalmente ajenas a l. Como ya se ha introducido en el apartado 2.4. al comentar la representacin de los problemas de optimizacin combinatoria, en el momento de disear un algoritmo branch and bound es muy importante distinguir entre el rbol posible de bsqueda y el rbol construido en el proceso de exploracin: uno es el rbol implcito y el otro el rbol explcito. Como el espacio de bsqueda puede ser infinito o, aun finito, muy extenso, el problema de buscar soluciones se convierte en el de hacer explcita la mnima parte posible del grafo implcito que contiene un estado deseado. Como matizan Mompn et al. (1987) y Companys (1989a), el procedimiento genera un grafo G y un rbol T con los mismos vrtices que G, pero con la diferencia que en T cada vrtice tiene un nico
73
antecesor; G contiene todos los posibles caminos desde el vrtice raz s hasta cualquier vrtice n, T. en cambio, slo contiene el camino de menor coste o preferente desde s hasta n (si se agrupan los estados equivalentes). Antes de pasar a describir con detalle las diferentes fases del algoritmo, a continuacin se exponen dos algoritmos branch and bound tpicos en el rea de la investigacin operativa. Por un lado est el algoritmo de Land & Doig para programacin lineal entera, algoritmo que como comentan Corominas et al. (1984) se puede considerar como un precursor del procedimiento branch and bound; as, y como sealan Jnger & Thienel (1998), esta tcnica lleg a ser el mtodo seleccionado para implantar el procedimiento de resolucin branch and bound en el software comercial en los aos 60 y 70 (segn Sierksma 1996, actualmente los procedimientos branch and bound continan siendo el mtodo que ms usualmente se utiliza en la prctica para resolver programas lineales enteros y mixtos). El algoritmo de Land & Doig consta de las siguientes fases: Fase 0. Acotacin. Se resuelve el problema prescindiendo de las condiciones de integridad de las variables. Fase 1. Separacin. Si todas las variables que han de ser enteras lo son, fin y el ptimo es la mejor solucin entera encontrada; si no. se selecciona una de las variables que debe ser entera y no lo es (x), y se construyen los dos programas lineales resultantes de incorporar al programa lineal anterior cada una de las restricciones siguientes: Xj<e x > e + 1 donde e es la parte entera de x. Fase 2. Acotacin. Se resuelven los dos programas lineales. Fase 3. Seleccin. Entre todos los programas lineales todava no ramificados, se selecciona aqul para el cual la funcin econmica toma el mejor valor (el vrtice de mejor cota) y se vuelve a la fase 1. Por otro lado se describe el algoritmo de Balas para la resolucin de programas lineales binarios puros. Esta tcnica realiza una bsqueda en profundidad con backtracking; para seleccionar la variable a separar, define un ndice de imposibilidad de obtener una solucin factible para cada variable candidata y selecciona la variable de menor ndice (como comentan Corominas et al. 1984, tambin se puede tener en cuenta nicamente la
'
funcin objetivo y seleccionar la variable libre de menor coeficiente en valor absoluto en dicha funcin objetivo); para aumentar la eficiencia del algoritmo y evitar separaciones intiles, en cada vrtice se pueden hacer tests de eliminacin de variables: con ellos se puede reducir el nmero y complejidad de las restricciones, adems de fijar el valor de alguna variable (dichos tests, que en este texto se definen como tcnicas de reduccin, se presentan en el apartado 3.8.). 3.5.1.2. Particularidades de la funcin objetivo. En referencia a la funcin objetivo, una caracterstica a tener muy presente en este tipo de procedimientos de bsqueda es que sta no ha de cumplir ninguna condicin especial, no es necesario conocer su forma exacta y basta con poder acotarla y calcular su valor en un punto cualquiera (Corominas 1974). 3.5.1.3. Estrategias de ramificacin / separacin. Uno de los elementos ms importantes de los procedimientos branch and bound lo constituye la estrategia de separacin o ramificacin (branch), que especifica cmo separar un problema dado en un conjunto de problemas parciales ms pequeos, los subproblemas P, de forma que su resolucin equivalga a la resolucin del problema original P0. En realidad, la divisin se realiza sobre el conjunto de soluciones posibles y se resuelve el problema sobre cada uno de los subconjuntos generados. Segn comenta Ibaraki (1988), un mismo problema puede tener diferentes operaciones y estructuras de separacin; adems, la eleccin de la estrategia a utilizar influye grandemente en la eficacia del algoritmo branch and bound diseado. Recuperando la terminologa utilizada en la formalizacin del procedimiento branch and bound (apartado 3.5.1.1.), se describe un problema parcial P como el siguiente problema de optimizacin:
P: [MIN] (MAX) f(x) x e S,
donde: S es el conjunto de soluciones factibles. X es el conjunto de soluciones. S X, Xi c X y Si = S n X,. Como exponen Ibaraki (1988), Gendron & Crainic (1994) y Franco & Lpez (1995), las operaciones de separacin pueden verse como la descomposicin o divisin del
75
conjunto de soluciones X en un nmero finito de subconjuntos, Xn, X2, ..., X^, tales que:
Xj c Xj, U j= i k Xij
j = 1,2,..., k
S
Una vez realizada la separacin, se pueden definir los siguientes k problemas parciales Pjj, con j = 1,2,..., k:
Operacin de separacin aplicada al problema parcial Pi (X es separado en Xj (j=l.2.3.4), quienes entonces determinan Sjj), de Ibaraki (1988).
Segn se expone en Ibaraki (1988), Nemhauser & Wolsey (1989) y Gendron & Crainic (1994), en muchos casos la divisin de X en los subconjuntos X], X2, ..., Xk proporciona una particin de X, si, adems de cumplir X = Uj=i k Xj, todos los Xj son mutuamente disjuntos: Xj o Xs = 0 para j, s = l,...,k, j * s (propiedad que distingue una divisin de una particin); pero en otros casos no. A menudo tambin es posible identificar un conjunto Y, como resultado de estudiar el problema parcial P tal que ninguna solucin x e Y puede ser la solucin ptima de PO; en este caso la condicin Uj=i k Xj n S queda como sigue Uj = i k Xy z> S - Y,. Por otro lado, y aunque no es comentado en Ibaraki (1988), a veces se puede considerar que Xj Uj=i k Xy: por ejemplo, el fijar una variable a un valor concreto puede implicar
76
el fijar otras variables a otros valores, eliminado otros posibles y, por tanto, regiones del espacio de soluciones; de esta manera, si se realiza esta doble ramificacin la unin de los subconjuntos puede no ser X. Sea un problema con las variables binarias X|, x 2 y la restriccin X] + X2 ^ 1:
Pi2
X2
\r
Pai
Ejemplo de la relacin X, * Uj=i k Xj.
en este caso P = Pi u P2, pero si se realiza la siguiente ramificacin, que por otro lado es obligada, se obtiene que P & P\ u P2iComo se desprende de las exposiciones anteriores, y se comenta en Ibaraki (1988), los operadores de ramificacin (o de expansin segn Companys 1989a y Corts et al. 1993), adems de dividir el espacio de bsqueda en subespacios, tambin permiten eliminar algunos de stos al estudiarlos y comprobar que no es posible que contengan la solucin ptima de PQ. Recordando que se realiza la exposicin para un caso de minimizacin, cabe remarcar que la resolucin de P puede ser equivalente a la resolucin de Pi, P2,..., Pk, de forma que f(Pjj) > f(P); de esta manera f(P) > f(Po) y las soluciones de los subproblemas Py constituyen cotas superiores del problema global y de los subproblemas todava no explorados, por tanto pueden ser utilizadas para podar el rbol de bsqueda. En Ibaraki (1988) tambin se exponen algunos ejemplos de procedimientos de ramificacin aplicados a problemas muy conocidos: a) En el problema de la mochila 0-1, fijando el valor de una variable a O a 1 se obtienen dos problemas parciales. b) Los procedimientos de separacin para la resolucin de problemas de programacin entera utilizando tcnicas de ramificacin y acotacin, suelen ser de dos tipos:
''
- fijar valores para la variable x, desde su cota inferior L hasta su cota superior U; - restringir el valor de la variable x a: < I x I > U I + 1, donde IJ I es el resultado de resolver el correspondiente programa lineal. c) En problemas de secuenciacin u ordenacin, se suelen fijar las variables que pueden ir en la primera posicin, en la segunda, en la tercera,..., etc. Como se puede observar, en Ibaraki (1988) nicamente se expone la posibilidad de una particin del vrtice seleccionado. De todas maneras existe un conjunto de autores (Corominas et al. 1984, Mompn et al. 1987, Companys 1989a, etc.) que, adems de la particin, proponen que, por un lado, el procedimiento de separacin no sea necesariamente una particin: sea una divisin, y, por otro, que no se generen a la vez todos los sucesores de un vrtice, lo que puede llegar a ser computacionalmente menos costoso (Mompn et al. 1987). 3.5.1.4. Propiedades de la solucin ptima. Un concepto que no es introducido por Ibaraki (1988), aunque s por otros autores (Kubiak et al. 1997, Tadei et al. 1998, etc.), es la importancia de obtener propiedades que debe cumplir toda solucin ptima o tales que existe al menos una solucin ptima que las cumple. Como exponen estos autores, este hecho reduce considerablemente el nmero de soluciones a enumerar en un esquema branch and bound: reduce el tamao del rbol de bsqueda a hacer explcito. De esta forma, una solucin total o parcial es factible si cumple dichas propiedades; si no, se poda o, an mejor, no se genera en el proceso de separacin. Tadei et al. (1998) resuelven un problema at flow-shop de n piezas y dos mquinas, con diferentes instantes de disponibilidad de las piezas. Estos autores exponen dos nuevas condiciones que debe cumplir una solucin ptima: si se cumplen, respectivamente permiten eliminar o fijar una pieza del inicio de una pane de la secuencia, como integrante de una solucin ptima. 3.5.1.5. Clculo de la cota superior. En un problema de minimizacin, el disponer de una solucin factible es imprescindible para poder aplicar el test de acotado inferior e identificar, de esta forma, subproblemas/vrtices que no contienen soluciones ptimas para eliminarlas/os de la enumeracin. En la literatura publicada en el rea de la investigacin operativa, la mayora de textos proponen como primer paso en cualquier algoritmo branch and bound el clculo de una
7R '
solucin inicial factible de PQ mediante procedimientos heursticos, u(Po), solucin que es una cota superior de f(Prj) y que pasa a constituir la solucin preferible Z . Entre otros autores, Ibaraki (1988), Almiana & Pastor (1995), Nagar et al. (1996), etc., proponen calcular cotas superiores en cada uno de los vrtices P generados, u(P), y no nicamente en el vrtice PO- Realmente, la cota superior de P es la mejor (menor en el caso considerado) de todas las u(P) halladas mediante diferentes procedimientos heursticos y as u(P) se utiliza como el valor de la mejor solucin obtenida hasta el momento en el vrtice P. Segn Ibaraki (1988), Nagar et al. (1996) y Johnson et al. (1997), si se dispone de una buena cota superior -para lo cual, y como exponen Grtschel & Lovsz (1995), se necesitan heursticas de calidad- el podado de vrtices mediante el test de acotado inferior puede llegar a ser muy potente. Adems, y como es lgico, conviene conocer una solucin factible cuanto antes para comenzar a podar desde el inicio (Corominas et al. 1984 y Gendron & Crainic 1994). Los procedimientos heursticos utilizados para obtener soluciones factibles pueden ser de cualquier tipo, as es posible utilizar algoritmos heursticos derivados de procedimientos basados en el propio branch and bound o en tcnicas generales de exploracin del espacio de soluciones factibles. Concretamente, en The 13th Biennial European Conference on Artificial Intelligence, Schaerf (1998) comenta que la bsqueda local constituye un paradigma emergente para la bsqueda combinatoria, que recientemente ha demostrado ser muy eficiente para un gran nmero de problemas de scheduling; se basa en la idea simple de navegar en el espacio de bsqueda pasando iterativamente de una solucin a otra de su vecindario (compuesto por las soluciones que pueden ser obtenidas aplicando un cambio local a sta), y se propone la combinacin de tcnicas de bsqueda local como el recocido simulado, la bsqueda tab y varias clases de hill-climbing, con bsquedas con backtracking. En el rea de la investigacin operativa estas tcnicas no son tan recientes: en Fischietti et al. (1995), para resolver un modelo de programacin lineal entera se utiliza un algoritmo branch and cut (procedimiento descrito en el apartado 3.5.8.) en el que para obtener buenas soluciones factibles proponen aplicar procedimientos de "refinado" a soluciones factibles ya disponibles (posiblemente obtenidas mediante heursticas); por su parte, y con el objetivo de aumentar la eficacia del branch and bound que proponen, Guilln et al. (1995) desarrollan un procedimiento de generacin de soluciones factibles a un coste computacional muy bajo, que consiste en un algoritmo heurstico que implementa la idea de que soluciones cercanas a la ptima deben tener una estructura similar a la ptima (optimizacin local?). Por otro lado, Johnson et al. (1997) proponen una forma de realizar el menor trabajo posible si se utiliza la programacin lineal como procedimiento de acotado inferior.
79
Como el resolver un programa lineal usualmente requiere mucho esfuerzo computacional, se deberan utilizar los resultados del programa lineal tanto como sea posible y, en este caso, para obtener una solucin factible. La tcnica consiste en el redondeo sucesivo de las variables fraccinales hasta que se encuentra una solucin o hasta que se detecta infactibilidad; es obvio que el orden en el que se redondea tiene gran impacto en la posibilidad de encontrar una solucin entera, pero para algunos problemas de optimizacin combinatoria especficos, a veces es posible, basndose en su estructura particular, obtener una ordenacin que garantiza una solucin entera. Segn Ragsdale & Shapiro (1996), existe un concepto errneo, comnmente mantenido en el rea de la investigacin operativa, que considera vital el uso de una buena solucin inicial para resolver programas matemticos rpidamente, utilizando procedimientos branch and bound. Este concepto errneo consiste en que la eficiencia computacional del branch and bound mejora, o al menos no empeora, al especificar una buena cota inicial del valor de la funcin objetivo. Esta creencia se refleja en el manual de usuario de diversos paquetes comerciales y en diversos artculos de investigacin; sin embargo, aunque no es injusta, no es totalmente cierta: el uso de una mejor solucin inicial puede conducir a veces a una bsqueda branch and bound ms larga (Ragsdale & Shapiro 1996). Sea un problema de minimizacin en el que z es el valor de la solucin preferible. Se puede esperar que si se resuelve un problema con una Z inicial = +00 y con una z mejor, la segunda resolucin no necesite ms vrtices que la primera; sin embargo, como exponen Ragsdale & Shapiro (1996), se han descubierto casos en los que esto no ocurre y en los que en el segundo caso se necesitan muchos ms vrtices que utilizando Z = +. Para entender la razn de esta anomala, se puede considerar el impacto que tiene la mejor solucin en diferentes tipos de estrategias de seleccin del prximo vrtice a ramificar utilizadas por algunos paquetes informticos, como son la "mejor proyeccin", "pseudo-coste" y "error relativo" (todas ellas expuestas en el apartado 3.5.1.8.). Todas estas estrategias seleccionan vrtices basndose en una estimacin de la mejor solucin entera factible que se podra obtener de cada subproblema; estas estimaciones dependen directamente del mejor valor inicial o actual, y por tanto, el uso de una solucin inicial puede alterar el orden en el que son seleccionados los vrtices en un branch and bound, desviando la bsqueda del camino que gua a la solucin ptima y provocando la necesidad de un mayor nmero de vrtices. Respecto al trabajo de Ragsdale & Shapiro (1996) conviene hacer una precisin importante para evitar errores de concepto. El uso de una buena solucin inicial para resolver programas matemticos es muy importante de cara a realizar, lo antes posible, un eficiente proceso de podado. Otro aspecto consiste en el uso que se realiza de dicha informacin, y cmo el valor z es incorporado en las diferentes estrategias de seleccin del prximo vrtice a ramificar.
80
3.5.1.6. Procedimientos de acotacin / relajacin. Otra de las fases cruciales que es necesario especificar claramente en el diseo de un algoritmo branch and bound, es el procedimiento de clculo de la cota g (bound) inferior en caso de minimizacin y tambin denominado procedimiento de relajacin-, que especifica una forma de excluir un subproblema de la exploracin: cmo se identifican, para eliminarlos, los problemas parciales P que no contienen soluciones ptimas. Continuando con la terminologa utilizada en Ibaraki (1988), se denomina cota inferior del valor ptimo de un subproblema P (f(P)), al valor g(P) que cumple g(P) < f(P) para P e p (donde p es el conjunto de vrtices de la arborescencia). Como ya se ha comentado, para un problema parcial P se define una relajacin T \ como el siguiente problema de optimizacin:
Por tanto, g(P) es el resultado de resolver la relajacin p del subproblema P: el espacio de soluciones factibles se ampla, y, en caso de minimizar, el valor ptimo para P nunca excede al valor de f(P). Cabe recordar que la expresin g(P) se refiere a g(x). Como ya se ha expuesto en la formalizacin inicial, se cumplen las siguientes propiedades: 1 . Si P es infactible P tambin y se asume por convenio que g(P) = f(P) = <. 2. Asumiendo que el valor de la funcin objetivo g(x) es igual a f(x), si una solucin ptima de P es factible en P, tambin es solucin ptima de P; si g(x) * f(x) entonces esto no es cierto. 3. Sea Z el valor de la solucin preferible de PO, si g(P) > Z , entonces P se puede podar. De esta manera y como sealan Bjorndal et al. (1995), el procedimiento de acotado se basa en la resolucin exacta del problema relajado. De nuevo cabe destacar que para la
81
resolucin de la relajacin P , a veces es posible el uso de programas de optimizacin standard, o al menos ms sencillos. A continuacin se comentan diferentes procedimientos de acotacin expuestos en la literatura: a) Programacin lineal. En la resolucin de programas lineales mixtos se obtiene una cota inferior tpica, denominada por Ibaraki (1988) giJPi), al resolver el programa lineal resultante de relajar la condicin de integridad de las variables del correspondiente programa matemtico. A lo largo de la historia, el procedimiento de acotado basado en la resolucin de los programas lineales resultantes de dicha relajacin ha sido, parece ser, la tcnica ms utilizada (Marsten & Morin 1978, etc.). Incluso en nuestros das existen autores que habiendo experimentado con varias formas de obtener cotas inferiores, como por ejemplo la relajacin lagrangiana, comentan que obtienen los mejores resultados con la relajacin lineal (Dillenberger et al. 1994 en la resolucin de un problema de planificacin de la produccin mediante programacin lineal mixta y Johnson et al. 1997). De todas formas, esto no quiere decir que no existan problemas especficos para los que se obtienen mejores resultados con otros procedimientos de acotado. Segn Johnson et al. (1997), una gran parte del tiempo consumido por el branch and bound se invierte en resolver programas lineales; as, las mejoras aparecidas en los ltimos aos en la resolucin de estos programas matemticos, que han conseguido que en estos momentos la metodologa existente sea muy eficiente, han repercutido notablemente en la mejora de eficiencia de los procedimientos branch and bound. Adems, en estos momentos los cdigos modernos de programas lineales tratan fcilmente la adicin de filas (restricciones) y de columnas (variables), lo que es esencial para los nuevos procedimientos branch and bound denominados brandi and cut, branch and price y branch and cui and price, tcnicas descritas en los apartados 3.5.8., 3.5.9. y 3.5.10., respectivamente. Como exponen estos mismo autores, los mtodos de punto interior no son muy utilizados en branch and bound, ya que es molesto reoptimizar un programa lineal con un procedimiento de punto interior cuando se han aadido filas o columnas. A pesar de todo, y como el resolver un programa lineal usualmente requiere mucho esfuerzo computacional, Johnson et al. (1997) proponen utilizar los resultados de ste tanto como sea posible. As, la solucin del programa lineal se utiliza usualmente de tres maneras:
82
- el valor de la solucin es utilizado como cota del vrtice activo del rbol de bsqueda; - la informacin asociada a los costes reducidos se utiliza para fijar variables; - y la solucin del programa lineal tambin su utiliza para guiar la seleccin de los vrtices y las variables de ramificacin. b) Relajacin lagrangiana. El procedimiento de acotacin basado en la relajacin lagrangiana consiste en incorporar a la funcin objetivo algunas restricciones (segn Corominas 1974 y Hoffman & Padberg 1996, usualmente las que dificultan los clculos), dejando otras fuera, por ejemplo las de no negatividad. Sea un problema parcial P descrito como el siguiente problema de optimizacin:
P: [MIN] f(x) A-x>b x e X,,
donde X es el conjunto de soluciones. La relajacin lagrangiana se define mediante el siguiente problema de optimizacin: P i(X):[MIN] L(x; X) = f(x) + XT (b - A x) x e X Son varios los autores que comentan esta tcnica de acotacin (Corominas 1974, Ibaraki 1988, Dyer et al. 1995, Hoffman & Padberg 1996, Johnson et al. 1997, Marn 1997, etc.); entre stos, en Ibaraki (1988) se seala que el incluir restricciones en la funcin objetivo proporciona mejores cotas que las que se obtienen ignorando totalmente dichas restricciones. Adems, la mayora considera que es muy importante disponer de buenos multiplicadores de lagrange, ya que contra mejores son stos, las cotas que proporcionan son ms ajustadas; de todas formas presenta el inconveniente de que hay que hallar los valores de los multiplicadores A, (Corominas 1974), para lo cual, y segn Hoffman & Padberg (1996), se van resolviendo subproblemas hasta que se encuentran los valores ptimos de dichos multiplicadores. Por otro lado, Marn (1997) comenta que la tcnica de relajacin lagrangiana presenta la ventaja de que se pueden obtener diversas cotas: tanto en funcin de la formulacin como del conjunto de restricciones relajadas.
83
c) Relajacin subrogada (surrogate relaxation). La tcnica de relajacin subrogada, por ejemplo utilizada por Almiana & Pastor (1995) para resolver un problema de cubrimiento total, consiste en sustituir todas las restricciones del problema por una nueva restriccin obtenida como resultado de sumar todas las restricciones sustituidas. Inmediatamente se pueden plantear diversas cuestiones interesantes: por qu sumar todas las restricciones en una sola?, por qu no sumarlas en dos, o en tres, o ...?; por qu sumarlas directamente?, por qu no ponderarlas con unos pesos: a RI + R2 + y RS + ...?, el problema reside en hallar unos pesos a, , y,... que suministren la cota ms ajustada posible. Estudiando la literatura publicada sobre el tema, queda patente que en un mismo problema se pueden utilizar diferentes procedimientos de acotado, lo que influye en gran medida en la eficacia del algoritmo branch and bound diseado (Bjorndal et al. 1995). Por otro lado, y como comentan Ibaraki (1988). Gangonells & Gmez (1995), Grtschel & Lovsz (1995) y Washburn (1998) entre otros, el tiempo de computacin necesario para hallar g(P) es un factor crucial para determinar la eficacia del algoritmo; as, para que el podado de vrtices mediante el test de acotado inferior sea potente, se debe disponer de una g que pueda ser computada eficientemente y que proporcione una cota precisa (ajustada), lo contrario (o incluso la inexistencia de un principio de acotacin) puede proporcionar procedimientos extremadamente ineficientes (Corominas 1974 y Bjorndal et al. 1995). Washburn (1998) va ms all y matiza que, en algunas ocasiones y para problemas particulares, se obtienen mejores resultados con cotas ms imprecisas pero mucho ms rpidas de calcular (se sacrifica ajuste por velocidad): se puede producir una mayor ramificacin que con cotas ms ajustadas, pero el tiempo total de clculo es menor: uno de los argumentos que esgrime este autor es el siguiente: como muchas de las soluciones parciales son muy malas es fcil probar que no son ptimas, y es importante no invertir mucho tiempo comprobndolo. Apoyando las ideas expuestas en el prrafo anterior, Grtschel & Lovsz (1995) comentan que muchos de los desarrollos realizados para obtener soluciones a problemas difciles se han basado en la invencin de mejores relajaciones, aprovechando las propiedades estructurales y con rpidos algoritmos para solucionarlas. Por su parte, Johnson et al. (1997) recuerdan que como los programas lineales mixtos disponen de diferentes formulaciones en trminos de variables y restricciones, los programas lineales relajados de dichas formulaciones pueden ser enormemente diferentes en trminos de la calidad de las cotas que proporcionan; por tanto, tambin se puede intentar controlar el tamao del rbol proporcionando una buena formulacin inicial.
84
Una idea interesante expuesta en Corominas et al. (1984) y Gangonells & Gmez (1995), consiste en introducir el concepto de acotado dinmico. En un mismo algoritmo branch and bound puede haber varios procedimientos de acotado, tanto para un mismo vrtice de la arborescencia (aplicar varias tcnicas de acotado y asignar al vrtice la cota ms ajustada de entre todas las calculadas), como para los diversos vrtices generados (aplicar una tcnica a ciertos vrtices y otras a otros: por ejemplo, un procedimiento para los vrtices ms prximos al vrtice raz y, por comportamiento o tiempo de ejecucin, otro para los de mayor profundidad en la arborescencia). Corominas et al. (1984) matizan que incluso para hallar una cota de un vrtice mediante programacin lineal, en vez de resolver completamente el programa lineal resultante, se puede ir calculando una cota cada vez ms fina como resultado de ir haciendo iteraciones en el simplex-dual: se busca el empeoramiento que se obtendra si se hiciera una iteracin y si la cota es peor que la solucin preferible se poda el vrtice, si no se hace esta primera iteracin y se busca el empeoramiento que se obtendra si se hiciera una nueva iteracin, y si la cota es peor que ..., y as sucesivamente. Se trata de obtener cotas menos ajustadas pero ms rpidas de calcular, que permitan podar rpidamente los vrtices. Otro concepto a tener presente en los procedimientos de acotado es la existencia de dominancias entre cotas: en un problema de minimizacin, se dice que una cota domina a otra si la primera es siempre mayor o igual que la segunda y ambas no son siempre iguales (Marn 1997). Como exponen Bjorndal et al. (1995), otra de las funciones de las cotas, adems de la de podar vrtices de la arborescencia, es que son necesarias para certificar la calidad de los procedimientos heursticos, deriven o no de algoritmos branch and bound. Los algoritmos branch and bound, y en particular la potencia de sus procedimientos de acotacin y podado, pueden ser utilizados para otros procedimientos de bsqueda. Nagar et al. (1996) utilizan un procedimiento branch and bound para generar informacin que es usada para guiar la bsqueda en un algoritmo gentico. El procedimiento branch and bound se utiliza para generar informacin que asegure si cierta secuencia parcial, en un problema de secuenciacin_/7ou>-.s/Jo/7, puede generar o no soluciones ptimas cuando se complete en una solucin factible: por ejemplo, en un problema con 6 tareas, si se conoce que la cota inferior de una secuencia parcial (1, 3, 4) es mayor que la solucin preferible, no es necesario evaluar las secuencias resultantes a partir de esta secuencia parcial (1, 3, 4, 2, 5, 6), (1, 3, 4, 2, 6, 5) etc. 3.5.1.7. Dominancias. Comprobar si existen relaciones de dominancia entre vrtices de la arborescencia que representan el mismo estado, tambin persigue el objetivo de reducir la enumeracin
85
explcita mediante la poda de vrtices, al eliminar aqullos que son equivalentes; de esta manera, slo se generan soluciones parciales diferentes (Bosch 1993, entre otros). Segn Ibaraki (1988), el podado por dominancias es un recurso que puede llegar a ser tan potente como el test de cota inferior, pero segn Gendron & Crainic (1994) se utiliza raramente. Concretamente, se basa en la relacin de dominancia D siguiente: si PiDPj, es decir si P domina a Pj, y P ha sido generado, Pj puede ser eliminado, ya que seguro que la solucin que se obtenga de P no ser peor que la que se pudiera obtener de PJ: f(P) < f(Pj). Como exponen Bruin et al. (1988), un subproblema P domina a otro Pj si se puede probar que para toda solucin factible de Pj existe al menos una solucin factible de P con menor o igual valor de la funcin objetivo. Ibaraki (1988) propone un sencillo ejemplo aclaratorio: en la bsqueda del camino mnimo desde i hasta j, si se llega a k por dos caminos diferentes, el camino con menor valor asociado de i a k domina al otro. Kusiak et al. (1993) resuelven el problema de tecnologa de grupos mediante una heurstica basada en branch and bound. En su procedimiento de resolucin incorporan una de las relaciones de dominancia que se presentan ms comnmente en los problemas de optimizacin combinatoria: las simetras (Bosch 1993, Kusiak et al. 1993, etc.). Las simetras caractersticas del problema de tecnologa de grupos las tienen en cuenta realizando una ordenacin inicial, de manera lexicogrfica o no, de las mquinas a asignar (M), M?, Ma,...); de esta manera, ya no se generan vrtices equivalentes. Sea un problema en el que se han de asignar diversas mquinas a 3 celdas idnticas (Q, Ci, Ci): en una primera etapa la mquina M] se asigna directamente a Q y en la segunda se asigna iVb a Q o a 2'.
86
Cabe destacar que el tratamiento de las simetras tambin se puede realizar en el momento de formular el problema, de esta forma el procedimiento de exploracin ya no genera vrtices equivalentes que podran dar lugar a soluciones simtricas. Por otro lado, Ibaraki (1988) propone la idea de verificar relaciones de dominancia slo con un subconjunto de los vrtices generados; segn este mismo autor, esta tctica resulta ser ms rpida pero puede llegar a ser menos efectiva. 3.5.1.8. Estrategias de exploracin / seleccin. Las estrategias de exploracin de la arborescencia de bsqueda, tambin denominadas estrategias de seleccin del prximo vrtice a explorar, ya han sido introducidas en el apartado 3.2. al comentar las funciones de evaluacin. As, para evaluar los vrtices candidatos a ser explorados, ordenarlos y poder decir cul es el considerado como mejor o peor, usualmente se utiliza una estrategia de seleccin que se puede considerar que incorpora una funcin de evaluacin (tambin llamada indicador) que, a veces, utiliza informacin heurstica relativa al problema. Como exponen Nemhauser & Wolsey (1989), como introduccin se puede decir que los dos objetivos principales de esta fase son los siguientes: a) seleccionar el vrtice que con mayor posibilidad contiene la solucin ptima, aunque no se pueda probar; b) seleccionar el vrtice que ms rpidamente puede proporcionar una solucin factible mejor que la solucin preferible, lo que permite podar ms eficazmente. A diferencia de las fases anteriores del algoritmo branch and bound en las que se pretende identificar qu soluciones no pueden ser ptimas para eliminarlas de la enumeracin, la estrategia de exploracin determina nicamente en qu orden se generan y examinan los subproblemas, o, como se expone en Companys (1989a), cmo se hace explcita una porcin del grafo implcito suficiente para que incluya por lo menos una solucin ptima. De todas maneras, y aunque los algoritmos branch and bound siempre convergen en un nmero finito de pasos, su eficacia y el espacio de almacenamiento necesario dependen fuertemente de la estrategia de bsqueda seleccionada (Ibaraki 1988, Winston 1994a, Bjorndal et al. 1995, Gangonells & Gmez 1995, etc.). Las estrategias de seleccin del prximo vrtice a explorar no son nicas; de esta manera, y como sealan Nilsson (1971), Barr & Feigenbaum (1981), Hartnell (1986), Alvarez et al. (1988), Roca (1992), Kusiak et al. (1993), Jnger et al. (1994) y Grtschel & Lovsz (1995) entre otros, segn cules sean los criterios para elegir el siguiente
87
vrtice a explorar, se pueden obtener mltiples versiones diferentes del algoritmo branch and bound, unas ms eficientes que otras. Son muchos los autores que exponen estrategias de seleccin del prximo vrtice a explorar: Corominas et al. (1984), Alvarez et al. (1988), Ibaraki (1988), Nemhauser & Wolsey (1989), Corts et al. (1993), Winston (1994a), Fernndez & Companys (1995), Gangonelis & Gmez (1995), Balas et al. (1996), Nagar et al. (1996), Ragsdale & Shapiro (1996), Roucairol (1996), Sierksma (1996), Johnson et al. (1997), Kubiak et al. (1997), etc. Algunos de estos criterios de seleccin ya han sido expuestos en el apaado 3.3. al explicar los procedimientos de bsqueda basados en la "fuerza bruta" y algunos otros lo sern en el apartado 3.6. al introducir los procedimientos de bsqueda usualmente descritos en el rea de la inteligencia artificial. Cabe destacar de nuevo, que existen diversos procedimientos que han adoptado como rasgo diferenciador de los dems la estrategia de seleccin del prximo vrtice a explorar, con lo cual no est claro si su nomenclatura diferente se refiere al procedimiento de bsqueda o a la estrategia de seleccin como pane integrante de dicho algoritmo de bsqueda. A continuacin se exponen tres estrategias de bsqueda descritas por Ragsdale & Shapiro (1996), que incorporan diversos paquetes comerciales de programacin lineal mixta. Sea un problema de minimizar, donde ZPL es el valor de la cota inferior de un vrtice, Z' el valor de la cota superior y Z* el valor de la solucin ptima. Todas estas estrategias seleccionan vrtices, basndose en una estimacin de la mejor solucin entera factible que se podra obtener de cada problema candidato en la lista de vrtices. Sean eb, ep y er la estimacin de la mejor solucin entera posible que se podra obtener del vrtice i, utilizando respectivamente los estimadores "mejor proyeccin", "pseudo-coste" y "error relativo". a) Estrategia de la mejor proyeccin. Se define el estimador del vrtice i de la manera siguiente:
e i = ZPL, + p o,,
donde Zpy es el valor de la funcin objetivo relajada en el vrtice i, p es el factor de proyeccin, y 0 es la suma de las infalibilidades enteras en el vrtice i (a = Sj min(fi jf 1 - fy), donde fj representa la parte fraccional de la variable entera relajada j, en la solucin del programa lineal en el vrtice i). El factor de proyeccin p es un nmero que estima la cantidad por la que el ptimo relajado ZPL se espera que se degrade, por cada unidad de infactibilidad entera en el vrtice.
El valor p es igual para todos los vrtices estimados. Los paquetes comerciales proporcionan varios valores de p por defecto. Sin embargo, si se especifica una solucin inicial Z', se utiliza este valor para hallar el valor de p. Por ejemplo, en el paquete MIPII (Ragsdale & Shapiro 1996), se calcula como sigue:
min\ p=
Tambin es costumbre recalcular el valor de p siempre que se encuentra una solucin entera factible en el branch and bound. En el paquete MIPII se recalcula el valor de p para la solucin entera del vrtice k, mediante la siguiente expresin:
Cuando el valor de p vara, cambia el valor estimado de todos los vrtices representados por eb; se puede observar que el valor eb es una funcin lineal del valor de p, ya que tanto ZPL como 0 son constantes. Esta claro que si se selecciona un vrtice para ramificar basndose en el estimador eb, el valor relativo de los vrtices depende del valor de p. Sin embargo, p puede estar directa o indirectamente influenciado por Z' y por el proceso de podado. De esta manera, y como ya se ha comentado, el uso de una solucin inicial puede alterar el orden en el que son seleccionados los vrtices en un algoritmo branch and bound, provocando la necesidad de un mayor nmero de vrtices (Ragsdale & Shapiro 1996). b) Estrategia del pseudo-coste. Se define el estimador del vrtice i como sigue: ep = ZpLi + Ij min [PCLj - fi jt PCUj (1 - fi)], donde los valores PCLj y PCUj representan, respectivamente, el pseudo-coste (o penalizacin) inferior y superior para la variable j. PCLj es una estimacin de la cantidad por la que el ptimo del PL del vrtice se espera que se degrade (por unidad de infactibilidad), al forzar la variable j al valor entero inferior de su valor en el vrtice i. De forma similar, PCUj es una estimacin de la cantidad por la que el ptimo del PL del vrtice se espera que se degrade (por unidad de infactibilidad), al forzar la variable j al valor del entero superior de su valor en el vrtice i. Por defecto, cuando se inicializa el branch and bound en el paquete MPSX (Ragsdale & Shapiro 1996), todos los pseudo-costes son nulos. La estimacin de estas cantidades comienza a ser posible cuando se selecciona una variable de ramificacin. Por tanto, contra ms ramas adicionales se generan en el branch and bound, ms y ms pseudo-
89
costes son posibles para refinar los estimadores de los vrtices. De esta manera, mientras una solucin inicial puede reducir el nmero de ramas por la poda, simultneamente puede alterar los estimadores de los vrtices para futuras selecciones (Ragsdale & Shapiro 1996). c) Estrategia del error relativo. Se define el estimador del vrtice i como:
PL,-2'
Como se describe en el punto anterior, es posible un cambio en el valor de ep, dependiendo del valor de Z'; esto hace que el valor de er tambin pueda cambiar en funcin del valor de Z'. Una vez se ha seleccionado el vrtice a explorar, a menudo tambin se ha de concretar la variable con la que se efectuar la separacin. Aunque este paso puede ser diferente del de seleccionar el prximo vrtice a ramificar, tambin se podra utilizar para este fin. En la definicin que hacen Balas et al. (1996) de su procedimiento branch and cut (expuesto en el apartado 3.5.8.), para decidir el vrtice a ramificar se selecciona el de mejor cota; en cambio, para elegir la variable a separar se utiliza el criterio propuesto por Padberg & Rinaldi en 1991. Sean Xj el valor de las variables enteras que en la resolucin del programa lineal -resultado de la relajacin del programa matemtico- no proporciona un valor entero; sean fo y fi respectivamente, el mayor valor de Xj < 0,5 y el menor valor Xj > 0,5; se define el conjunto de variables candidatas para ser seleccionadas como sigue: 1= { i (1,..., p): fo/2 < x < (l+fi)/2 }, y se selecciona la variable de I con el mayor coeficiente (en valor absoluto) en la funcin objetivo. En la misma lnea argumenta!, Corominas et al. (1984) comentan que en el algoritmo de Balas se selecciona para ramificar el vrtice ms profundo, pero para elegir la variable a separar, se define un ndice de imposibilidad de obtener una solucin factible para cada variable candidata y selecciona la variable de menor ndice. Corominas et al. (1984) exponen que tambin se podra haber tenido en cuenta nicamente la funcin objetivo y se podra haber seleccionado la variable no fijada de menor coeficiente en valor absoluto en la funcin objetivo (como expone Sierksma 1996, en programacin lineal entera no est claro qu variable se debe elegir para ramificar y se suele seleccionar aqulla de mayor importancia en la funcin objetivo).
90
Otros criterios de seleccin de la variable a separar pueden ser los siguientes: - la variable que posee el mejor descendiente de todos los posibles (Ibaraki 1988), - la variable que posee el peor descendiente de todos los posibles, con la esperanza de que ste empeore tanto que no vuelva a ser necesario su exploracin (Corominas et al. 1984 e Ibaraki 1988), - la variable que posee el mejor conjunto promedio de vrtices descendientes (Ibaraki 1988), - la variable que consigue una mxima discriminacin entre los vrtices hijos resultantes, con el objetivo de no necesitar explorar los peores de ellos (Corominas et al. 1984 e Ibaraki 1988), - la variable que tiene un hijo con un valor de su cota, obtenida con el empeoramiento que se obtendra al hacer una primera iteracin del simplex, mejor (Corominas et al. 1984), - la variable para la que el valor resultante de resolver el programa lineal asociado, est ms cerca de tomar valores enteros (Ibaraki 1988), - la variable ms restrictiva, y, por consiguiente, susceptible de limitar ms el proceso de exploracin del rbol de soluciones (Fernndez & Companys 1995), - la variable que minimiza la dificultad de obtener soluciones factibles (Ibaraki 1988). Aunque est ampliamente extendido, en la mayora de ocasiones explorar el vrtice de mejor cota no es determinante para los procedimientos branch and bound; muchas veces es mejor utilizar predictores diseados especialmente para esta misin que incorporan otras informaciones heursticas o estructurales acerca del problema a resolver. Por otro lado cabe destacar que, aunque de forma tmida, Pearl (1984) e Ibaraki (1988) describen procedimientos en los que las estrategias generales de bsqueda comienzan a tener carcter dinmico al utilizar dos o ms criterios de seleccin, en funcin del estado de evolucin de la bsqueda o en funcin de los subconjuntos de vrtices entre los que se realice dicha seleccin (aspecto de gran importancia en la funcin general de evaluacin y seleccin de vrtices diseada en el apartado 7.4.4.). 3.5.1.9. Clasificacin de los algoritmos branch and bound para problemas de permutacin. Kohler & Steiglitz (1974) exponen la caracterizacin de los algoritmos de enumeracin implcita branch and bound para problemas de permutacin (problemas de optimizacin combinatoria cuyo conjunto de soluciones posibles est formado por la permutacin de un conjunto de valores y que incluyen a los problemas de flow-shop y de asignacin cuadrtica como casos especiales), en trminos de una tupia de seis parmetros (Bp,S,E,D,L,U). De esta forma se puede realizar una clasificacin general de este tipo de
91
algoritmos, as como obtener un algoritmo general que permite obtener otros en funcin de la seleccin del valor concreto de cada uno de estos parmetros. En la caracterizacin presentada, (BP,S,E,D,L,U), cada uno de estos seis parmetros de clasificacin representa lo siguiente: - Bp es la regla de ramificacin para el problema de permutacin, que genera descendientes inmediatos al dividir el subproblema tratado en subconjuntos disjuntos. La generacin de descendientes inmediatos, que es total, se realiza en orden lexicogrfico. - S es la regla de seleccin del prximo vrtice a ramificar de entre el conjunto de vrtices activos actuales. Segn estos autores, aunque existen muchas otras variaciones posibles, las reglas de seleccin ms comunes son las siguientes: - S = LLB (Least Lower-Bound Rules): seleccin del vrtice activo con menor cota inferior: en caso de empate se selecciona el primer vrtice generado, LLBpipoo el ltimo, LLBtiFO- S = FIFO (Firs-In-First-Oiit Rule): seleccin del vrtice activo que fue generado primero. - S = LIFO (Las-In-Firsr-Out Rule): seleccin del vrtice activo que fue generado ltimo. - D es la funcin de dominancia de vrtices. Se dice que un vrtice v\ domina a otro vrtice v2, V]Dv 2 , si la mejor solucin completa incluida en v\, xi, no es peor que la mejor solucin completa incluida en v2, x2: f(xi) < f(x2), en problemas de minimizacin y siendo f la funcin objetivo. - L es la funcin de acotado inferior, que debe cumplir las propiedades siguientes: - Si v2 es un descendiente de v\, entonces L(v2) > L(VI), en problemas de minimizacin. - Para cada solucin completa v, L(v) = f(v), siendo f la funcin objetivo. - U es el valor de la solucin preferible. - E es el conjunto de reglas para utilizar la funcin de dominancia D y el coste de la solucin preferible U, en la poda tanto de vrtices acabados de generar como de vrtices actualmente activos. Sea vr el vrtice actual de ramificacin, vr(1 un descendiente inmediato de vr y va un vrtice de la lista actual de vrtices activos. E representa varios subconjuntos de las siguientes cuatro reglas:
92
(i) U/DBAS (upper-bound tested for dominance of descendants of branching node and members of currently active set). Si L(vrd) > U entonces vrd es podado despus de ser generado; si L(va) > U entonces va es eliminado de la lista de vrtices activos. (ii) AS/DB (active node set tested for dominance of descendants of branching node). Se comprueba si alguno de los vrtices de la lista de vrtices activos domina al vrtice acabado de generar: si vaDvrd entonces vrd es podado despus de ser generado. (iii) BFS/DB (branched-forn node set tested for dominance of descendants of branching node). Se comprueba si alguno de los vrtices previamente generados domina al vrtice acabado de generar: si vpDvrd entonces vrd es podado despus de ser generado. (iv) DB/AS (descendants of branching node tested for dominance of currently active node set). Se comprueba si el vrtice acabado de generar domina a alguno de los vrtices de la lista de vrtices activos: si vrdDva entonces va es eliminado de la lista de vrtices activos. Si E contiene reglas AS/DB y DB/AS, entonces el conjunto de vrtices activos puede depender del orden en el que estas reglas son aplicadas. Estos autores comentan que la caracterizacin propuesta permite describir un algoritmo general que puede ser extendido para describir diversos procedimientos (por ejemplo, con Bp, S = FIFO, E = {AS/DB, DB/AS}, D, L, U, se pueden describir tcnicas de programacin dinmica) e incluso algoritmos branch and bound heursticos. Por otro lado, cabe destacar que la clasificacin presentada para problemas de permutacin es clara y muy compacta. 3.5.2. Branch and search. Djerdjour (1997) resuelve el problema de la mochila multidimensional cuadrtico, aplicando un procedimiento enumerativo de ramificacin y acotacin, que denomina branch and search. Esta tcnica de bsqueda consiste en un branch and bound tpico, con una estrategia de bsqueda primero en profundidad. 3.5.3. Branch and relax. Hentenryck (1995), un investigador procedente del rea de la inteligencia artificial, presenta el trmino branch and relax como un trmino general para referirse tanto a los procedimientos branch and bound (expuestos en el apartado 3.5.1.) como a las tcnicas branch and prune (introducidas a continuacin en el apartado 3.5.5.). Concretamente dice: "Branch and relax (often called branch and bound for optimization problems and
93
branch and prune for decision problems) is a well-known technique to solve combinatorial search problems. It consists ..." (Hentenryck 1995, p. 569). 3.5.4. Branch and reduce. Ryoo & Sahinidis (1996) utilizan el trmino branch and reduce para referirse a un procedimiento de exploracin del espacio de soluciones factibles mediante la ramificacin, acotado y podado, que, concretamente, definen para resolver problemas de optimizacin global. De todas formas, y como ellos mismos comentan, aunque el branch and reduce resuelve problemas de optimizacin global lo interesante es intentar adaptarlo para resolver problemas de optimizacin combinatoria. Segn Ryoo & Sahinidis (1996) branch and reduce toma su nombre de la combinacin del anlisis de intervalos y dualidad, con conceptos de branch and bound. Branch and reduce integra un branch and bound tradicional junto a una amplia variedad de tests de reduccin de rangos. Estos tests (que presentan inecuaciones vlidas basadas en la optimalidad y criterios de factibilidad, y tcnicas de reduccin de rangos utilizadas para reducir el tamao del espacio de bsqueda en problemas de optimizacin global) se aplican a cada subproblema en el rbol de bsqueda, para contraer el espacio de estados y reducir el gap de la relajacin. Otro componente crucial es la implementacin de tcnicas heursticas para la resolucin aproximada de los subproblemas de optimizacin, con el propsito de obtener una mejor solucin preferible del problema. Por ltimo, y segn los mismos autores, se incorpora un conjunto de esquemas de ramificacin que aceleran la convergencia de las estrategias de ramificacin standard. La estrategia de seleccin incorporada por Ryoo & Sahinidis en su procedimiento es la bsqueda primero el de mejor cota (denominada por stos best bound first). Siendo Z el valor de la solucin preferible y con el objetivo de minimizar, el algoritmo branch and reduce se puede describir brevemente como sigue: Paso 0. Inicializacin. Sea la cota superior z = +. Poner el vrtice raz en la lista Activos. Paso 1. Finalizacin. Eliminar todos los vrtices de la lista Activos tales que su cota inferior sea > z . Si Activos = 0, parar y la solucin preferible es ptima. Paso 2. Seleccin de subproblemas. Seleccionar un vrtice de la lista Activos segn la estrategia de seleccin y eliminarlo de la lista.
"
Paso 3. Pre-proceso. Ajustar las variables acotadas del subproblema seleccionado usando reduccin de rango basado en la factibilidad. Paso 4. Acotado. Resolver el subproblema seleccionado o acotar su solucin. Si la solucin encontrada es factible y su valor de la funcin objetivo < Z . tomarla como solucin preferible y actualizar z ; ir a paso 5. Si el valor de su cota inferior es > Z , ir a paso 1. Paso 5. Acotado superior opcional. Aplicar heursticas de bsqueda local para encontrar una solucin factible mejor; si se obtiene, tomarla como solucin preferible y actualizar z . Paso 6. Post-proceso. Ajustar las cotas de las variables usando tcnicas de reduccin de rangos. Si la reduccin de rango es exitosa en al menos una de las variables del subproblema, entonces reconstruirlo usando las nuevas variables acotadas e ir a paso 4. Paso 7. Separacin. Ramificar el subproblema obteniendo un conjunto de nuevos subproblemas, incluirlos en la lista Activos e ir a paso 1. De esta manera, las principales aportaciones de este procedimiento las constituyen los pasos 3, 5 y 6. 3.5.5. Branch and prune. Wagner (1975) y Hentenryck et al. (1997) comentan el algoritmo branch and prune, aunque de forma no coincidente: mientras que Wagner expone que el branch and bound tambin se puede llamar branch and prune, Hentenryck et al. definen esta tcnica como un nuevo procedimiento de bsqueda en el espacio de estados. Concretamente, Hentenryck et al. (1997) consideran que su procedimiento branch and prime, caracterizado por los mismos autores como un mtodo para resolver problemas de bsqueda global, es una tcnica diferente a lo que habitualmente se puede conocer como branch and bound "... Operationally, Newton [el nombre del paquete de software] uses a branch and prune algorithm which was inspired by the traditional branch and bound approach used w solve combinatorial optimization problems ...", Hentenryck et al. (1997), p. 797. De todas formas, el procedimiento branch and prune que definen es una tcnica de ramificacin y acotacin para permitir la poda del espacio de bsqueda, al que, en este caso, se le incorporan tcnicas de propagacin de restricciones en cada uno de los vrtices de la arborescencia, y, ms concretamente, tcnicas de reduccin de los intervalos de los valores definidos para cada variable de forma que se cumpla una
95
condicin de consistencia local llamada caja-consistencia (en el apartado 3,8,2. se introducen tcnicas de reduccin de este tipo provenientes del rea de la inteligencia artificial). Por otro lado, Granvilliers (1998) describe de forma semejante un algoritmo branch and prune aplicado en la resolucin de sistemas polinomiales no lineales. Como se puede comprobar, las descripciones de los procedimientos branch and prune y branch and reduce para la resolucin de problemas de optimizacin global, muestran que ambos algoritmos son altamente coincidentes. Por otro lado, este tipo de procedimientos son usualmente denominados interval branch and bound algorithms, lo que indica que, en realidad, pueden ser considerados algoritmos branch and bound que incorporan tcnicas de reduccin de intervalos. 3.5.6. Depth-first I Breadth-first I Best-first I... branch and bound. Kumar (1990), Sarkar et al. (1991), Korf (1993) y Zhang & Korf (1995), comentan que la tcnica conocida como depth-first branch and bound (DFBnB) es un procedimiento branch and bound en el que se selecciona para separar el vrtice generado ms recientemente, incorporando, por tanto, la estrategia de seleccin depth first (ya definida en el apartado 3.3.3. al exponer la bsqueda en profundidad). Zhang & Korf (1995) matizan que para aumentar la eficiencia de este procedimiento, los vrtices hijos generados del ltimo vrtice separado deben ser explorados en orden creciente del valor de una funcin de evaluacin. Kumar (1990) tambin define el procedimiento denominado best-first branch and bound, como un algoritmo branch and bound en el que la estrategia de seleccin de los vrtices a separar consiste en seleccionar el vrtice de mejor valor de un indicador (que para Kumar, y en este caso, est constituido por el valor de la cota inferior), as se utiliza la estrategia best first (ya definida en el apartado 3.3.7. al exponer la bsqueda primero el mejor); como seala Kumar, si la funcin de acotado da una buena aproximacin el procedimiento es muy eficiente, pero sino es muy ineficiente. A pesar de que nicamente se han definido como tales los procedimientos depth-first branch and bound y best-first branch and bound, se puede considerar con total seguridad que existen muchos otros procedimientos de bsqueda a los que se les ha incorporado un procedimiento de acotado y podado como el branch and bound, o que dichas estrategias han sido incorporadas a un procedimiento branch and bound. As por ejemplo, no resulta difcil imaginar la existencia de un procedimiento branch and bound en el que la estrategia de seleccin de los vrtices a ramificar sea la utilizada en la bsqueda en anchura (con lo que se obtendra un breadth-first branch and bound), la de la bsqueda primero el de menor coste (uniform-cost branch and bound o cheapest-first branch and bound), la de la bsqueda primero el de mejor cota (best-bound branch and
"6
bound), la utilizada en diversos procedimientos de bsqueda usualmente descritos en el rea de la inteligencia artificial y expuestos en el apartado 3.6. (la del algoritmo iterative deepening (iterative-deepening branch and bound), la del algoritmo A* (A* branch and bound), la del algoritmo IDA* (IDA* branch and bound), etc.), e incluso, por qu no, la incorporacin de un branch and bound en los procedimientos de bsqueda basados en programacin dinmica (dynamic-programming branch and bound). Por ltimo, cabe destacar que para la resolucin de problemas de dimensiones interesantes, hoy en da la mayora de procedimientos diseados suelen incorporar indefectiblemente procedimientos de acotado y podado. 3.5.7. Branch and bound con estrategia primero el de mejor cota local (locally best bound rule). Liao (1994) propone una nueva estrategia de seleccin de los vrtices a explorar, denominada regla el de mejor cota local (locally best bound rule). Esta estrategia selecciona para separar el vrtice de mejor cota global entre un conjunto reducido de vrtices que, al igual que ocurre en el caso de la bsqueda primero el de mejor cota, es el de mejor valor de g(n) + h(n), donde g(n) = g*(n) y h(n) nunca sobrestima a h*(n), o. para procedimientos en los que las funciones g(n) y h(n) no tienen sentido, el de mejor valor de l(n), donde l(n) es una cota global de la mejor solucin alcanzable desde el vrtice n. La particularidad de esta estrategia consiste que, en este caso, el movimiento de avance no se realiza seleccionando para ramificar el vrtice que parece ms prometedor de entre todo el conjunto de vrtices abiertos que se tiene hasta ese momento, sino de entre los de un subconjunto de dichos vrtices abiertos. Sea un problema de optimizacin que debe ser minimizado, la idea de la bsqueda el de mejor cota local es la siguiente. En cualquier momento en el que los vrtices guardados en la memoria central exceden un rango pre-especifcado (Liao cita como ejemplo 200 vrtices), se ordenan en una lista en forma no decreciente de sus cotas inferiores y se divide sta en dos partes: la parte que contiene los primeros vrtices de la lista (como por ejemplo cita Liao, un porcentaje del 30%) se contina almacenando en la memoria central, mientras que el resto de vrtices se guarda en una memoria auxiliar como el disco duro de un ordenador. El procedimiento de ramificacin, acotacin y poda (branch and bound) contina manipulando nicamente los vrtices existentes en la memoria central hasta que sta est vaca: todos los vrtices han sido eliminados o guardados en la memoria auxiliar; en este instante, uno de los conjuntos de vrtices almacenados en la memoria auxiliar es seleccionado y estos vrtices son incorporados a la memoria central para continuar con el procedimiento branch and bound. El proceso
"'
contina hasta que no existe ningn conjunto de vrtices guardados en la memoria auxiliar. Siendo z el valor de la solucin preferible, el algoritmo se puede describir brevemente como sigue: Etapa 1. Initialization. Sea la cota superior 2 = . Etapa 2. Bsqueda del vrtice de ramificacin. Entre todos los vrtices de la memoria central, seleccionar el de menor valor de la cota inferior. Etapa 3. Ramificacin, acotado y podado. Ramificar totalmente el vrtice seleccionado y descartarlo de la arborescencia; calcular una cota inferior de los nuevos vrtices generados: si se obtiene una nueva solucin factible, calcular su valor objetivo, compararlo con Z y si tiene un valor menor retenerla como solucin preferible y actualizar z ; podar aquellos vrtices de la memoria central cuya cota inferior sea mayor o igual que z . Etapa 4. Actualizar la lista de vrtices de la memoria central. Eliminar los vrtices podados y guardar los recin generados. Etapa 5. Test. (a) Si el nmero de vrtices en la memoria central es mayor que el rango especificado, ir a la etapa 6; si no, continuar. (b) Si hay vrtices en la memoria central, ir a la etapa 2; si no, continuar. (c) Si hay vrtices guardados en la memoria auxiliar, ir a la etapa 7; si no, ir a la etapa 8. Etapa 6. Ordenar y guardar vrtices. Ordenar los vrtices de forma no decreciente del valor de su cota inferior; dividir la lista de vrtices en dos partes mediante un porcentaje especificado; mantener la primera parte en la memoria central y guardar la segunda parte en la memoria auxiliar. Ir a la etapa 2. Etapa 7. Recuperar un conjunto de vrtices. Descartar los conjuntos de vrtices de la memoria auxiliar cuyo primer integrante tenga una cota inferior mayor (o, aunque el autor no lo especifica, igual si slo se busca una solucin ptima) que z ; entre los conjuntos de vrtices restantes, seleccionar aqul cuyo primer vrtice tenga el menor valor de la cota inferior; copiar en la memoria central aquellos vrtices de dicho conjunto cuya cota inferior sea menor (o igual) que Z y eliminar los vrtices restantes de este conjunto. Ir a la etapa 2. Etapa 8. Parar.
98
Liao (1994) comenta algunas caractersticas de la tcnica descrita. Aunque dentro de los conjuntos de vrtices no seleccionados para ser incorporados en la memoria central es probable que existan vrtices que pueden ser podados, esto no se hace ya que consume mucho tiempo; en principio, slo se eliminan conjuntos completos de vrtices. Por otro lado, para poder podar rpidamente dichos conjuntos de vrtices o parte de un conjunto en el momento de incorporarlos a la memoria central, es recomendable guardarlos en orden no decreciente del valor de su cota inferior. Si el rango especificado es suficientemente grande para que la memoria central pueda acomodar en todo momento la parte generada de la arborescencia, el procedimiento descrito es un branch and bound que utiliza como estrategia de exploracin la regla best bound. Uno de los principales problemas a resolver en el momento de utilizar este procedimiento consiste en determinar un valor apropiado para el rango de vrtices que se han de conservar en la memoria central. Intuitivamente el rango debera ser tan grande como permitiera la memoria central, pero, segn Liao, esta intuicin es incorrecta y para aclararlo enumera las ventajas de utilizar un rango grande y uno pequeo. Las ventajas de utilizar un rango grande son las siguientes: 1.- Como el vrtice de ramificacin es seleccionado entre los de la memoria central, para un rango grande tiende a tener menor valor de la cota; por tanto se tiende a ramificar menos vrtices y el tiempo de computacin se reduce. 2.- Cuando el nmero total de vrtices es menor que el rango, no se precisa ordenar ni guardar vrtices en la memoria auxiliar; esto representa un ahorro de tiempo de ordenacin y de acceso a la memoria auxiliar. 3.- Como la poda se realiza en la memoria central, cuando se encuentra una solucin mejor se pueden podar muchos ms vrtices con un decremento en el tiempo de bsqueda y de ordenacin. De todas formas Liao (1994) tambin describe ventajas al usar rangos pequeos: L- Como el vrtice de ramificacin es seleccionado slo entre los de la memoria central, un rango pequeo comporta menos tiempo de bsqueda; esto representa un gran ahorro de tiempo de computacin ya que la operacin de bsqueda se utiliza frecuentemente. 2.- La operacin de actualizacin se realiza cuando se encuentra una solucin factible mejor y los vrtices son podados; como esta operacin se realiza en los vrtices de la memoria central, tardar menos contra menor sea el rango. 3.- Cada vez que se deben guardar vrtices en la memoria auxiliar, se requiere una operacin de ordenacin; esta operacin requiere menos tiempo para el mismo
""
nmero total de vrtices cuando el rango es pequeo, ya que es de orden O(n log n). De todas formas y tanto para determinar el mejor valor del rango, como el del porcentaje de vrtices que se retienen en la memoria central (el otro gran problema a resolver cuando se utiliza esta tcnica), Liao (1994) lo hace de forma emprica. Por ejemplo, para el algoritmo de Balas utiliza rangos de 3.000, 1.000, 600, 200 y 50 vrtices, reteniendo en la memoria central el 10, 30 o el 50% de la lista de vrtices; en este caso Liao comenta que parece que funciona mejor reteniendo el 30% de los vrtices de la lista y trabajando con un rango de 200 o 50 vrtices. Para este mismo algoritmo, Liao (1994) comenta que, segn muestran algunos resultados experimentales, la aplicacin de esta estrategia de seleccin no slo hace que se utilice mucha menos memoria central que con la regla best bound, sino que adems en muchos casos se utiliza menos cantidad de computacin. 3.5.8. Branch and cut4. Como exponen Bjorndal et al. (1995), en la resolucin de problemas de optimizacin combinatoria utilizando tcnicas enumerativas, el procedimiento de acotado es vital en el desarrollo de un algoritmo eficiente. La actuacin de los procedimientos de branch and bound suele proporcionar buenos resultados cuando las relajaciones proporcionan cotas muy cercanas al ptimo, pero en los casos en los que se presenta un gap importante entre la cota y la solucin ptima, estas tcnicas pueden resultar poco eficientes. Bjorndal et al. (1995) exponen de forma actualizada la combinatoria polidrica, un campo de investigacin cuyo objetivo es el de proveer de un conjunto finito de restricciones lineales que encierren al conjunto de soluciones posibles en un poliedro -en realidad, en un politopo o poliedro (politopo acotado) mnimo)- hallando posteriormente y con programacin lineal, un vrtice ptimo. En la prctica se presentan dos problemas: por un lado, es extremadamente difcil conocer todas las restricciones lineales necesarias para definir el poliedro mnimo (teora polidrica), y, por otro, el nmero de restricciones es exponencial y aunque slo un nmero polinomial de stas son necesarias para definir la solucin ptima, no se sabe cules son (computacin polidrica). Las consideraciones anteriores han convergido en aproximaciones basadas en planos de corte, como el branch and cut.
Como exponen Jnger & Thienel (1998). en Caprara & Fischetti (1997) se muestra una reciente y completa bibliografa sobre algoritmos brunch und cul.
100
Como relatan Hoffman & Padberg (1996) y Jnger & Thienel (1998), los algoritmos de planos de corte tiene su origen en 1958, cuando Gomory desarrolla un algoritmo de planos de corte para problemas de programacin entera (segn Gass & Harris 1996, se puede definir "corte de Gomory" como una restriccin lineal que es incluida en un problema de programacin lineal, para reducir el espacio de soluciones sin eliminar ningn valor entero). Como describen brevemente Jnger et al. (1994), Grtschel & Lovsz (1995), Hoffman & Padberg (1996) y Sierksma (1996) entre otros, el mtodo de planos de corte de Gomory consta de dos fases iterativas: Fase 1. Programacin lineal: resolucin del programa lineal resultante de relajar la condicin de integridad de las variables; si en la solucin ptima del programa lineal las variables que tienen carcter entero lo son, ya se ha alcanzado la solucin ptima del problema original. Fase 2. Planos de corte: se resuelve un problema de identificacin de facetas, cuyo objetivo consiste en encontrar una inecuacin lineal que elimine la solucin fraccional lineal encontrada, pero sin eliminar ninguna solucin de la regin factible original5. Como Bjorndal et al. (1995) matizan, ltimamente se est trabajando en buscar cortes que no slo eliminen soluciones no factibles (fraccinales en programacin lineal entera), sino tambin soluciones factibles no interesantes. El algoritmo contina hasta que, o se encuentra una solucin factible, o el programa lineal es infactible, o no se pueden generar ms cortes. Como ya se ha comentado, la idea consiste en reducir progresivamente el espacio de soluciones, de forma que la solucin entera ptima corresponda a un punto extremo del espacio de soluciones reducido. Considrese el siguiente programa lineal binario que se presenta en Johnson et al. (1997):
La solucin ptima del programa lineal es x* = (74/93, O, 1, 0). Como que \\ = 1 implica que todas las otras variables son iguales a O y como mucho dos de las otras variables pueden ser iguales a 1, la restriccin 2 Xj + x2 + x3 + x4 < 2 es una restriccin vlida; adems, sta es un corte violado ya que no es satisfecha por x*. Jjicluyendo esta restriccin en el programa lineal, la cota resultante es ms ajustada.
En Corominas et al. (1984 ) se describe el procedimiento concreto de generacin de planos de corte de Gomory.
101
Jnger et al. (1994) exponen el procedimiento de una forma ms general: se comienza con un pequeo subconjunto de las restricciones de un problema de optimizacin lineal, cuyo conjunto de restricciones es demasiado grande para ser representado explcitamente, y se halla el ptimo sujeto a dichas restricciones; se comprueba si alguna de las restricciones no consideradas no se satisface; si existe alguna restriccin violada, se adiciona al programa lineal y se resuelve de nuevo; si no se viola ninguna restriccin, la solucin obtenida tambin resuelve el programa original. Cabe destacar que el procedimiento no requiere una lista explcita de todas las restricciones que definen el programa original, nicamente requiere un procedimiento que identifique inecuaciones que son validas para el programa original y que son violadas por la solucin actual. Con el objetivo de asegurar la resolucin ptima de un problema de optimizacin combinatoria, la generacin de planos de corte se puede incorporar a un procedimiento de branch and bound, con el objetivo de obtener cotas ms ajustadas al reducir el conjunto de soluciones factibles en el programa lineal sin eliminar ninguna solucin vlida para el problema original (Corominas et al. 1984), obtenindose de esta manera el algoritmo llamado branch and cut. Como exponen Jnger et al. (1994), la primera combinacin de inecuaciones vlidas y mtodos de branch and bound fue realizada por Miliotis en 1976 para el problema TSP; el uso de facetas que definen planos de corte y el uso de generacin automtica de planos de corte en combinacin con branch and bound, fue formulado y publicado en 1984 por Grtschel et al. para un problema de ordenacin lineal; y, por otro lado, el trmino branch and cut fue introducido por Padberg y Rinaldi en 1991 para resolver el TSP. Diversos autores han utilizado y definido el procedimiento branch and cut (Hoffman & Padberg 1993, Jnger et al. 1994, Escudero et al. 1995a, Fischetti et al. 1995, Grtschel & Lovsz 1995, Saltzman 1995, Balas et al. 1996, Hoffman & Padberg 1996. Johnson et al. 1997, etc.), y, aunque presentan algunas diferencias, se puede definir el procedimiento bsico de branch and cut como lo hacen Johnson et al. (1997). Para Johnson et al. (1997), el procedimiento branch and cut es simplemente la modificacin del algoritmo branch and bound, en el que, despus de solucionar el programa lineal y no habindose podado el vrtice, si se encuentran una o ms restricciones violadas (planos de corte), se incluyen en la formulacin del programa lineal y ste es resuelto de nuevo; si no se encuentra ninguna, se ramifica. De esta manera, la generacin automtica de cortes no slo se realiza antes de comenzar el branch and bound, sino en cada vrtice del rbol de enumeracin; adems, y para que este procedimiento tenga xito, es importante que los cortes generados en un vrtice del rbol sean vlidos para todos los dems vrtices, lo que ha limitado el tipo de cortes que
102
se han utilizado en branch and cut (Jnger et al. 1994, Saltzman 1995 y Balas et al. 1996). Otros autores incorporan diversos refinamientos, aunque son caractersticas que tambin pueden ser incorporadas en cualquier otro esquema de ramificacin y acotacin, mejorndose, presumiblemente, los resultados obtenidos. Segn Fischetti et al. (1995) la ejecucin del branch and cut mejora si se es capaz de encontrar pronto "buenas" soluciones factibles: proponen un procedimiento heurstico que primero obtiene una solucin factible a partir de la ltima solucin parcial, para, posteriormente, aplicarle procedimientos de refinado. Para Hoffman & Padberg (1996) los principales componentes del branch and cut son los procedimientos de reformulacin automtica, heursticas que proporcionan buenas soluciones enteras factibles, procedimientos de fijacin de variables (por implicaciones lgicas o de coste reducido) y el hecho, cada vez ms importante, de aprovechar las estructuras y caractersticas propias del problema, adems de los procedimientos intrnsecos de generacin de planos de corte. Por su parte, Escudero et al. (1995a) utilizan un procedimiento de branch and cut en el que explotan tcnicas de preproceso: procedimientos de reduccin del tamao del problema va identificacin de restricciones redundantes y fijacin de variables, y procedimientos de reforzamiento de las condiciones del problema; de igual manera que Hoffman & Padberg (1996), tambin destacan la importancia de obtener propiedades que permitan fijar nuevas variables, detectar infactibilidades e incluso identificar nuevas propiedades. Por su parte, Jnger et al. (1994) incluyen el uso de diversas heursticas para calcular el primer valor de la solucin preferible, procedimientos de clculo de soluciones factibles en cada vrtice aprovechando la fase de planos de corte (explorando las soluciones fraccinales del programa lineal), tcnicas de optimizacin local para mejorar la solucin preferible obtenida por el procedimiento anterior (con un control del tiempo dedicado a la optimizacin local fijo, segn un nmero predeterminado de iteraciones, o mediante una estrategia dinmica en funcin de la solucin obtenida del programa lineal respecto a la mejor solucin factible, etc.), procedimientos de abandono de la fase de generacin y adicin de planos de corte si la cota superior no disminuye significativamente, tcnicas para fijar variables basndose en sus costes reducidos y en implicaciones lgicas desprendidas de explorar las estructuras particulares del problema, etc. Segn la opinin de Johnson et al. (1997), el branch and cut generaliza, tanto los algoritmos de planos de corte puros en los que los cortes son incluidos en el vrtice raz hasta que se encuentra una solucin ptima del problema, como el branch and bound. En esta tesis se argumenta la opinin contraria, siendo el procedimiento branch and bound el que generaliza a todos los dems.
Como exponen Balas et al. (1996), a grandes rasgos y para un problema de minimizacin, el algoritmo branch and cut est formado por las siguientes fases: Fase Fase Fase Fase 1. Iniciacin. 2. Seleccin del vrtice. 3. Clculo de la cota inferior. 4. Ramificar o generar cortes? (decisin de la que depende en gran parte el xito del algoritmo). Si se generan cones, ir a la fase 5. Si se ramifica, ir a la fase 6. Fase 5. Generar planos de corte vlidos para el programa original, pero violados por la solucin de la relajacin. Ir a la fase 3. Fase 6. Ramificacin. Ir a la fase 2.
Adems, y como estos mismos autores comentan, en el esqueleto fundamental del procedimiento branch and cut descrito, se pueden incorporar, como ya se ha comentado, diversos refinamientos: uso de heursticas, preproceso, fijacin de variables, etc. A continuacin se describe un ejemplo concreto. Hoffman & Padberg (1993) resuelven un problema de horarios de tripulaciones areas mediante un branch and bound que genera planos de corte, adems de utilizar procedimientos de reformulacin, heursticas y programacin lineal. Concretamente, el procedimiento branch and cut propuesto para resolver el programa lineal binario resultante tiene cuatro componentes bsicos: un preprocesador que ajusta y reduce la formulacin (se transforma el problema en una representacin equivalente fijando variables, eliminando restricciones que resultan ser redundantes, etc.), una heurstica que proporciona buenas soluciones factibles rpidamente, un procedimiento de generacin de cortes que ajusta el programa lineal relajado y una estrategia de ramificacin que selecciona la variable de separacin y determina el rbol de bsqueda. La siguiente figura muestra un diagrama de flujo del branch and cut diseado por Hoffman & Padberg (1993), donde z es el valor de la solucin preferible y ZpL es el valor de la solucin del programa lineal.
104
Diagrama de flujo del procedimiento branch and cui, de Hoffman & Padberg (1993),
Del grfico anterior cabe destacar las subfases Incremento en ZPL?, Fijar variables, Se han fijado suficientes variables?. Aunque no queda claramente especificado en el texto, se puede suponer que "Incremento en ZPL?" se refiere a algn procedimiento que tiene en cuenta el coste reducido, que permite asegurar que una variable nunca estar en la base ya que entonces ZPL > Z ; as, siempre que es posible se utiliza un procedimiento para fijar variables que puedan tener implicaciones para otras, de forma que si se fija un % especfico de las variables que quedan por fijar, el control se enva de nuevo al preproceso y si no a la heurstica. Cuando se alcanza la fase Generador restricciones, ya se dispone de una buena formulacin del problema y se ha resuelto el programa lineal, y en este momento se generan y aaden nuevas restricciones basadas en la teora de poliedros que dan cortes polidricos. El programa lineal es resulto de nuevo entrando en el bucle representado en la figura anterior.
105
Con el objetivo de trabajar con arborescencias de tamao reducido, Hoffman & Padberg (1993) tambin proponen, aunque sin especificar cmo, una estrategia de ramificacin que vara dependiendo de las caractersticas de la solucin actual del programa lineal. Entrando en un mayor grado de detalle y tambin a modo de ejemplo, a continuacin se exponen las particularidades del algoritmo branch and cut descrito por Balas et al. (1996): - Para seleccionar el vrtice a ramificar se utiliza una estrategia de control best-bound (de todas formas, Jnger et al. (1994) comentan que existen diversos procedimientos: bsqueda en anchura, en profundidad, best-bound, etc.). - La seleccin de la variable a separar se realiza utilizando el criterio propuesto por Padberg & Rinaldi en 1991: - sea x la solucin del ltimo programa lineal; - determinar el mayor valor de Xj < 0,5 y el menor valor Xj > 0,5; sean fo y f| dichos valores respectivamente; - definir el conjunto de variables candidatas para ser seleccionadas como: - seleccionar la variable e I con el mayor coeficiente (en valor absoluto) en la funcin objetivo. Por su parte, Jnger et al. (1994) comentan una mayor variedad de estrategias de seleccin de la variable de ramificacin. Sea i la solucin del ltimo programa lineal resuelto: 1) Seleccin de una variable con valor cercano a 0.5 que disponga del mayor coeficiente en la funcin objetivo. Se busca L y H tales que L = min {0.5, max{ x e I xe<0.5,ee E}} y H = max{0.5, min{ 3F e I i e >0.5, e e E}}. Sea C = {e-e E l 0.75 L < x e ^ H + 0.25 (1 - H)} el conjunto de variables cuyo valor es cercano a 0.5. Se selecciona de C la variable con mayor coeficiente en la funcin objetivo. 2) Seleccin de la variable con el valor obtenido del programa lineal ms cercano a 0.5. 3) Seleccin de la variable fraccional con el mayor coeficiente en la funcin objetivo. 4) Si hay variables fraccinales que son iguales a 1 en la solucin preferible, seleccin de la de mayor coeficiente en la funcin objetivo. 5) Seleccin de la variable fraccional ms cercana a 1 .
106
- Para evitar que aumente desmesuradamente el tamao del programa lineal y ste sea inabordable, se van eliminando restricciones resultantes de cortes (como hacen Jnger et al. 1994, quienes especifican que eliminan aquellas restricciones dominadas o que no definen facetas, y que por tanto ajustan dbilmente, y aquellas que son poco importantes). Segn Hoffman & Padberg (1993), Jnger et al. (1994) y Johnson et al. (1997), la fase ms importante en los procedimientos de planos de corte, reside en el hecho de encontrar restricciones violadas dada una solucin del programa lineal que no satisface todas las restricciones del problema original. Debido a que el cierre convexo de puntos factibles que se puede asociar a un problema combinatorio es un poliedro que puede ser descrito por un conjunto finito de inecuaciones lineales, tal restriccin debe existir, aunque saber cul es, es muy difcil. En particular, si todas las variables en la restriccin Ej aj Xj < b deben ser no negativas, el corte es dado por j [ajj Xj < LbJ, donde Led es la parte entera o redondeada hacia abajo del nmero real a; cuando |_bJ < b, la restriccin ajusta el programa lineal. Esta idea est fcilmente extendida a restricciones con variables enteras y reales, y aunque los algoritmos puros de planos de corte que incorporan dichos cortes han proporcionado muy lenta convergencia y no son prcticos, los resultados empricos obtenidos con estos cortes en un algoritmo branch and cut han sido ms positivos (Johnson et al. 1997). Para la programacin lineal entera y mixta generales, de entre todas las restricciones posibles interesan, sobre todo, aquellas que definen facetas, y aunque se conoce que el obtener restricciones que definen facetas del poliedro convexo es importante, stas son extremadamente difciles de encontrar (Hoffman & Padberg 1993, Jnger et al. 1994 y Johnson et al. 1997). Ante tales dificultades, se persigue el ms modesto objetivo de separar en clases de restricciones vlidas, que en varios sentidos son fuertes y pueden dar facetas para un poliedro que contenga el cierre convexo, o dar caras de razonablemente gran dimensin, pero no necesariamente facetas. Como exponen Johnson et al. (1997), el problema de encontrar cortes violados puede ser polinomial o NP-hard (y entonces se utilizan heursticas que pueden fallar y no encontrar ningn corte), y el tiempo que se debe invertir en encontrar cortes violados debe ser resuelto empricamente caso por caso. Fischetti et al. (1995), Balas et al. (1996) y Johnson et al. (1997) entre otros, exponen diversos tipos de cortes: - Lifted cover inequalities6. Cortes que en algoritmos branch and cut y para programacin binaria han probado ser muy efectivos, segn dichos autores.
Para mayor informacin sobre los cortes lifted cover inequalities se recomienda Crowder et al. (1983).
Liff-and-project1'.
- Flow cover inequalities*. Generalizacin de las restricciones de cubrimiento, que en algoritmos branch and cut y para programacin binaria mixta, han probado ser muy efectivas segn estos autores. - Por su parte, Fischetti et al. (1995) proponen definir nuevas familias de desigualdades que exploten las caractersticas propias del problema concreto a resolver (restricciones lgicas,...). Como comentan Hoffman & Padberg (1993) y Jnger et al. (1994) entre otros, el branch and cut puede utilizarse para resolver problemas de grandes dimensiones (incluso a veces pudiendo probar su optimalidad), aunque tambin se puede utilizar como un procedimiento heurstico, que adems proporciona una cota inferior de la solucin ptima. Uno de los problemas que presenta el branch and cut es que, aunque obtiene la solucin ptima en un nmero finito de pasos, no se puede estimar el tiempo necesario para obtenerla ni aun sabiendo el tamao del ejemplar. Adems y como se expone en Jnger et al. (1994), la implementacin de un branch and cut es ms complicada que muchos algoritmos puramente combinatorios. Cabe destacar que ningn autor, excepto Jnger et al. (1994), comentan cmo resolver el programa lineal: mediante el simplex o el simplex dual, segn qu base sea factible. Tambin sealan que el programa de resolucin del programa lineal es uno de los cuellos de botella de estos procedimientos, ya que muchas veces ms del 90% del tiempo de clculo se lo pasa resolviendo programas lineales. Exponen que existen eficientes programas que implementan el simplex (CPLEX, OSL, etc.) o mtodos de punto interior (OSL, CPLEXbarrier, etc.) y que es necesario que stos dispongan de potentes rutinas de post-optimizacin (para detectar infactibilidades, etc.). Como en todo procedimiento de exploracin del espacio de estados, en el branch and cut tambin tiene una importancia vital el modelizar y formular el problema a resolver de la manera ms adecuada posible. Alonso & Escudero (1995, 1998) resuelven un problema de planificacin del trfico areo mediante dos formulaciones equivalentes: la segunda necesita un mayor nmero de variables y restricciones, pero muchas de stas definen facetas de la regin factible; como consecuencia, es frecuente que en la solucin continua relajada del problema se obtengan muchas variables con valor entero y, por consiguiente, el proceso de resolucin mediante branch and cut es mucho menor y ms rpido.
Se puede oblener una informacin ms detallada sobre los cortes lift-and-project en Balas el al. (1996) y. como estos mismos autores recomiendan, en Balas et al. (1993). Una mayor concrecin sobre los cones flaw cover inequalities se puede encontrar en Padberg et al. ( 1985).