Introducción a la optimización robusta

TRABAJO FIN DE GRADO Introducci´on a la optimizaci´on robusta Realizado por: Cristina Consolaci´on Mart´ınez Ortega Supervisado por: Eduardo Conde S´anchez FACULTAD DE MATEM´ ATICAS DPTO DE ESTAD´ ISTICA E INVESTIGACI ´ ON OPERATIVA 1 ´ Indice general 1. Decisi´on en ambiente de incertidumbre 6 1.1. Planteamiento del problema . . . . . . . . . . . . . . . . . . . 6 1.2. Tablas de decisi´on . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3. Criterios de decisi´on bajo incertidumbre estricta . . . . . . . 9 1.3.1. Criterio maximin de Wald. . . . . . . . . . . . . . . . 10 1.3.2. Criterio maximax de Hurwicz. . . . . . . . . . . . . . 10 1.3.3. Criterio minimax regret de Savage. . . . . . . . . . . . 12 1.3.4. Criterio maxisum de Laplace. . . . . . . . . . . . . . . 13 1.3.5. Ejemplo de Milnor. . . . . . . . . . . . . . . . . . . . . 13 1.4. Principios de racionalidad . . . . . . . . . . . . . . . . . . . . 14 1.4.1. Principio: Clasificaci´on completa. . . . . . . . . . . . . 14 1.4.2. Principio: Independencia de etiquetado. . . . . . . . . 15 1.4.3. Principio: Independencia de escala de valores. . . . . . 16 1.4.4. Principio: Dominaci´on fuerte. . . . . . . . . . . . . . . 16 1.4.5. Principio: Independencia de alternativas irrelevantes. . 17 1.4.6. Principio: Independencia de la adici´on de una constante a una columna. . . . . . . . . . . . . . . . . . . . 18 1.4.7. Principio: Independencia de permutaciones por filas. . 19 1.4.8. Principio: Independencia de duplicaci´on de columnas. 20 2 1.5. An´alisis de los principios de racionalidad . . . . . . . . . . . . 21 2. Aplicaciones del criterio minimax regret 32 2.1. Modelo: Programaci´on lineal robusta. . . . . . . . . . . . . . 35 2.2. Modelo: Problema robusto de asignaci´on. . . . . . . . . . . . 38 2.3. Modelo: Problema robusto de caminos m´as cortos. . . . . . . 40 2.4. Modelo: Problema robusto de ´arbol de uni´on. . . . . . . . . . 41 2.5. Modelo: Problema robusto de mochila. . . . . . . . . . . . . 42 2.6. Modelo: Problema robusto de asignaci´on de recursos. . . . . 43 2.7. Modelo: Problema robusto de secuenciaci´on. . . . . . . . . . 46 2.8. Modelo: Problema robusto de dise˜no de redes. . . . . . . . . 50 2.9. Ejemplo num´erico . . . . . . . . . . . . . . . . . . . . . . . . 54 3. Complejidad y aproximaci´on 70 3.1. Complejidad. ........................... 70 3.2. M´etodo de descomposici´on de Benders. . . . . . . . . . . . . . 76 3.3. M´etodo de descomposici´on de Benders aplicado al dise˜no robustoderedes. .......................... 78 3.4. Generaci´on de cortes para el Problema Maestro del AlgoritmodeBenders .......................... 81 3.5. Algoritmo de Benders . . . . . . . . . . . . . . . . . . . . . . 87 3.6. Coste esperado de los dise˜nos robustos . . . . . . . . . . . . . 91 3.7. Conclusiones ........................... 93 3 Abstract Sometimes, we may found a decision problem, different situations in which we have different options and we must decide. The treatment we must give to the problem must take into account the frequency with which the decision maker is in that situation. Sometimes, it may be appropriate to use expected values whereas other times it may not be a good choice. If we speak of decisions that must be made in concrete situations that will not be repeated, at least under the same probabilistic conditions, such as evacuations, emergency services assistance, etc, the decision criterion should not be to select the least expected cost. In this way, the stochastic programming may not be able to satisfy the requirements of decision making in decision environments characterized by significant uncertainty since it requires assigning probability distributions to the scenarios considered. This is not a trivial exercise for many decision makers because in many cases it can be difficult to calculate the probability of a future scenario occurring when the related factors refer to the behavior of companies, agencies or governments for which we do not have information. In other cases, changes in the attitudes and priorities of potential clients related to the decision problem may have to be considered. The approach followed in this work, unlike that used in stochastic programming, has the objective of protecting the decision maker without using a probability model on the performance of the system. In the framework of robustness, what the decision maker wants is not the optimal long-term or optimal for a single scenario (although it is the most likely scenario), but a decision that works well in all cases. So a robust decision will be one that is 4 characterized by significant uncertainty, works well in all cases and is protected against the worst possible scenarios. The robust discrete optimization problems are in general more difficult to solve than their deterministic counterparts. The major source of complexity comes from the extra degree of freedom - the scenario set. For many polynomially solvable classical optimization problems such as assignment, minimum spanning tree, shortest path, resource allocation, single machine scheduling with sum of flow times criterion, their corresponding robust versions are weakly or strongly NP−hard. The problems we will see have a high complexity, so we will see a numerical method of resolution that can be stopped before reaching the optimum that will lead us to a ε−optimal solution. With this approach we can obtain a method that is computationally more efficient in order to compute good solutions in real life problems. 5 Cap´ıtulo 1 Decisi´on en ambiente de incertidumbre 1.1. Planteamiento del problema A menudo podemos encontrarnos con un problema de decisi´on, distintas situaciones en las que se nos presentan distintas opciones y debemos decidir. El tratamiento que debemos dar al problema deber´a tener en cuenta la frecuencia con la que el decisor se encuentra en esa situaci´on. A veces, puede ser adecuado usar valores esperados y en cambio, otras veces puede no ser una buena opci´on (como veremos bas´andonos en el libro de S. French [5]). Un ejemplo de esto podr´ıa ser elegir la mejor ruta para ir de casa al trabajo. El tiempo requerido para recorrer una ruta concreta es una variable aleatoria debido por ejemplo a la intensidad de tr´afico o al efecto de los sem´aforos, pero si en este caso tenemos en cuenta valores esperados, y optamos por elegir la ruta con la que, en media, tardamos menos, la Ley Fuerte de los Grandes N´umeros nos dice que si aplicamos este criterio de decisi´on reiteradamente en las mismas condiciones probabil´ısticas, el tiempo promedio 6 empleado se acerca cada vez m´as al ´optimo. Pero en cambio, si hablamos de decisiones que deben ser tomadas en situaciones concretas que no se volver´an a repetir, al menos bajo las mismas condiciones probabil´ısticas, como evacuaciones, asistencia de servicios de emergencia, etc. el criterio de deci- si´on no deber´ıa ser el de seleccionar la ruta de menor tiempo esperado. En este caso es necesario reforzar la toma de decisiones de forma que se proteja al decisor contra eventualiades que pudiesen ocurrir. Esto da lugar a lo que se denomina optimizaci´on robusta. Adem´as, dentro del marco de la programaci´on estoc´astica, se necesita conocer las distribuciones de probabilidad de cada una de las rutas posibles y eso puede no ser una tarea f´acil. Por lo tanto, como podemos ver, tomar una buena decisi´on no es tan sencillo. 1.2. Tablas de decisi´on En esta secci´on veremos c´omo podemos representar los problemas de decisi´on sin perder ninguna de sus caracter´ısticas esenciales mediante lo que llamaremos una tabla de decisi´on. La consecuencia de cualquier acci´on viene determinada no s´olo por la acci´on en s´ı misma sino tambi´en por un n´umero de factores externos. Estos factores est´an habitualmente fuera del control del decisor y suelen ser desconocidos en el momento en el que se toma la decisi´on. A cada realizaci´on posible la denominaremos escenario y conocido el escenario podr´ıamos predecir las consecuencias de cada acci´on con certeza. En la tabla de decisi´on representaremos los distintos escenarios que nos podr´ıamos encontrar como el conjunto {θs:s∈S}=θ1, θ2, . . . , θny las distintas acciones o alternativas que podemos llevar a cabo por el conjunto {X:x∈X}=x1, x2, . . . , xmcon n, m ∈Z. En el caso en el que las acciones sean elegir qu´e persona ocupar´a un determinado puesto de trabajo, como ocurre en los problemas de contrataci´on de personal, los θjse suelen 7 identificar, no como posibles escenarios sino como cualidades o atributos de los diferentes candidatos al puesto de trabajo. En esta situaci´on un criterio de decisi´on determinar´a de manera objetiva la decisi´on ´optima de manera objetiva y cuantificable en funci´on de la valoraci´on de los candidatos en cada una de las caracter´ısticas tenidas en cuenta. Para los criterios de decisi´on que presentaremos en este tema, asumiremos que tanto los escenarios como las acciones son finitos pero, podr´ıamos esperar que fuesen infinitos y en tal caso, las herramientas matem´aticas que deber´an usarse ser´an diferentes. Como hemos dicho, los factores externos no son conocidos por el decisor en el momento en que ´este toma la decisi´on. Pero una vez elegida la acci´on xi, tiene lugar uno y s´olo uno de los escenarios. A este escenario lo llamaremos escenario real. De esta forma, llamaremos vij al valor de la consecuencia de elegir la acci´on xicuando θjes el escenario real. Estas valoraciones representan algo positivo, es decir, cuanto mayores son, mejor. Se trata por tanto de beneficios obtenidos por el decisor que elige una acci´on bajo un determinado escenario o de la puntuaci´on de una caracter´ıstica positiva para un posible candidato a un puesto de trabajo. Por tanto, una tabla de decisi´on viene representada como vemos en la tabla 1,1. Los problemas de decisi´on se clasifican seg´un el conocimiento de quien toma la decisi´on sobre el escenario real de la siguiente forma. Decisiones bajo certeza. En este caso, el decisor sabe cu´al es el escenario real y plantea las distintas acciones. Es equivalente a tomar n= 1 y considerar un ´unico escenario. En dicho escenario, vi1representa el 8 creciente (o decreciente) de dicho´ındice. De aqu´ı en adelante podemos considerar una regla de decisi´on no especificada y suponer que se asigna el ´ındice Via la acci´on xi, de tal forma que si Vi> Vj∀i6=jel criterio considera xi mejor que xj. Si expresamos de esta forma los cuatro criterios que hemos visto obtenemos lo siguiente: Criterio de m´axima recompensa de Wald Vi=si; Criterio optimista pesimista de Hurwicz Vi=αsi+ (1 −α)oi; Criterio de minimax regret Vi=−ρi; Criterio de raz´on insuficiente de Laplace Vi=X j1 nvij. 1.4.2. Principio: Independencia de etiquetado. Este principio establece el requisito de que la elecci´on sugerida por un criterio no debe verse influenciada por la forma en que vienen representadas las alternativas frente a los distintos escenarios. Por tanto, se exige que la clasificaci´on final de las acciones sea independiente tanto del orden en el que hemos etiquetado la acci´on en la tabla de decisiones, como del orden en el que hemos etiquetado los escenarios. De manera general, sea una tabla de decisi´on m×ncon escenarios θj, acciones xiy valores vij dados. Sea una segunda tabla de decisi´on m×n, con escenarios θj0, acciones x0y valores v0 ij construida a partir de la primera permutando las filas y las columnas tales que, la fila ise convierte en la fila π(i) y la columna jen la columna π(j). v0 π(i)π(j)=vij. De esta forma, una regla de decisi´on asigna los valores VryV0 rrespectivamente a las acciones en las dos tablas de forma que 15 Vi> Vk⇔V0 π(i)> V 0 π(k),∀1≤i, k ≤m. 1.4.3. Principio: Independencia de escala de valores. Observemos que si cambiamos de una escala de medida a otra, cada uno de los valores vij se convertir´ıa en (δvij +β), donde δ > 0 es el factor de conversi´on y βel ajuste del cambio desde el cero. Por lo que deber´ıamos exigir que la elecci´on sugerida por una regla de decisi´on sea independiente de la escala en la que medimos el valor. De manera general, sea una tabla de decisi´on m×ncon escenarios θj, acciones aiy valores vij dados. Sea una segunda tabla de decisi´on m×n, con escenarios θj, acciones ai, pero diferentes valores v0 ij construidos a partir de la primera cambiando la escala de medici´on del valor, con δ > 0 y βfijos como sigue v0 ij =δvij +β Bajo este principio de racionalidad, una regla de decisi´on asigna los valores VryV0 rrespectivamente a las acciones en las dos tablas de forma que Vi> Vk⇔V0 i> V 0 k,∀1≤i, k ≤m. 1.4.4. Principio: Dominaci´on fuerte. Este principio establece que si una acci´on tiene mejor valoraci´on estrictamente que otra, cualquiera que sea el escenario, entonces claramente la primera acci´on debe ser preferida a la segunda. Consideremos, por ejemplo, la tabla de decisi´on 2 ×5 siguiente θ1θ2θ3θ4θ5 a17 8 6 3 5 a2425−7 1 16 En este caso, el principio establece que la acci´on a1deber´ıa ser preferida a la acci´on a2, porque cualquiera que sea el escenario conduce a una mejor consecuencia en sentido estricto. Supongamos que en una tabla de decisi´on hay dos alternativas aiyaktal que ∀escenario θj vij > vkj. Entonces una regla de decisi´on debe asignar los valores Vrtal que Vi> Vk. 1.4.5. Principio: Independencia de alternativas irrelevantes. Este principio exige que la clasificaci´on de dos acciones en una tabla de decisi´on debe ser independiente a las dem´as acciones posibles. De manera general, sea una tabla de decisi´on m×ncon escenarios θj, acciones aiy valores vij dados. Sea una segunda tabla construida a partir de la primera simplemente a˜nadiendo una acci´on extra. As´ı, la segunda tabla es (m+1)×n y v0 ij =vij ∀1≤i≤n, 1 ≤j≤n. Para 1 ≤j≤n,v0 (m+1)jpuede tomar cualquier valor num´erico. Entonces, una regla de decisi´on asigna los valores VryV0 rrespectivamente a las acciones de las dos tablas tal que Vi> Vk⇔V0 i> V 0 k∀1≤i, k < m Esto es que una regla de decisi´on debe conducir a la misma clasificaci´on de las primeras macciones en ambas tablas. 17 1.4.6. Principio: Independencia de la adici´on de una constante a una columna. Consid´erense las dos tablas 2 ×2 siguientes θ1θ2 a16 4 a23 8 θ0 1θ0 2 a0 116 4 a0 213 8 La diferencia entre ambas tablas es que se ha a˜nadido a ambos elementos de la primera columna la constante 10 para pasar de la primera a la segunda. Podemos ver que la decisi´on que representa la primera tabla es exactamente la misma que representa la segunda. Bajo el primer escenario, la primera alternativa es 3 unidades mejor que la segunda; bajo el segundo escenario es 4 unidades peor. Por lo que cabr´ıa esperar que una regla de decisi´on eligiera la misma acci´on en ambas tablas. Pues bien, sea una tabla de decisi´on m×ncon escenarios θj, alternativas aiy valores vij dados. Sea una segunda tabla con los mismos escenarios θj y alternativas aipero con diferentes valores vij, construidos a partir de la primera a˜nadiendo una constante a todos los elementos de la l−´esima columna tal que para j6=l, 1≤j≤n, 1≤i≤m: v0 il =vil +c v0 ij =vij 18 Entonces, una regla de decisi´on debe asignar los valores VryV0 rrespectivamente, a las acciones en las dos tablas tal que Vi> Vk⇔V0 i> V 0 k∀1≤i, k ≤m Los principios vistos hasta ahora no precisan restricci´on acerca de la incertidumbre existente sobre el escenario que ocurrir´a al tomar la decisi´on, es decir, son requisitos para cualquier regla de decisi´on, sin necesidad de encontrarnos bajo incertidumbre estricta. Los dos siguientes principios se centran claramente en el ´ambito de la incertidumbre estricta. Si efectivamente el decisor no conoce nada acerca del escenario real, es f´acil suponer que no habr´ıa diferencia entre las alternativas de la tabla siguiente θ1θ2θ3 a1603 a2063 Es claro que el conjunto de posibles consecuencias de a1es id´entico en t´erminos de valor a la de a2. La ´unica diferencia razonable entre ambas es que se producen consecuencias iguales en valor pero bajo distintos escenarios. Parece razonable esperar, que si hacemos una permutaci´on en una fila no deber´ıa verse afectada la decisi´on final. 1.4.7. Principio: Independencia de permutaciones por filas. Supongamos que en una tabla de decisi´on m×nhay dos acciones aiy ak, y una permutaci´on τpara los n´umeros {1,2,· · · , n}tal que vij =vkτ(j). Bajo este principio de racionalidad, una regla de decisi´on deber´ıa asignar el valor Vra las acciones tal que 19 Vi=Vk. Podr´ıa decirse que el principio 1.4.7 no es suficiente para caracterizar lo que entendemos por circunstancias de incertidumbre estricta. Consid´erense los dos problemas de decisi´on de las tablas 1.4 y 1.5. Es de esperar que nos preguntemos ahora si existe realmente alguna diferencia entre estos problemas si es cierto que el escenario real es estrictamente incierto. Si los escenarios θ0 2,θ0 3,θ0 4yθ0 5se asocian y se identifican con el escenario compuesto θ00 2, entonces las tablas 1.4 y 1.5 implicar´ıan id´enticas consecuencias para dos alternativas consideradas. Realmente una elecci´on que apunte que θ2en la tabla 1.4 sea diferente a θ00 2en la tabla 1.5 no puede ser bajo una situaci´on de incertidumbre estricta. Es cierto que θ00 2se verifica bajo cualquiera de sus “versiones”θ0 2,θ0 3,θ0 4oθ0 5, pero eso, bajo incertidumbre estricta, no es relevante a la hora de comparar la posibilidad de que ocurra uno de estos dos escenarios θ00 2yθ0 1. Por lo tanto la acci´on elegida en la tabla 1.4 debe ser la misma que en la tabla 1.5 si este principio es verificado por el criterio de decisi´on. 1.4.8. Principio: Independencia de duplicaci´on de columnas. Sea una tabla de decisi´on m×ncon escenarios θj, alternativas aiy valores vij dados. Sea una tabla m×(n+ 1) con escenarios θ0 j, alternativas a0 iy valores v0 ij construidos a partir de los valores de la primera tabla duplicando la n−´esima columna de forma que ∀1≤j≤n,∀1≤i≤m v0 ij =vij v0 i(n+1) =vin. 20 As´ı, una regla de decisi´on debe asignar los valores VryV0 rrespectivamente a las acciones en las dos tablas tal que Vi> Vk⇔V00 i> V 00 k,∀1≤i, k ≤m θ1θ2 a19 4 a22 6 Tabla 1.4: Ejemplo para el principio 1.4.8 θ00 2 θ0 1θ0 2θ0 3θ0 4θ0 5 a0 19 4 4 4 4 a0 22 6 6 6 6 Tabla 1.5: Ejemplo para el principio 1.4.8 N´otese que aunque este principio s´olo duplica la ´ultima columna una vez, una duplicaci´on repetida permite que se aplique a situaciones como las de la tabla anterior. Adem´as, la combinaci´on de este principio con el principio 1.4.2 denota que se aplica a situaciones en las que cualquier columna es duplicada. 1.5. An´alisis de los principios de racionalidad En esta secci´on se comparan los cuatro criterios de decisi´on que se definieron en la secci´on 1.3 t´erminos de la base axiom´atica establecida a trav´es de los principios de racionalidad. Adem´as veremos que no existe ning´un criterio que sea compatible con todos los principios considerados. Teorema 1.5.1 Los criterios de decisi´on de Wald, Hurwicz, minimax regret y Laplace verifican la siguiente tabla de compatibilidades respecto a los principios de racionalidad 1.4.1-1.4.8. 21 Wald Hurwicz minimax Laplace Principio 1.3.1 ! ! ! ! Clasificaci´on completa Principio 1.3.2 ! ! ! ! Independencia de etiquetado Principio 1.3.3 ! ! ! ! Independencia de escala de valores Principio 1.3.4 ! ! ! ! Dominaci´on fuerte Principio 1.3.5 ! ! % ! Independencia de alternativas irrelevantes Principio 1.3.6 % % ! ! Independencia de la adici´on de una constante a una columna Principio 1.3.7 ! ! % ! Independencia de permutaciones por filas Principio 1.3.8 ! ! ! % Independencia de duplicaci´on de columnas Tabla 1.6: Compatibilidad de los criterios con los principios de racionalidad. ! indica que el criterio satisface el principio, % indica que no lo satisface. Demostraci´on 1.5.1 A continuaci´on solo se demostrar´a la compatibilidad de los criterios con algunos de los principios que consideramos m´as relevantes, y veremos un contraejemplo para cada uno de los criterios y los principios que incumplen. El principio 1.4.1 lo satisfacen todos los criterios puesto que, cada criterio asigna un valor num´erico a cada alternativa y el orden de estos valores nos da una clasificaci´on completa. Para demostrar que el criterio maximin de Wald satisface el principio 1.4.2, vemos que si el nivel de seguridad de una acci´on es el m´ınimo de los valores de esa acci´on en los distintos escenarios, podemos asegurar que el nivel de seguridad no cambia en el caso en que permutemos las columnas. Esto se debe a que el m´ınimo de un conjunto de valores no depende de la posici´on en que se encuentren los distintos valores. Veamos que el criterio de Laplace satisface el principio 1.4.3. 22 Sea vij =δvij +β, con δ > 0. Entonces, Vi= n X j=1 1 nvij > n X j=1 1 nvkj =Vk; ⇔δ  n X j=1 1 nvij +β > δ   n X j=1 1 nvkj +β; ⇔ n X j=1 1 n(δvij +β)> n X j=1 1 n(δvkj +β); ⇔V0 i= n X j=1 1 nv0 ij > n X j=1 1 nv0 kj =V0 k. Para demostrar que el criterio maximin de Wald satisface el principio 1.4.4. Supongamos que vij > vkj para todos los escenarios θj. Entonces Vi=si= m´ın j=1,...,n {vij}=vij0 > vkj0 ≥m´ın j=1,...,n {vkj}=sk=Vk. Veamos que el criterio de Hurwicz satisface el criterio 1.4.5. Para toda acci´on ai,αsi+ (1 −α)oi=αm´ın j=1,...,n {vij}+ (1 −α) m´ax j=1,...,n {vij}es independiente de cualquier otra acci´on. De esta forma, a˜nadir una nueva acci´on a la tabla no puede afectar a la clasificaci´on del resto de acciones a1, a2, . . . , am. Veamos que el criterio de Laplace satisface el principio 1.4.6. Sea v0 il =vil +cpara alg´un l v0 ij =vij para j6=l, 1≤j≤n 23 Entonces Vi= n X j=1 1 nvij > n X j=1 1 nvkj =Vk; ⇔c n+X1 n+vij >c n+X1 n+vkj; ⇔V0 i= n X j=1 1 nv0 ij > n X j=1 1 nv0 kj =V0 k. Es evidente que el m´ınimo elemento de la i-´esima fila es independiente de cualquier permutaci´on por filas. Por tanto, el criterio maximin de Wald satisface el principio 1.4.7. Para ver que el criterio minimax regret satisface el principio 1.4.8, supongamos que duplicamos la n-´esima columna. Entonces r0 i(n+1) = m´ax k=1,...,n nv0 k(n+1)o−v0 i(n+1),1≤i≤m, = m´ın k=1,...,m {vkn} − vin =rin. Ya que r0 ij =rij para 1 ≤i≤my 1 ≤j≤n,ρ0 i=ρipara cualquier ai. Por tanto, la clasificaci´on de las acciones no se ve afectada. Veamos ahora un contraejemplo para mostrar que el criterio de minimax regret no cumple el criterio 1.4.5. Para ello, consideremos la tabla 1.7 con alternativas a1ya2, luego consideremos la adici´on de la alternativa a3. Es f´acil comprobar que en el primer caso, ρ1= 3 <6 = ρ2, pero al a˜nadir la acci´on a3,ρ0 1= 9 >6 = ρ0 2. Por tanto, no se cumple el criterio 1.4.5. Para mostrar que el criterio minimax regret no cumple el principio 1.4.7 conside- 24 31 Cap´ıtulo 2 Aplicaciones del criterio minimax regret Como mencion´abamos al principio del primer cap´ıtulo, la programaci´on estoc´astica puede no ser capaz de satisfacer las necesidades de la toma de decisiones en entornos de decisi´on caracterizados por una incertidumbre significativa, ya que exige asignar distribuciones de probabilidad a los escenarios considerados y esto podr´ıa estar lejos de ser un ejercicio trivial para muchos decisores. En muchos casos puede ser dif´ıcil calcular la probabilidad de que ocurra un escenario futuro cuando los factores que intervienen se refieren al comportamiento de empresas, agencias o gobiernos de los que no disponemos de informaci´on. En otros casos puede que haya que considerar cambios en las actitudes y prioridades de los clientes potenciales relacionados con el problema de decisi´on. Adem´as, en muchas ocasiones, los decisores est´an m´as interesados en protegerse del riesgo que supone tomar decisiones por las que deber´an rendir cuentas en el futuro que en optimizar la eficacia esperada en todos los escenarios o simplemente en aquellos m´as probables. El decisor no solo se preocupa de c´omo el beneficio var´ıa en cada uno de los escenarios, 32 sino tambi´en de c´omo el beneficio real bajo la decisi´on tomada se compara con el beneficio ´optimo que podr´ıamos haber logrado si hubi´esemos conocido de antemano el escenario real. En el enfoque que se sigue en este trabajo, a diferencia del que se utiliza en programaci´on estoc´astica, tiene como objetivo el de proteger al decisor sin necesidad de utilizar un modelo de probabilidad sobre el comportamiento del sistema. En el marco de la robustez, lo que el decisor quiere no es el ´optimo a largo plazo ni el ´optimo para un ´unico escenario (aunque sea el escenario m´as probable), sino una decisi´on que funcione bien en todos los casos. Por lo que una decisi´on robusta ser´a aquella que caracterizada por una incertidumbre significativa, funciona bien en todos los casos y se protege contra el peor de los posibles escenarios. Dentro del marco de la robustez, y bas´andonos en [14] nos vamos a centrar en los tres criterios de decisi´on siguientes: Criterio maximin. Criterio minimax regret. Criterio minimax regret relativo. En ´el se compara la eficacia relativa de cada decisi´on frente a la ´optima en cada uno de los escenarios posibles. Este criterio podemos definirlo a partir del criterio minimax regret de Savage como sigue Definimos el regret relativo como r0 ij = m´ax l=1,...,m {vlj} − vij m´ax l=1,...,m {vlj}=rij m´ax l=1,...,m {vlj} Por lo que el peor regret relativo resultante bajo la acci´on xiser´a 33 ρ0 i= m´ax j=1,...,n nr0 ijo y entonces deber´ıamos elegir una acci´on que minimiza ρ0 i. Elegir xktal que ρ0 k= m´ın i=1,...,m nρ0 io= m´ın i=1,...,m    m´ax i=1,...,n rij m´ax l=1,...,m {vlj}   Remarcamos que, igual que ocurr´ıa con los criterios del cap´ıtulo anterior, la elecci´on de distintos criterios para la misma situaci´on pueden dar lugar a decisiones ´optimas distintas. Adem´as, tendremos en cuenta que, si los datos de entrada del problema se refieren a costes en lugar de a recompensas, la definici´on del r0 ij ser´ıa r0 ij = cij −m´ın l=1,...,n {clj} m´ın l=1,...,n {clj} De acuerdo con estas tres definiciones, para encontrar soluciones robustas nos centraremos en resolver los siguientes problemas de optimizaci´on: Para el criterio maximin zM= m´ın {y|f(X, θs)≤y, s ∈S;x∈X=∩s∈SFs}, siendo Fsel conjunto de soluciones factibles bajo el escenario s∈S. Para el criterio minimax regret zR= m´ın {y|f(X, θs)≤y+zs, s ∈S;x∈X}. Para el criterio minimax regret relativo zRL = m´ın {y|f(X, θs)≤(y+ 1)zs, s ∈S;x∈X}. 34 Tenemos en cuenta en todas las definiciones que la intersecci´on de los conjuntos factibles para s sea no vac´ıa, ∩s∈SFs6=∅. Nos referimos a ´estos como problemas de optimizaci´on robusta discreta. El principal objetivo que planteamos en esta secci´on es discutir la formulaci´on de un problema de optimizaci´on cuya soluci´on conduzca a la identificaci´on de decisiones robustas. 2.1. Modelo: Programaci´on lineal robusta. Un problema de programaci´on lineal para un escenario espec´ıfico sdado, se escribe de la forma m´ın csx s.t Asx=bs, x≥0. El problema minimax regret relativo de programaci´on lineal robusta ser´ıa como sigue m´ın y s.t csx≤(y+ 1)zs, s ∈S, Asx=bs, s ∈S, x≥0. 35 Que bien podr´ıa escribirse de la siguiente forma m´ın m´ax csx−zs zs:s∈S s.t Asx=bs, s ∈S, x≥0. Para el problema minimax regret de programaci´on lineal es necesario reemplazar el t´ermino de la derecha por y+zs. m´ın m´ax {csx−zs:s∈S} s.t Asx=bs, s ∈S, x≥0. Y el problema maximin de programaci´on lineal robusta tendr´ıa una formulaci´on an´aloga a las anteriores quedando como sigue m´ax m´ın {−csx:s∈S} s.t Asx=bs, s ∈S, x≥0. La programaci´on lineal tiene una amplia variedad de aplicaciones econ´omicas, como podemos ver en los libros de [10], [2] y [19], en muchos de ellos teniendo en cuenta la utilizaci´on de datos para los que existe incertidumbre en situaciones de planificaci´on a medio y largo plazo. 36 Para mostrar c´omo puede verse reflejada esta incertidumbre proponemos el siguiente problema de mezcla de productos. Una empresa fabrica nproductos finales diferentes, que podr´ıan ser variaciones del mismo producto, y utiliza mmaterias primas b´asicas para su fabricaci´on. Generalmente, las cantidades as ij indican la cantidad de materia prima b´asica iutilizada para la producci´on de una unidad del producto j, y las cantidades bs iindican la cantidad m´axima de materia prima disponible. En otros casos, as ij podr´ıa representar coeficientes de productividad (las horas de trabajo necesarias por unidad de producto final), y bs ipodr´ıa ser horas de trabajo disponibles de un tipo espec´ıfico de trabajo (cualificado, no cualificado o subcontratado). Pues bien, la empresa est´a interesada en maximizar su beneficio neto (el precio de venta menos la mano de obra y otros costos de producci´on) y, por lo tanto, las cantidades −cs jrepresentan el beneficio neto para un escenario de datos de entrada sespec´ıfico. La incertidumbre de los datos de entrada puede manifestarse de varias formas Incertidumbre en los coeficientes de beneficio neto. Podr´ıa reflejar las diferentes condiciones del mercado que pueden afectar al precio (por ejemplo, las posibles acciones de los competidores o la tasa de cambio y la incertidumbre inflacionaria si operan en un mercado extranjero), los costes de mano de obra (por ejemplo, la oferta limitada de mano de obra y / o huelgas laborales) y otros costes de producci´on (problemas inesperados de equipo tales como aver´ıas y problemas de calidad o rendimiento). 37 Uso de tecnolog´ıa de producci´on imprecisa. Esto influye en los coeficientes dependientes de la tecnolog´ıa aij (usamos la interpretaci´on de aij como coeficientes de productividad). Para una nueva tecnolog´ıa es dif´ıcil estimar el impacto o los efectos de aprendizaje sobre la productividad. Esto induce una alta incertidumbre en los valores de aij. Incertidumbre de la oferta de materias primas. Esta incertidumbre podr´ıa ser causada por las fuerzas del mercado (industrias competidoras por la misma materia prima podr´ıan limitar el suministro disponible) u otras razones sencillas tales como el clima o las restricciones gubernamentales a las importaciones. 2.2. Modelo: Problema robusto de asignaci´on. El problema de asignaci´on es un problema de programaci´on lineal entera con una estructura especial. Este problema tiene una amplia variedad de aplicaciones y se define como sigue m´ın X i,j cs ijxij s.t Pixij = 1, j = 1, . . . , n, Pjxij = 1, i = 1, . . . , n, xij ≥0, i, j = 1, . . . , n. Observamos que la matriz de restricciones es totalmente unimodular por lo que no necesitamos exigir que las variables xij ∈ {0,1}sino que es suficiente con que sean no negativas. Adem´as, no nos hace falta exigir que xij ≤1 puesto que tal como aparecen las restricciones no nos vamos a encontrar 38 ning´un xij que sea mayor o igual que 1. El problema minimax regret relativo de asignaci´on puede formularse de la forma m´ın y s.t X i,j cs ijxij ≤(y+ 1)zs, s ∈S, Pixij = 1, j = 1, . . . , n, Pjxij = 1, i = 1, . . . , n, xij ∈ {0,1}, i, j = 1, . . . , n. De manera an´aloga podemos encontrar la formulaci´on maximin, y mediante los cambios apropiados en el miembro de la derecha de la primera restricci´on, al igual que ocurr´ıa en el modelo anterior, podemos obtener la formulaci´on de minimax regret. Para el problema de asignaci´on, cada recurso (como ser´ıa un empleado o una m´aquina), debe ser asignado exclusivamente a una ´unica actividad o tarea particular. En este caso, hay un coste cij asociado con la asignaci´on ique realiza la tarea j. La incertidumbre de datos de entrada en este caso podr´ıa ser el nivel de eficiencia del empleado o m´aquina en cualquier d´ıa en particular de acuerdo con una planificaci´on. Por ejemplo, en el caso de una m´aquina, el nivel de eficiencia de la misma se ve afectado por muchos factores desconocidos tales como las condiciones meteorol´ogicas o la presencia de dispositivos auxiliares espec´ıficos (como accesorios, paletas y aceites lubricantes) que potencian la eficiencia de la m´aquina. Lo que intenta la una 39 decisi´on robusta es asignar los recursos a las tareas de manera que se proteja la actividad que se realiza contra la peor situaci´on posible. 2.3. Modelo: Problema robusto de caminos m´as cortos. Dado un grafo G= (V, E), con longitud no negativa ceasociada a cada eje e∈E, un nodo origen v0∈Vy un nodo destino vt∈V, se define el problema de caminos m´as cortos como encontrar el camino de m´ınima longitud total para ir de v0avt. Este problema puede resolverse en tiempo polinomial con una complejidad O(|V|2) , mediante el algoritmo de Dijkstra en [3], aunque existen implementaciones que rebajan esta complejidad. El problema maximin de camino m´as corto puede definirse como encontrar el camino que tiene longitud m´axima m´ınima en todos los escenarios. Para este tipo de problema, cada escenario corresponde a un conjunto predeterminado de longitudes de ejes. El problema minimax regret relativo (y de manera similar minimax regret) de caminos m´as cortos se define como encontrar entre todos los trayectos que van de v0avtel que minimiza la diferencia relativa m´axima (diferencia m´axima) de la longitud del trayecto frente a la longitud de trayecto ´optima en cada escenario. Una aplicaci´on obvia de este modelo es la de obtenci´on de rutas para el transporte de mercanc´ıas usando una red de carreteras. En la incertidumbre de los datos est´a reflejada la incertidumbre en las condiciones de tr´afico en las distintas carreteras (como es la presencia de accidentes, atascos de tr´afico en las horas punta o proyectos de construcci´on). Todos los escenarios anteriores podr´ıan no ser apropiados para un d´ıa en particular, debido a la falta de informaci´on actualizada en todas las carreteras tendr´a que considerar un subconjunto apropiado de escenarios, que podr´ıa afectar a todo o s´olo a un 40 orden de procesamiento de los ntrabajos, siendo σ(k) la posici´on en la que es procesado el trabajo ken la secuencia σ. Definimos las variables xik ∈ {0,1} como sigue xik =            1si σ(k) = i i = 1, . . . , n;k= 1, . . . , n. 0 en otro caso Es decir, xik vale 1 si el trabajo ise procesa en la k−´esima posici´on. Entonces, nuestro problema minimax regret relativo de secuenciaci´on puede ser escrito como m´ın y s.t 1 nPn i=1 Pn k=1 (n−k+ 1)ps ixik ≤1 n(y+ 1)zs, s ∈S, Pn k=1 xik = 1 i= 1, . . . , n, Pn i=1 xik = 1 k= 1, . . . , n, xik ∈ {0,1}i, k = 1, . . . , n. De esta forma, el lado izquierdo de la primera restricci´on representa el tiempo promedio que se tarda en atender a un cliente, y lo que se pretende es minimizar el regret relativo respecto del tiempo de completaci´on promedio ´optimo bajo cada escenario posible. Al igual que en otros modelos, para la versi´on de minimax regret del problema el lado derecho de la primera restricci´on debe ser reemplazado por y+zs, mientras que para el maximin, es decir, minimax en t´erminos de coste lo reemplazar´ıamos por y. 47 Veamos ahora la formulaci´on de un problema de secuenciaci´on con m´as de una m´aquina. El problema de secuenciaci´on de dos m´aquinas se ocupa de la programaci´on de una instalaci´on de producci´on en dos etapas (lo que podr´ıan ser dos m´aquinas), con procesamiento fijo desde la etapa 1 hasta la etapa 2, y con espacio de almacenamiento infinito entre ambas etapas. Considerando las mismas variables indicadoras xik que antes, y las variables Bs k= tiempo de inicio del k−´esimo trabajo en la secuencia de la segunda m´aquina (donde el super´ındice sse refiere al escenario de los tiempos de procesamiento). Lo que quiere decir que Bs kser´a el m´aximo entre el tiempo que se tarda en procesar el k−´esimo trabajo en la m´aquina 1 y el tiempo que tarda en quedarse libre la m´aquina 2 para el el k−´esimo trabajo. Pues bien, en estas condiciones podemos formular el problema de secuenciaci´on para el criterio de tiempo de completaci´on con el objetivo de fabricar en dos m´aquinas para un escenario de tiempos de procesamiento scomo sigue m´ın Pn i=1 ps i2xin +Bs n s.t Pn i=1 Pk j=1 ps i1xij ≤Bs k, k = 1, . . . , n;s∈S, Bs k+Pn i=1 ps i2xik ≤Bs k+1 k= 1, . . . , n −1; s∈S, Pn i=1 xik = 1 k= 1, . . . , n, Pn k=1 xik = 1 i= 1, . . . , n, xik ∈ {0,1}i, k = 1, . . . , n. 48 Si nos fijamos en la primera restricci´on, el miembro de la izquierda representa el tiempo total de procesamiento de los kprimeros trabajos en la m´aquina 1. Con respecto a la segunda restricci´on, el miembro de la izquierda representa el tiempo en el que puede comenzar el procesamiento del k−´esimo trabajo en la m´aquina 2 m´as lo que tarda ese trabajo en ser procesado por la m´aquina 2. Lo que estaremos calculando ser´a el m´ınimo tiempo total que se tarda en completar los ntrabajos en las 2 m´aquinas. As´ı pues, el minimax regret en el problema de secuenciaci´on para el criterio de tiempo de completaci´on se define como m´ın y s.t Pn i=1 ps i2xin +Bs n≤y+zs, s ∈S, Pn i=1 Pk j=1 ps i1xij ≤Bs k, k = 1, . . . , n;s∈S, Bs k+Pn i=1 ps i2xik ≤Bs k+1 k= 1, . . . , n −1; s∈S, Pn i=1 xik = 1 k= 1, . . . , n, Pn k=1 xik = 1 i= 1, . . . , n, xik ∈ {0,1}i, k = 1, . . . , n. La cantidad zsrepresenta el tiempo de completaci´on ´optimo del problema en cada escenario. Por lo tanto, lo que estamos minimizando es el m´ınimo del m´aximo regret de los tiempos de completaci´on. Para obtener el minimax regret relativo para el problema de secuenciaci´on, igualmente necesitamos reemplazar el lado derecho de la primera restricci´on por y (y+1)zs, y de manera an´aloga podemos encontrar una formulaci´on para el criterio maximin. 49 2.8. Modelo: Problema robusto de dise˜no de redes. Para estudiar el problema de dise˜no de redes nos centraremos en entornos caracterizados por una incertidumbre significativa en los datos de entrada. El problema de dise˜no de redes intenta resolver la siguiente cuesti´on: ¿qu´e configuraci´on de red minimiza la suma de los costes fijos de los arcos elegidos en dicha red y el coste de los enrutamientos de bienes a trav´es de la red definida por estos arcos? Este tipo de problema tiene aplicaciones tan diversas como la toma de decisiones de inversi´on de capital para la planificaci´on del transporte, la planificaci´on de la ruta y la flota de veh´ıculos, dise˜no de redes de telecomunicaciones, localizaci´on de instalaciones y dise˜no del sistema de distribuci´on de la carga. Desde un punto de vista te´orico, la versi´on m´as simple del problema de dise˜no de red sin capacidad de flujo en los arcos con costes de enrutamiento lineal, modela muchos de los problemas m´as conocidos en la optimizaci´on combinatoria (por ejemplo, caminos m´as cortos, m´ınimo ´arbol de uni´on, ramificaci´on ´optima, problema del viajante y problema de la red Steiner). Para un estudio m´as exhaustivo de problemas de dise˜no de red y sus aplicaciones, as´ı como una cobertura de los casos especiales de modelos de dise˜no de redes sin capacidad de flujo, v´ease [18]. Los elementos b´asicos del modelo son un conjunto Nde nodos y un conjunto Ade arcos no dirigidos disponibles para dise˜nar la red. Denotamos por {i, j}un arco no dirigido entre los nodos iyj, y por (i, j)y(j, i) sus correspondientes direcciones. Sea Kel conjunto de mercanc´ıas para cada k∈K,dkdenota la cantidad requerida de flujo de la mercanc´ıa kque debe ser enviada desde su punto de origen, denotado por O(k), hasta su punto de destino, denotado por D(k). Dado ck ij denota el coste no negativo de ruta de la mercanc´ıa ken el arco (i, j) y Fij es el coste fijo de construcci´on del 50 arco {i, j}. En general, ck ij yck ji no tienen por qu´e ser iguales, por ejemplo si hablamos de una ruta de carreteras, ir de iajpodr´ıa ser un camino m´as largo o con m´as cuestas que el camino de ir de jai, por lo que no tendr´ıan el mismo coste de combustible. Los par´ametros de entrada m´as importantes para el problema son los coeficientes de coste de ruta ck ij y los vol´umenes de los diversos productos a transportar dk. En el modelo que consideramos, no tenemos limitada la capacidad de flujo sobre los arcos, por tanto podemos simplificar el problema asumiendo que todo el producto se transporta utilizando la misma ruta desde O(k) hasta D(k). Esto equivale a ajustar los costes que ahora no ser´an unitarios sino que se refieren al transporte de la cantidad total de cada producto. Igual que hemos hecho en otros modelos, utilizaremos la notaci´on s∈S como el ´ındice de escenario de datos de entrada y Sel conjunto de todos los escenarios posibles. Diferentes escenarios de datos de entrada S implican diferentes costes de tomar el arco (i, j) para transportar todo el flujo de mercanc´ıa kdesde el nodo ial nodo j, es decir, ck ij(s). Sea Ck(s) = nck ij(s), i, j ∈NoyC(s) = Ck(s), k ∈K. Para datos de entrada espec´ıficos, (es decir, C(s), s∈S), el problema de dise˜no de red contiene dos tipos de variables de decisi´on, uno que modela decisiones discretas y otro que modela decisiones de flujo continuo. Sea yij una variable binaria que indica si se ha elegido o no el arco {i, j}, es decir yij =            1 si el arco {i, j}es elegido para el dise˜no de red 0 en caso contrario 51 Sea xk ij el flujo de la mercanc´ıa ken el arco dirigido (i, j). Entonces, si y= (yij) y x= (xk ij) son las matrices de las variables de dise˜no y flujo, para un escenario espec´ıfico s∈S, el problema de dise˜no de redes se formula como sigue: m´ın X k∈KX (i,j)∈A (ck ij(s)xk ij +ck ji(s)xk ji) + X {i,j}∈A Fijyij s.t X i∈N xk ij −X h∈N xk jh =                        −1 si j=O(k); j∈N 1 si j=D(k); k∈K 0 en otro caso.                        ;j∈N, k ∈K, xk ij ≤yij, xk ji ≤yij,{i, j} ∈ A, k ∈K, xk ij, xk ji ≥0; yij ∈ {0,1},{i, j} ∈ A, k ∈K, y∈Γ. El primer bloque de restricciones para cada producto krepresenta las limitaciones habituales de conservaci´on de flujo de red. El segundo bloque de restricciones rechaza cualquier flujo de mercanc´ıas a trav´es de arco {i, j} si este arco no est´a incluido en el dise˜no, es decir, yij = 0. El conjunto Γ incluye cualquier restricci´on lateral impuesta individual o conjuntamente en las variables de flujo y de dise˜no (por ejemplo, restricciones de elecci´on 52 m´ultiple (yij +ypq ≤1) o restricciones de prioridad (yij ≤yrs)). Las decisiones en el dise˜no de redes tienen un impacto determinante en la eficacia del sistema dise˜nado para un largo periodo de tiempo. En muchas instancias, debido a los cortos ciclos de vida de los productos, los dise˜nos de redes de fabricaci´on deben desarrollarse sin ni siquiera saber el conjunto exacto de productos a fabricar. Esta incertidumbre de datos de entrada impulsa al dise˜nador a buscar dise˜nos que sean “buenos” (es decir, cercanos al ´optimo) para una variedad de escenarios operativos futuros. Esto se denomina “propiedad de robustez” de los dise˜nos de redes. Dado que estamos hablando de costes de enrutamiento, el criterio minimax para el dise˜no de redes se formula como sigue: m´ın x,y m´ax s∈S(X k∈KX {i,j}∈A (ck ij(s)xk ij +ck ji(s)xk ji) + X {i,j}∈A Fijyij)−zs s.t X i∈N xk ij −X h∈N xk jh =                        −1 si j=O(k); j∈N 1 si j=D(k); k∈K 0 en otro caso.                        ;j∈N, k ∈K, xk ij ≤yij, xk ji ≤yij,{i, j} ∈ A, k ∈K, xk ij, xk ji ≥0; yij ∈ {0,1},{i, j} ∈ A, k ∈K, y∈Γ. 53 Donde zsrepresenta el coste de dise˜no ´optimo bajo el escenario s∈S. 2.9. Ejemplo num´erico Vamos a resolver el problema del dise˜no robusto de redes sobre el grafo de conexiones potenciales representado en la figura 2.1 Los coeficientes que -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 1 2 3 4 5 6 7 8 9 10 1 1 1 1 3 3 2 4 1 6 2 8 8 9 3 2 10 12 15 16 Figura 2.1: Red de conexiones potenciales con los costes fijos Fij aparecen asociados a los ejes corresponden con los costes fijos de construcci´on Fij . Suponemos que a lo largo de cada eje se puede transportar producto en ambos sentidos. El software utilizado para resolver la formulaci´on determin´ıstica del problema bajo cada escenario es AMPL. A continuaci´on se muestra el c´odigo correspondiente a la resoluci´on del problema bajo el primer escenario de costes de transporte set NODOS:={1..10}; set ARCOS within {NODOS,NODOS}:={ 54 (1,2), (1,3), (1,4), (1,5), (1,7), (2,6), (2,7), (5,7), (7,9), (6,9), (3,6), (3,10), (1,10), (4,10), (3,7), (8,10), (4,8), (5,8), (6,10), (8,9), (2,1), (3,1), (4,1), (5,1), (7,1), (6,2), (7,2), (7,5), (9,7), (9,6), (6,3), (10,3), (10,1), (10,4), (7,3), (10,8), (8,4), (8,5), (10,6), (9,8)}; set PRODUCTOS:={1..3}; param c{ARCOS,PRODUCTOS}; param F{ARCOS}; param B{NODOS,PRODUCTOS}; var x{ARCOS,PRODUCTOS}>=0; var y{ARCOS} binary; minimize objetivo:sum{(i,j) in ARCOS,k in PRODUCTOS} c[i,j,k]*x[i,j,k]+ sum{(i,j) in ARCOS} F[i,j]*y[i,j]; subject to flow{j in NODOS, k in PRODUCTOS}: sum{(i,j) in ARCOS}x[i,j,k]-sum{(j,h) in ARCOS}x[j,h,k]=B[j,k]; subject to bound{(i,j) in ARCOS,k in PRODUCTOS}: x[i,j,k]<=y[i,j]+y[j,i]; data; param c:= [1,2,1] 1 [1,3,1] 2 [1,4,1] 3 [1,5,1] 3 55 [1,7,1] 5 [2,6,1] 6 [2,7,1] 7 [5,7,1] 8 [7,9,1] 1 [6,9,1] 2 [3,6,1] 3 [3,10,1] 3 [1,10,1] 5 [4,10,1] 6 [3,7,1] 7 [8,10,1] 8 [4,8,1] 1 [5,8,1] 2 [6,10,1] 3 [8,9,1] 8 [2,1,1] 1 [3,1,1] 2 [4,1,1] 3 [5,1,1] 3 [7,1,1] 5 [6,2,1] 6 [7,2,1] 7 [7,5,1] 8 [9,7,1] 1 [9,6,1] 2 [6,3,1] 3 [10,3,1] 3 [10,1,1] 5 [10,4,1] 6 [7,3,1] 7 [10,8,1] 8 [8,4,1] 1 [8,5,1] 2 [10,6,1] 3 [9,8,1] 8 [1,2,2] 5 [1,3,2] 2 [1,4,2] 1 [1,5,2] 3 [1,7,2] 2 [2,6,2] 6 [2,7,2] 1 [5,7,2] 8 [7,9,2] 3 [6,9,2] 2 [3,6,2] 2 [3,10,2] 3 [1,10,2] 5 [4,10,2] 3 [3,7,2] 7 [8,10,2] 8 [4,8,2] 2 [5,8,2] 2 [6,10,2] 3 [8,9,2] 1 [2,1,2] 5 [3,1,2] 2 [4,1,2] 1 [5,1,2] 3 [7,1,2] 2 [6,2,2] 6 [7,2,2] 1 [7,5,2] 8 [9,7,2] 3 [9,6,2] 2 [6,3,2] 2 [10,3,2] 3 [10,1,2] 5 [10,4,2] 3 [7,3,2] 7 [10,8,2] 8 [8,4,2] 2 [8,5,2] 2 [10,6,2] 3 [9,8,2] 1 [1,2,3] 2 [1,3,3] 2 [1,4,3] 9 [1,5,3] 1 [1,7,3] 2 [2,6,3] 1 [2,7,3] 1 [5,7,3] 1 [7,9,3] 3 [6,9,3] 1 [3,6,3] 2 [3,10,3] 3 [1,10,3] 5 [4,10,3] 3 [3,7,3] 7 [8,10,3] 2 [4,8,3] 5 [5,8,3] 2 [6,10,3] 3 [8,9,3] 2 [2,1,3] 2 [3,1,3] 2 [4,1,3] 9 [5,1,3] 1 [7,1,3] 2 [6,2,3] 1 [7,2,3] 1 [7,5,3] 1 [9,7,3] 3 [9,6,3] 1 [6,3,3] 2 [10,3,3] 3 56 [*,*,3] : 12345678910 := 1 .0000.0..0 2 0....00... 3 0....00..0 4 0......0.0 5 0.....01.. 6 .00.....00 7 000.0...0. 8 ...00...01 9 .....000.. 100.00.0.0.. ; y [*,*] : 12345678910 := 1 .0010.0..0 2 0....00... 3 1....00..0 4 0......1.0 5 0.....01.. 6 .01.....00 7 000.1...0. 8 ...00...01 9 .....000.. 100.00.0.0.. ; 63 Gr´aficamente la nueva red ´optima se corresponde con la representada en trazo grueso en la figura 2.3 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 1 2 3 4 5 6 7 8 9 10 1 1 1 1 3 3 2 4 1 6 2 8 8 9 3 2 10 12 15 16 Figura 2.3: Dise˜no ´optimo bajo el escenario s2 Para resolver el problema minimax regret usaremos es siguiente c´odigo AMPL set NODOS:={1..10}; set ARCOS within {NODOS,NODOS}:={ (1,2), (1,3), (1,4), (1,5), (1,7), (2,6), (2,7), (5,7), (7,9), (6,9), (3,6), (3,10), (1,10), (4,10), (3,7), (8,10), (4,8), (5,8), (6,10), (8,9), (2,1), (3,1), (4,1), (5,1), (7,1), (6,2), (7,2), (7,5), (9,7), (9,6), (6,3), (10,3), (10,1), (10,4), (7,3), (10,8), (8,4), (8,5), (10,6), (9,8)}; set PRODUCTOS:={1..3}; set ESCENARIOS:={1..2}; 64 param c{ARCOS,PRODUCTOS,ESCENARIOS}; param F{ARCOS}; param B{NODOS,PRODUCTOS}; var x{ARCOS,PRODUCTOS}>=0; var y{ARCOS} binary; var maxregret>=0; minimize objetivo:maxregret; subject to regret1: sum{(i,j) in ARCOS,k in PRODUCTOS} c[i,j,k,1]*x[i,j,k]+ sum{(i,j) in ARCOS} F[i,j]*y[i,j]-37<=maxregret; subject to regret2: sum{(i,j) in ARCOS,k in PRODUCTOS} c[i,j,k,2]*x[i,j,k]+ sum{(i,j) in ARCOS} F[i,j]*y[i,j]-56<=maxregret; subject to flow{j in NODOS, k in PRODUCTOS}: sum{(i,j) in ARCOS}x[i,j,k]-sum{(j,h) in ARCOS}x[j,h,k]=B[j,k]; subject to bound{(i,j) in ARCOS,k in PRODUCTOS}: x[i,j,k]<=y[i,j]+y[j,i]; Aqu´ı se ha introducido el conjunto de ´ındices para los escenarios ESCENARIOS y se ha a˜nadido un nuevo ´ındice al array de costes de transporte. Por ´ultimo, se introducen dos nuevas restricciones denotadas por las etiquetas regret1 yregret2 que miden el regret bajo cada uno de los escenarios. El m´aximo de estos regrets se almacena en la variable maxregret que es mi- 65 nimizada. El valor objetivo ´optimo de este problema es 12.8 que se obtiene en la soluci´on x [*,*,1] : 1 2 3 4 5 6 7 8 9 10 := 1 .0000.3.0.7..0 2 0... . 00 ... 3 0... . 00 ..0 4 1 . . . . . . 0 . 0 5 0... . .0.30.. 6 . 0 0 . . . . . 0 0 7 000.0 . . .0. 8 ...00 . . .00 9 .... . 00 0.. 10 0 . 0 0 . 0 . 0 . . [*,*,2] : 12345678910 := 1 .0100.0..0 2 0....00... 3 0....10..0 4 0......0.0 5 0.....10.. 6 .00.....00 7 100.0...0. 8 ...00...00 9 .....000.. 100.00.0.0.. 66 [*,*,3] : 12345678910 := 1 .0000.0..1 2 0....00... 3 0....00..0 4 0......0.0 5 0.....10.. 6 .00.....00 7 100.0...0. 8 ...00...00 9 .....000.. 100.00.0.0.. ; Es interesante observar que el problema proporciona soluciones x1 ij fraccionarias a la hora de determinar c´omo se transporta la mercanc´ıa 1. La raz´on es que, fijado un dise˜no mediante las variables yij el conjunto de soluciones de transporte deja de ser un poliedro de v´ertices enteros al introducir las dos restricciones adicionales para computar el regret. El dise˜no robusto de la red se obtiene a partir de las variables binarias yij, y [*,*] : 12345678910 := 1 .0011.1..0 2 0....00... 3 1....00..0 4 0......0.0 67 5 0.....00.. 6 .01.....00 7 000.1...0. 8 ...00...00 9 .....000.. 101.00.0.0.. ; que definen el grafo representado en trazo grueso en la figura 2.4 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 1 2 3 4 5 6 7 8 9 10 1 1 1 1 3 3 2 4 1 6 2 8 8 9 3 2 10 12 15 16 Figura 2.4: Dise˜no robusto de la red 68 Para tener mayor facilidad comparando los dise˜nos ´optimos bajo cada escenario y el dise˜no robusto representamos en la figura 2.5 los tres dise˜nos -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 1 2 3 4 5 6 7 8 9 10 1 1 1 1 3 3 2 4 1 6 2 8 8 9 3 2 10 12 15 16 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 1 2 3 4 5 6 7 8 9 10 1 1 1 1 3 3 2 4 1 6 2 8 8 9 3 2 10 12 15 16 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 1 2 3 4 5 6 7 8 9 10 1 1 1 1 3 3 2 4 1 6 2 8 8 9 3 2 10 12 15 16 Escenario s1Escenario s2Soluci´on robusta Figura 2.5: Comparativa de los tres dise˜nos 69 Cap´ıtulo 3 Complejidad y aproximaci´on 3.1. Complejidad. Como hemos mencionado en cap´ıtulos anteriores, los problemas robustos de optimizaci´on discreta son en general, m´as dif´ıciles de resolver que sus formulaciones determin´ısticas. El principal factor es el aumento del grado adicional de libertad, es decir, de los escenarios establecidos. Para problemas de optimizaci´on cl´asicos en los que podemos hallar la soluci´on en tiempo polinomial, como pueden ser asignaci´on, m´ınimo ´arbol de uni´on, caminos m´as cortos, asignaci´on de recursos o de secuenciaci´on, las versiones robustas son d´ebilmente o fuertemente NP−duros. Hemos encontrado, (v´ease [13]) que algunos de los problemas antes mencionados pueden resolverse de manera pseudo-polinomial basado en programaci´on din´amica si el cardinal del conjunto de escenarios Ses acotado. El conocido problema de mochila que es pseudo-polin´omicamente resoluble tambi´en permanece pseudo-polin´omicamente resoluble para un conjunto de escenarios S cuyo cardinal est´e acotado, pero se convierte en NP−duro para un conjunto de escenarios en el que dicho cardinal no est´e acotado, es decir, cuando el tama˜no del conjunto de 70 escenarios forma parte del input. Para determinar la complejidad de los problemas minimax usaremos reducciones polinomiales a problemas de optimizaci´on NP-duros considerados est´andar en la Teor´ıa de la Complejidad. A continuaci´on describimos algunos de estos problemas. El problema de la 2−partici´on •Datos: Sean un conjunto finito Iy un tama˜no ai∈Z+para i∈I. •Pregunta: ¿Existe un subconjunto I0⊂Ital que Pi∈I0ai=Pi∈I\I0ai? Es conocido que el problema de la 2−partici´on es d´ebilmente NP−duro incluso cuando |I0|=|I| 2. El problema de la 3−partici´on •Datos: Sean un conjunto finito de 3lelementos I, una cota B∈ Z+, y un tama˜no ak∈Z+para k∈I, tal que cada aksatisface B/4< ak< B/2 y tal que Pk∈Iak=lB. •Pregunta: ¿Podemos dividir Ien lconjuntos disjuntos tal que Pk∈Iiak=Bpara 1 ≤i≤l? El problema de la 3−partici´on es fuertemente NP−duro. (V´ease [6]). El problema de la partici´on par-impar •Ejemplo: Sea una colecci´on de n´umeros enteros positivos ai, 1 ≤ i≤2ntal que Piai=A. 71 •Pregunta: ¿ Podemos dividir {ai}2n i=1 en dos conjuntos disjuntos A1, A2tal que Pai∈Akai=A 2para k= 1,2 y exactamente uno de a2i, a2i−1pertenezca a A1para 1 ≤i≤n? El problema de la partici´on par-impar es NP−duro. (V´ease [6]). El problema del conjunto de recubrimiento (SC) •Datos: Sean un conjunto Jde elementos y la familia Ide subconjuntos finitos de J, y k≥0. •Pregunta: ¿Contiene Iuna subfamilia de conjuntos de tal manera que el n´umero total de conjuntos en esta subfamilia es a lo m´as k, y cada elemento de Jest´a incluido en al menos uno de los conjuntos seleccionados? El problema del conjunto de recubrimiento es fuertemente NP−duro. (V´ease [6]). Veremos a continuaci´on una serie de resultados de complejidad de algunos de los modelos vistos en el cap´ıtulo anterior. Problema robusto de asignaci´on El problema robusto de asignaci´on lo definimos en la secci´on 2.2. Para un escenario espec´ıfico de datos de entrada el problema de asignaci´on puede resolverse en tiempo polinomial (O(n3)). Teorema 3.1.1 Los problemas robustos de asignaci´on minimax regret, minimax regret relativo y maximin son NP−duros incluso en el caso en el que |S|= 2. 72 red sin capacidad limitada en los arcos ([4], [8], [11], [16] y [21]). En esta secci´on discutiremos c´omo el m´etodo de descomposici´on de Benders puede modificarse adecuadamente para la generaci´on de dise˜nos robustos de redes. Cuando se aplica a problemas de dise˜no de redes, la descomposici´on de Benders va escogiendo iterativamente una configuraci´on de red y, y a continuaci´on va resolviendo el enrutamiento ´optimo de los diversos productos a trav´es de la red resultante, es decir, especificando x, y usa la soluci´on del problema de enrutamiento para redefinir la configuraci´on de red. Este ´ultimo paso se produce con la generaci´on de nuevas restricciones para el problema, que se denominan cortes de Benders. Estas restricciones forman parte de un problema entero mixto con las variables de elecci´on de dise˜no de red discretas y una ´unica variable continua que representa el coste total de la red (coste fijo y coste de enrutamiento). Este problema entero se conoce como el problema Maestro de Benders, en ´el se minimiza el coste total de la red sujeto a los cortes de Benders generados por cada configuraci´on de red anterior. Cada vez que se resuelve el problema maestro, se obtiene una cota inferior para el coste del dise˜no de red ´optimo. Adem´as, cada soluci´on al problema maestro determina una configuraci´on de red, y el coste fijo, combinado con el de transporte ´optimo sobre esta red es una cota superior para el valor ´optimo del problema. Estas dos cotas permiten una terminaci´on anticipada del algoritmo con nuestra evaluaci´on del grado de suboptimalidad de los dise˜nos de red obtenidos hasta ahora. En la literatura se pueden encontrar resultados referidos al problema de dise˜no de red desde una perspectiva de “optimalidad”(es decir, determinar la soluci´on del problema para un escenario de datos espec´ıficos). En sus conti- 79 nuos esfuerzos para resolver la complejidad del problema, los investigadores utilizaron diversos esquemas mejorando la descomposici´on de Benders (ver [16], [17]). Las versiones m´as refinadas de la metodolog´ıa Benders aplicada al dise˜no de redes han sido obtenidas para encontrar y verificar soluciones ´optimas para problemas con 30 nodos, 130 arcos con 40 arcos fijos abiertos (es decir, estos arcos ya existen en el dise˜no) y 58 productos b´asicos (v´ease [16]). Estos enfoques suelen ser ineficaces para resolver el problema con incertidumbre. Adem´as, el enfoque de fuerza bruta solo generar´a una lista parcial de soluciones ´optimas (o cercanas al ´optimo en el caso de una terminaci´on anticipada del algoritmo) para cada escenario de datos. Este enfoque no toma ninguna medida para tratar de generar en el proceso de optimizaci´on ninguna decisi´on robusta, y es probable que la intersecci´on de estas listas no contenga ninguna soluci´on robusta cualificada. El enfoque que veremos a continuaci´on apunta a generar dise˜nos de redes robustos con un esfuerzo computacional significativamente menor que la ejecuci´on repetida de aplicaciones independientes del Algoritmo de Benders. Podemos ver en la referencia [16] que los autores muestran que la mayor parte del esfuerzo computacional del Algoritmo de Benders (casi el 90 % de su tiempo de ejecuci´on) se invierte en la soluci´on del problema maestro. Esto se debe a que tenemos un problema maestro para cada escenario de datos. Cuando un problema maestro se resuelve, a partir de su soluci´on obtenemos una configuraci´on de red tentativa, y podemos resolver el enrutamiento ´optimo de los diversos productos en ese dise˜no de red para cada escenario de datos de manera eficiente utilizando el algoritmo de Dijkstra ([3]). Despu´es, usando teor´ıa de dualidad ([20]), podemos generar un nuevo corte para cada uno de los problemas maestros correspondientes a cada uno de los escenarios de datos. Como veremos esta generaci´on cruzada de cortes de Benders 80 (es decir, generando un corte para cada problema maestro correspondiente a cada escenario cada vez que se resuelve un problema maestro) acelera la convergencia del problema maestro para todos los escenarios. Un beneficio adicional de este procedimiento es que cada soluci´on obtenida para cada problema maestro, en el proceso de cortes de generaci´on cruzada que hemos mencionado, se compara repetidamente con las mejores cotas superior e inferior obtenidas para cada escenario de datos. 3.4. Generaci´on de cortes para el Problema Maestro del Algoritmo de Benders Consideramos un y∈Γ fijo, as´ı el problema UNDP(s) se reduce al problema lineal BP(s, y) : m´ın Ws(y) = X k∈KX {i,j}∈A (ck ij(s)xk ij +ck ji(s)xk ji) s.t X i∈N xk ij −X h∈N xk jh =                        −1 si j=O(k); j∈N 1 si j=D(k); k∈K 0 en otro caso.                        ;j∈N, k ∈K, xk ij ≤yij, xk ji ≤yij,{i, j} ∈ A, k ∈K, xk ij, xk ji ≥0; {i, j} ∈ A, k ∈K. 81 De esta manera, Ws(y) representa el coste de transporte para un dise˜no concreto de red dado por una configuraci´on de red yfija. En el enfoque de la descomposici´on de Benders, se buscan las soluciones del dual de BP(s, y) y son utilizadas para generar cortes adicionales para el problema maestro de Benders. El conjunto factible de este problema dual no depende del dise˜no de la red, con lo cu´al cualquier soluci´on factible dual nos dar´a una acotaci´on inferior del valor objetivo ´optimo de problema BP(s, y). Dado que los arcos no tienen capacidad, fijado ypodemos descomponer el problema BP(s, y) y su dual en Ksubproblemas independientes, uno para cada mercanc´ıa. Precisamente por no tener capacidades, la soluci´on ´optima puede ser encontrada mediante la resoluci´on de un problema de caminos m´as cortos sobre la configuraci´on de red y, y con matriz distancia Ck(s). El dual para cada uno de los ksubproblemas de BP (s, y) viene dado por: DBPk(s, y) : m´ax uk D(k)(s)−uk O(k)(s) + X {i,j}∈A (vk ij(s) + vk ji(s))yij s.t uk j(s)−uk i(s)−vk ij(s)≤ck ij(s),{i, j} ∈ A, uk i(s)≥0, i ∈N, vk ij(s), vk ji(s)≥0,{i, j} ∈ A. donde uk j(s) es la variable dual correspondiente a la restricci´on para el k- ´esimo producto y nodo jen el primer bloque de restricciones del dise˜no de 82 redes, y vk ij(s) es la variable dual correspondiente a la restricci´on para el arco {i, j}para el segundo bloque de restricciones del problema de dise˜no de red. Observemos adem´as, que las restricciones del problema dual no dependen de la configuraci´on de red y. Una vez resueltos todos los problemas duales, obtendremos unos valores para uyv, y sumando todos los valores objetivos de los problemas duales estaremos determinando un coste de enrutamiendo bajo una estructura y. Si todos los Kproblemas de caminos m´as cortos en la red definida por yson factibles, obtendremos un corte de la forma z≥X {i,j}∈A Fijyij +X k∈K  (uk D(k)(s)−uk O(k)(s)) −X {i,j}∈A (vk ij(s) + vk ji(s))yij  (3.1) donde el miembro de la derecha representa el coste correspondiente a transportar la mercanc´ıa kbajo el escenario sy a trav´es de la estructura yde la red. Puesto que lo que queremos es minimizar el m´aximo de los posibles costes, zrepresenta el m´aximo coste de transporte de la mercanc´ıa kbajo el escenario sa trav´es de la estructura y. Para un escenario espec´ıfico de datos de entrada s∈S, la restricci´on anterior es una funci´on de zey, donde zes la variable continua en el problema maestro de Benders (BMs) para cada escenario s 83 BMs: m´ın z s.t z≥X {i,j}∈A Fijyij +X k∈K  (uk D(k)(s)−uk O(k)(s)) −X {i,j}∈A (vk ij(s) + vk ji(s))yij  yij ∈ {0,1},{i, j} ∈ A, y∈Γ. (3.2) As´ı pues, estamos minimizando el m´aximo coste que se produce bajo las estructuras de la red consideradas, es decir, se persigue encontrar aquella estructura yde tal forma que el m´aximo de todos ellos sea lo menor posible. Las constantes uk j(s) y vk ij(s) usadas en la primera restricci´on, correspondiente al corte que hemos hecho, son los valores ´optimos de las variables duales del problema DBPk(s, y). Estos valores se pueden calcular directamente como se indica a continuaci´on. Sea uk O(k)(s) = 0 y uk j(s) igual a la longitud del camino m´as corto desde O(k) al nodo jen la red definida por yy matriz distancia Ck(s). Una vez conocidos los valores de u, los valores de vk ij(s) y vk ji(s) vendr´an dados por vk ij(s) = m´ax nuk j(s)−uk i(s)−ck ij(s),0o vk ji(s) = m´ax nuk i(s)−uk j(s)−ck ji(s),0o 84 Podemos encontrar estos valores siempre que todos los problemas duales tengan soluci´on factible. En el caso en el que para alguna mercanc´ıa la red definida por yno tuviese soluci´on factible, querr´ıa decir que existir´ıa un conjunto de arcos CSkseparando O(k) de D(k) con yij = 0 para todo {i, j} ∈ CSk. A estos arcos se les denomina conjunto de corte, es decir, un subconjunto de arcos del grafo que desconecta los nodos de origen y destino para la mercanc´ıa k. Si esto ocurre, querr´ıa decir que no podemos mandar la mercanc´ıa del nodo O(k) al nodo D(k) y por lo tanto, el problema ser´ıa infactible. Por este motivo, buscamos imponer que se elija en el dise˜no de la red al menos, uno de los arcos que unen esos dos nodos. Es decir, a˜nadiremos el siguiente corte de factibilidad al problema maestro de Benders X {i,j}∈CSk yij ≥1.(3.3) De esta forma, el problema maestro de Benders es de la forma (3.2), con el conjunto Γ incluyendo todos los cortes de factibilidad de la forma (3.3) para cada mercanc´ıa kpara la cu´al D(k) no es accesible desde O(k). El conjunto de corte CSkpuede ser f´acilmente generado durante la ejecuci´on del algoritmo de caminos m´as cortos para la mercanc´ıa k. El camino m´as corto para cada producto se calcula utilizando el algoritmo de Dijkstra. Este algoritmo, sin ninguna carga computacional adicional, puede encontrar el camino m´as corto desde O(k) a todos los dem´as nodos i∈N,i6=O(k). Si el algoritmo no consigue obtener un camino desde O(k) a D(k), entonces podemos identificar todos los nodos que son accesibles desde O(k). Los cortes establecidos CSkse forman incluyendo todos los arcos, no incluidos en la soluci´on actual y, que unen un nodo alcanzable de O(k) a un nodo no 85 alcanzable de O(k). Observamos que la adici´on de un solo corte de este tipo no garantiza la accesibilidad de D(k) desde O(k). Sin embargo, la aplicaci´on repetida de estos cortes asegura que D(k) sea alcanzado. Es importante observar que la soluci´on de BMspara cada s, nos conducir´a a la generaci´on de un nuevo y. La soluci´on de los problemas de caminos m´as cortos para las distintas mercanc´ıas en la red definida por ynos permitir´a generar cortes de la forma (3.1) y (3.3) para todos los problemas maestros de Benders BMs,s∈S. Los cortes de Benders de la forma (3.1) son conocidos en la literatura de dise˜no de redes como cortes Est´andar de Benders. Estos cortes pueden interpretarse como cotas sobre la soluci´on ´optima del problema maestro de Benders correspondiente. Magnanti y al. presentaron en [16] una t´ecnica para fortalecer los cortes est´andar de Benders que daba lugar a cotas inferiores m´as finas. Estos cortes, conocidos como cortes Fuertes de Benders, tienen la capacidad de acelerar la convergencia del algoritmo de Benders. Los cortes fuertes de Benders tienen la misma forma que (3.1) pero, en lugar de usar el valor de uk j(s) y vk ij(s) descritos anteriormente, utiliza una nueva soluci´on dual nuk i(s), vk ij(s)oespecificada como sigue 86 uk O(k)(s)=0, uk D(k)(s) = uk O(k)(s), uk i(s) = m´ın nuk i(s), uk D(k)(s)−Dk io,para i6=O(k), D(k), vk ij(s) = m´ax n0, uk j(s)−uk i(s)−ck ij(s)o, donde Dk ies el m´ınimo coste de ruta de una unidad de mercanc´ıa kdesde el nodo ihasta D(k) en una red que incluye todos los arcos candidatos. Obs´ervese que el c´alculo de cortes fuertes no es computacionalmente m´as exigente que el c´alculo de los cortes est´andar, ya que las cantidades Dk ise pueden obtener durante una fase de preprocesamiento para todo i∈N, k∈K. 3.5. Algoritmo de Benders Para describir de forma pseudo-algor´ıtmica nuestro algoritmo de Benders para el problema de dise˜no robusto de redes sin capacidad, necesitaremos introducir la siguiente notaci´on. Sean UB(s) y LB(s), que denotan respectivamente una cota superior e inferior de UNDP(s). Usaremos la variable binaria SO(s) para indicar si el problema UNDP(s) ha sido resuelto de manera ´optima en este paso de nuestro procedimiento (es decir, SO(s)=1 si ha sido resuelto de manera ´optima, y SO(s) = 0 en otro caso). Una lista LRpalmacena todas las soluciones robustas (es decir, que son ε-´optimas 87 para todo s∈S). Denotamos por MP (s) el conjunto de restricciones del problema maestro de Benders para la formulaci´on UNDP (s) en este paso de nuestro procedimiento y ZMP(s) el valor objetivo ´optimo de ese problema maestro. Como es evidente, este conjunto se actualiza continuamente durante la ejecuci´on de nuestro procedimiento con la adici´on de los dem´as cortes de Benders generados. Tambi´en denotamos por z(s, y) el coste total de configuraci´on de la red ybajo el escenario sdonde z(s, y) viene dado por z(s, y) = Ws(y) + X {i,j}∈A Fijyij. El algoritmo puede ser descrito formalmente como sigue Algoritmo de Benders Paso 0: Inicializaci´on. Sea UB(s) = +∞,LB(s) = 0, y SO(s) = 0 para s= 1,...,|S|. Sea MP(s) = ∅, para s= 1,...,|S|, y LRp=∅. Calcular Dk ipara todo iyD(k), k∈K. Sea s= 1, e ir al Paso 1. Paso 1: Generaci´on del dise˜no de redes. Resolver el problema maestro para el escenario scon optimalidad. Sea y=yij la configuraci´on de red obtenida. Sea LB(s) = ZMP(s), e ir al Paso 2. 88 Bibliograf´ıa [1] J.J. Benders, Partitioning procedure for solving mixed variable programming problems, Numerische Mathematik, 1962. [2] V. Chvatal, Linear programming, W.H. Freeman and Company, 1983. [3] E.W. Dijkstra, A note on two problems in connection with graphs, Numerische Mathematik, 1959. [4] G.G. Guerrin Florian, M. and G. Bushel, The engine scheduling problem on a railway network, INFOR J., 1976. [5] S. French, Decision theory, John Wiley & Sons, 1986. [6] M.R. Garey and D.S. Johnson, Computers and intractability, W.H. Freeman, 1979. [7] B. Gavish, Topological design of centralized computer networks - formulations and algorithms, Networks, 1982. [8] A.M. Geoffrion and G. Graves, Multicommodity distribution system design by benders decomposition, Management Science, 1974. [9] G.J. Gutierrez and P. Kouvelis, Robust flowpath designs for automated guided vehicle systems, Working Paper, Management Department, University of Texas at Austin, 1996. 95 [10] F.S. Hillier and G.J. Lieberman, Introduction to mathematical programming, McGraw Hill, 1990. [11] H.H. Hoang, Topological optimization of networks: A nonlinear mixed integer model employing generalized benders decomposition, Working Paper, 1982. [12] P. Kouvelis Karabati, S. and G. Yu, A min-max-sum resource allocation problem and its applications, Working Paper, Fuqua School of Business, 1996. [13] P. Kouvelis and G. Yu, Robust discrete optimization and its applications, Working Paper, Department of MSIS, Graduate School of Business, 1995. [14] P. Kouvelis, P. Yu, G.Kouvelis, and G. Yu, Robust discrete optimization and its applications, Kluwer Academic Publisher, 1997. [15] R.C. Larson and A.R. Odoni, Urban operations research, Prentice Hall, Englewood Cliffs, 1981. [16] P. Mireault Magnanti, T.L. and R.T. Wong, Tailoring benders decomposition for uncapacitated network design, Mathematical Programming Study, 1986. [17] T.L. Magnanti and R.T. Wong, Accelerating benders decomposition: Algorithmic enhancement and model selection criteria, Operations Research, 1981. [18] , Network design and tansportation planning: Models and algorithms, Transportation Science, 1984. [19] K.G. Murty, Linear programming, Wiley, 1983. 96 [20] G.L. Nemhauser and L.A. Wolsey, Integer and combinatorial optimization, Wiley, 1988. [21] R. Richardson, An optimization approach to routing aircraft, Transportation Science, 1976. [22] M.J. Rosenblatt and H.L. Lee, A robustness approach to facilities design, International Journal of Production Research, 1987. [23] L. Stougie, Design and analysis of algorithms for stochastic integer programming, CWI Tract 37, 1987. [24] P. Toth, Dynamic programming algorithms for the zero-one knapsack problem, Computing,, 1980. 97