Método de descomposición de Benders aplicado al problema de diseño de redes con carga fija

TRABAJO FIN DE GRADO M´etodo de descomposici´on de Benders aplicado al problema de dise˜no de redes con carga fija Realizado por: Mar´ıa del Reposo Rivera Lineros Supervisado por: Eduardo Conde S´anchez FACULTAD DE MATEM´ ATICAS DPTO DE ESTAD´ ISTICA E INVESTIGACI´ ON OPERATIVA ´ Indice general 1. Introducci´on 5 2. M´etodo de descomposici´on de Benders 9 2.1. Descripci´on y esquema del algoritmo . . . . . . . . . . . . . . . . . . . . . 10 2.2. Variantes de la descomposici´on de Benders . . . . . . . . . . . . . . . . . . 12 3. Algunos problemas de dise˜no de redes con carga fija 15 3.1. Problemas de dise˜no de redes con capacidad ilimitada . . . . . . . . . . . 16 3.1.1. Origen-destino UNDP . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.1.2. Origen ´unico UNDP . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1.3. Origen ´unico, dos tecnolog´ıas UNDP . . . . . . . . . . . . . . . . . 20 3.2. Problemas de dise˜no de redes con capacidad limitada . . . . . . . . . . . . 21 3.2.1. Una ´unica tecnolog´ıa CNDP . . . . . . . . . . . . . . . . . . . . . 21 3.2.2. Varias tecnolog´ıas CNDP . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.3. CNDP con coste de capacidad escalonado . . . . . . . . . . . . . . 24 4. Una aplicaci´on al redise˜no de una red con carga fija y costes de transporte variables 27 4.1. El problema de la red ferroviaria de alta velocidad entre Espa˜na y Francia 27 4.2. Planteamiento del modelo. Algoritmo de Benders . . . . . . . . . . . . . . 29 4.3. Modelo con distintas tecnolog´ıas . . . . . . . . . . . . . . . . . . . . . . . 35 5. Experimento computacional 39 5.1. Planteamiento del problema . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.2. Resoluci´on computacional con AMPL . . . . . . . . . . . . . . . . . . . . 42 5.2.1. Fichero.dat............................... 42 5.2.2. Fichero.mod .............................. 43 5.2.3. Fichero.run............................... 45 5.2.4. Salida .................................. 49 6. Conclusiones 61 3 Abstract New communication networks are constantly emerging to improve connectivity services and facilitate the interconnection of devices of various types. This involves the development of different technologies, such as device-to-device communications, wireless sensor networks and vehicular communications. Mathematical Optimization techniques have always been at the heart of such design problems to formulate and propose computationally efficient numerical algorithms. Benders Decomposition, which is the focus of this document, is one of the more powerful techniques of Mathematical Programming. To design efficient algorithms for large scale problems, the exploitation of the mathematical structure of the problem formulation is crucial. In this way, Benders Decomposition is one the most popular schemes, because it exploits the structure of the problem and decentralizes the overall computational burden. This method was proposed by Benders in 1962, with the main objective of tackling problems with complicating variables, which, when temporarily fixed, yield a problem significantly easier to handle. The Benders Decomposition algorithm has been successfully applied to a wide range of difficult optimization problems. Successful applications are found in many different fields, including planning and scheduling, health care, transportation and telecommunications, energy and resource management and chemical process design. The main purpose of this document is to describe this method and how it can be implemented in the context of network design. We present a general algorithm based on Benders Decomposition for solving the multicommodity uncapacited fixed-charge network design problem, which is the type of problem that we will focus on. This problem is defined on a directed graph. The key feature of this model is its use in evaluating the trade-off between infrastructure investment and operational costs. The former is modeled by the fixed cost paid for using a given connection. The latter is modeled by a linear transportation cost paid per unit of commodity routed on such a connection. The goal is to route all commodities from origins to destinations at minimal cost. In the final part of this document we conduct a numerical experiment in which a transportation network is designed according to a set of costs where some of them are considered unknown when decisions are made. An extension of the classical network design formulation is proposed in order to take into consideration this drawback. 4 Cap´ıtulo 1 Introducci´on La noci´on de grafo (o de red) es de las primeras ideas que se adquieren en el estudio de estructuras abstractas. Este hecho no es una casualidad, puesto que nuestro mundo es un mundo entrelazado por redes: las que forman las personas en la sociedad, las de neuronas, la World Wide Web, las de transportes urbanos en una ciudad, las de rutas de los aeron´auticas... El dise˜no de redes constituye un ´area muy activa y relevante de la Programaci´on Matem´atica. Los problemas que comprende consisten, en general, en seleccionar de una red subyacente o potencial una subred que optimice un determinado indicador de eficiencia (funci´on objetivo) y que permita que se cumplan ciertas condiciones (restricciones), como condiciones de flujo por ejemplo. En la actualidad los problemas de dise˜no de redes de gran dimensi´on est´an muy presentes en m´ultiples contextos de la industria debido a su capacidad de modelar de manera realista multitud de procesos log´ısticos. Encontramos diversos ejemplos de aplicaciones del dise˜no de redes: Dise˜no de redes de transporte en las que la mercanc´ıa a transportar puede venir dada de diversas formas, por ejemplo, veh´ıculos (redes de carreteras, ferroviarias o a´ereas) o productos comerciales (redes que modelan la distribuci´on de productos de almacenes a comercios). Dise˜nos de redes de telecomunicaciones donde el ‘producto’ que fluye es la informaci´on, en las que se puede valorar el uso de distintas tecnolog´ıas, como es el caso de la fibra ´optica o el cobre. Planificaci´on laboral: el problema de organizar los turnos de trabajo del equipo de una empresa implica el dise˜no de un eficiente esquema en el que se alternen periodos laborables y de descanso. Este esquema debe satisfacer los requisitos de 5 personal en cada turno y debe cumplir con las condiciones correspondientes sobre la secuencia de los periodos de trabajo y descanso. En relaci´on al dise˜no de redes, Balakrishnan y Wong [15] modelan este problema como un problema de flujo. Problemas como el del ´arbol de uni´on de m´ınimo coste, el de Steiner, dise˜no de redes multiart´ıculo, el del viajante, construcci´on de redes de supervivencia y de restauraci´on, etc. son bien conocidos pero muchas de sus variantes se est´an investigando actualmente. De hecho, de algunos de ellos se sabe que se pueden resolver en tiempo polinomial y se conoce su estructura poli´edrica, pero la mayor´ıa tienen car´acter no polinomial y, por tanto, necesitan para su resoluci´on todas las herramientas posibles entre las que se encuentran descomposiciones, relajaciones o m´etodos heur´ısticos. En este trabajo nos centraremos en el problema del dise˜no de redes con carga fija. La utilidad de este tipo de problema es su capacidad para evaluar la compensaci´on entre la inversi´on en infraestructura y los costes operativos. El problema se define sobre un grafo dirigido. La inversi´on en infraestructura se modela a trav´es de los llamados costes fijos. Cada arco tiene un coste fijo asociado, el cual debe ser pagado si el arco forma parte de la soluci´on. Los costes operativos son usualmente costes de transporte y determinan el precio a pagar por el transporte de una unidad de mercanc´ıa a trav´es de un arco. El objetivo es establecer una red donde se satisfagan ciertas condiciones de flujo minimizando el gasto en costes fijos y de transporte. Para la resoluci´on de estos problemas nos centraremos en el m´etodo de descomposici´on de Benders, introducido a principio de los a˜nos sesenta como un m´etodo de resoluci´on de problemas de programaci´on entera mixta. La idea esencial del m´etodo de descomposici´on de Benders es acelerar el proceso de b´usqueda de soluciones identificando alguna estructura en el problema original que nos permita descomponerlo en dos problemas m´as sencillos de resolver. Una vez establecidos los dos problemas, se procede con el algoritmo de descomposici´on de Benders: se resuelven de manera iterada hasta que se verifique alguna condici´on que trataremos m´as adelante, existiendo una comunicaci´on entre ellos generalmente basada en la informaci´on de los problemas duales. Desde su introducci´on, la descomposici´on de Benders ha sido utilizada para resolver numerosos problemas entre los que se encuentran los de planificaciones de aerol´ıneas [16], transporte de mercanc´ıas peligrosas [17] e incluso problemas de servicios sanitarios [18]. Comenzaremos el trabajo describiendo de forma gen´erica el m´etodo de descomposici´on, exponiendo la teor´ıa sobre la que se basa y proporcionando un esquema b´asico del algoritmo necesario para su implementaci´on. En el cap´ıtulo 3 presentamos varios problemas de dise˜no de redes con carga fija a los que es aplicable el m´etodo de des6 composici´on de Benders y mencionamos los enfoques que algunos autores les han dado a estos problemas. En el cap´ıtulo 4 planteamos y desarrollamos una aplicaci´on de la descomposici´on de Benders al redise˜no de una red: el problema consiste en mejorar una red preexistente a trav´es de la creaci´on de nuevas conexiones o la mejora de la tecnolog´ıa. Finalmente, presentamos un experimento computacional: resolvemos con AMPL un problema particular del modelo desarrollado en el cap´ıtulo anterior. 7 8 Cap´ıtulo 2 M´etodo de descomposici´on de Benders A principios de los a˜nos sesenta Jacques F. Benders propone en [19] un nuevo m´etodo de resoluci´on de problemas de programaci´on matem´atica entera mixta. La dificultad de este tipo de problema reside en que, dado que algunas variables que lo definen son de naturaleza entera, no se puede usar la propiedad de convexidad de la regi´on factible, lo cual dificulta su resoluci´on. El algoritmo de Benders se basa en la idea de identificar alg´un tipo de estructura que nos permita separar el problema en dos: el problema maestro y el subproblema. De esta forma obtenemos dos problemas que de forma separada son m´as sencillos de resolver, desde el punto de vista computacional, que el problema original. Cada vez que se resuelve el subproblema obtenemos un nuevo corte que se incorpora al problema maestro, el cual propone una aproximaci´on a la soluci´on ´optima. El problema maestro y el subproblema son resueltos de forma iterativa, hasta que no se puedan generar m´as cortes o hasta que las cotas inferior y superior del ´optimo que se generan durante el proceso discrepen menos que el error establecido. La soluci´on obtenida en la ´ultima iteraci´on del problema maestro constituye la soluci´on del problema original. En particular, el tipo de problema a tratar en este trabajo, el dise˜no de redes con carga fija, presenta un esquema natural de descomposici´on: las variables de dise˜no, es decir, las variables que representan la selecci´on de los arcos y por tanto dise˜nan la red, forman parte del problema maestro, mientras que las variables que representan el flujo de mercanc´ıa son tratadas en el subproblema. De esta forma, en cada iteraci´on el problema maestro genera un posible dise˜no de la red, para el cual el subproblema identifica el flujo ´optimo de mercanc´ıa. 9 En el caso en el que la capacidad es limitada, es decir, cuando hay l´ımite en el flujo que puede circular a trav´es de los arcos, las variables yij representan la capacidad del arco (i, j). 3.1. Problemas de dise˜no de redes con capacidad ilimitada Primero consideraremos problemas de dise˜no de redes sin capacidad limitada o UNDP (uncapacitated network design problems). En estos problemas, no hay l´ımite en el flujo que puede circular a trav´es de los arcos seleccionados. 3.1.1. Origen-destino UNDP Comenzamos con el problema de dise˜no de redes origen-destino. En este caso, a cada mercanc´ıa k= 1,...,|K|se le asocia una demanda dk, un nodo origen O(k) y un nodo destino D(k). En algunos casos, los costes fijos representan completamente el coste real de la red, es decir, no hay costes asociados al volumen de la mercanc´ıa que fluye por un arco. Sin embargo, a veces para modelar adecuadamente algunos problemas es necesario establecer costes unitarios de transporte. Formulaci´on origen-destino UNDP (F1) Minimizar X (i,j)∈A X k∈K ck ijxk ij +fijyij!(3.1) sujeto a X j|(i,j)∈A xk ij −X j|(j,i)∈A xk ji =                dk, i =O(k),∀k∈K, 0, i /∈ {O(k), D(k)},∀k∈K, −dk, i =D(k),∀k∈K, (3.2) xk ij ⩽dkyij,∀(i, j)∈A, ∀k∈K, (3.3) xk ij ⩾0,∀(i, j)∈A, ∀k∈K, yij ∈ {0,1},∀(i, j)∈A. donde Las variables yij determinan la construcci´on del arco (i, j)∈A:yij = 1 si (i, j) pertenece a la soluci´on final y yij = 0 en caso contrario. Denotamos por ck ij al coste unitario de transporte de la mercanc´ıa ka trav´es del arco (i, j). 16 Denotamos por fij al coste fijo del arco (i, j), es decir, el coste que supone construir este arco. Por otra parte, La funci´on objetivo (3.1) es la suma de los costes fijos fij y de transporte ck ij. El conjunto de las restricciones (3.2) aseguran que el flujo de la mercanc´ıa kparte del nodo origen O(k) y llega al nodo destino D(k). Se denominan restricciones de balance de flujo. Las restricciones (3.3) limitan el flujo de la mercanc´ıa a los arcos seleccionados. Las restricciones (3.3) pueden ser sustituidas mediante restricciones agrupadas de la forma: X k∈K xk ij ⩽ X k∈K dk!yij,∀(i, j)∈A. (3.4) Este modelo, menos restrictivo que el anterior, supone una relajaci´on que puede reducir sustancialmente el n´umero de restricciones. Sin embargo, como indicamos anteriormente, los cortes de Benders obtenidos con formulaciones desagrupadas (mayor n´umero de restricciones) suelen ser m´as eficientes que los obtenidos con restricciones agrupadas [3]. Aplicaci´on de la descomposici´on de Benders El caso b´asico sin l´ımite de capacidad fue resuelto en uno de los primeros trabajos de Magnanti et al. [3]. En este trabajo, el problema maestro propone una red provisional a trav´es de las variables de dise˜no y el subproblema determina el flujo ´optimo bajo esta red provisional. Los autores usaron un conjunto de casos de hasta 30 nodos y 130 arcos para probar que: 1. El uso de t´ecnicas auxiliares puede mejorar el rendimiento de la descomposici´on de Benders. 2. Una elecci´on inteligente de cortes, espec´ıficamente, los cortes Pareto-´optimos, pueden afectar fuertemente al rendimiento del algoritmo. El trabajo de Magnanti et al. fue extendido diez a˜nos despu´es por Gutierrez et al. [5], donde proponen un modelo robusto capaz de tener en cuenta cierta incertidumbre en los costes de transporte ck ij y en las demandas dk. Los datos inciertos son descritos a trav´es de un conjunto de escenarios, cada uno con diferentes valores para ck ij. Observemos que, puesto que estamos tratando el caso sin capacidad limitada, las modificaciones en ck ij 17 pueden reflejar cambios tanto en los propios costes como en las demandas (trabajando con una escala adecuada). Hallamos la soluci´on a trav´es de un algoritmo de Benders multi-maestro, donde cada problema maestro individual se asocia con un posible escenario. Cada vez que un problema maestro es resuelto, el subproblema genera un corte para cada uno de los problemas maestros. 3.1.2. Origen ´unico UNDP Un importante caso particular del problema origen-destino es el caso en el que todos los puntos de demanda deben estar conectados a un origen ´unico (local access network design). Esta es la situaci´on, por ejemplo en el dise˜no de redes de ´area local (local area network, LAN ). Cuando la funci´on objetivo est´a ´unicamente definida por costes de transporte entonces el dise˜no de una red de ´area local puede ser formulado como un problema de transporte con un ´unico origen. Si la funci´on objetivo estuviera definida solo por costes fijos el problema se convierte en un problema de Steiner NP-duro o en hallar un ´arbol de uni´on de coste m´ınimo (minimum spanning tree problem) si todos los nodos deben ser alcanzados. En este ´ultimo caso, una importante situaci´on tiene lugar cuando el n´umero de arcos conectados directa o indirectamente con el origen es limitado (problema del ´arbol de uni´on de coste m´ınimo con capacidad limitada), aunque clasificamos este problema como con capacidad ilimitada dado que el flujo sobre los arcos no tiene l´ımite. Presentamos una formulaci´on para el caso general, en el que cada arco tiene asociados un coste fijo y otro variable. Formulaci´on origen ´unico UNDP (F2) Minimizar X (i,j)∈A X k∈K ck ijxk ij +fijyij! sujeto a X j|(i,j)∈A xk ij −X j|(j,i)∈A xk ji =                dk, i =O, ∀k∈K, 0, i /∈ {O, D(k)},∀k∈K, −dk, i =D(k),∀k∈K, xk ij ⩽dkyij,∀(i, j)∈A, ∀k∈K, 18 xk ij ⩾0,∀(i, j)∈A, ∀k∈K, yij ∈ {0,1},∀(i, j)∈A. En (F2) consideramos la demanda en cada nodo como una mercanc´ıa distinta, con diferentes costes de transporte ck ij que dependen de los arcos y de la mercanc´ıa. El nodo Oes el nodo origen. El sentido de esta formulaci´on es an´alogo al explicado para (F1). Salvo por el hecho de que todas las mercanc´ıas parten de un mismo nodo, (F2) es id´entica a (F1). La presencia de un nodo origen ´unico lleva a una formulaci´on simplificada en el caso en el que los costes variables sean independientes de las mercanc´ıas: Formulaci´on origen ´unico, mercanc´ıa ´unica UNDP (F0 2) Minimizar X (i,j)∈A cijxij +fijyij (3.5) sujeto a X j|(i,j)∈A xij −X j|(j,i)∈A xji =     D, i =O, −di, i 6=O, (3.6) xij ⩽Dyij,∀(i, j)∈A, (3.7) xij ⩾0,∀(i, j)∈A, yij ∈ {0,1},∀(i, j)∈A. El par´ametro direpresenta la demanda de cada nodo y Des la suma de todas las demandas excluyendo el origen. La funci´on objetivo (3.5) de la formulaci´on (F0 2) sigue minimizando la suma de los costes fijos y de transporte. Sin embargo, en este caso no es necesario diferenciar las mercanc´ıas. El ´unico requisito es que del origen salga la cantidad correcta de mercanc´ıa y que a cada nodo llegue la demandada, lo cual imponemos en las restricciones de balance de flujo (3.6). Las restricciones (3.7) proh´ıben el flujo en los arcos que no formen parte del dise˜no. Aplicaci´on de la descomposici´on de Benders En la pr´actica es conveniente hallar una inicializaci´on adecuada. Por ejemplo, en Randazzo y Luna [6], se utiliza una relajaci´on lineal y un algoritmo del camino m´as corto para obtener una soluci´on factible, la cual es usada para generar valores iniciales para las variables duales. En el problema maestro se a˜naden restricciones redundantes pero que contribuyen a incrementar la probabilidad de generar una soluci´on factible, y 19 el subproblema es descompuesto en kproblemas de flujo de red f´aciles, uno para cada mercanc´ıa. En un trabajo m´as reciente, Gavish [7] present´o un algoritmo de descomposici´on de Benders para el problema del ´arbol de uni´on de coste m´ınimo con capacidad limitada. El algoritmo es bastante est´andar, el problema maestro fija las variables enteras de dise˜no y tiene lugar una de las siguientes situaciones: Los arcos seleccionados constituyen un ´arbol de uni´on. Entonces, o bien la soluci´on es ´optima (si el n´umero de arcos conectados al origen respeta el l´ımite) o bien los arcos conectados al origen pueden utilizarse para generar un corte y obtener una nueva iteraci´on. El grafo no est´a conectado. En este caso, se puede generar un corte y resolverse el problema maestro de nuevo. 3.1.3. Origen ´unico, dos tecnolog´ıas UNDP Una tercera situaci´on com´un en los problemas de dise˜no de redes con capacidad ilimitada es el caso en el que hay disponibles dos tecnolog´ıas distintas, cada una con sus correspondientes ventajas. Por ejemplo, una tecnolog´ıa puede tener unos costes fijos mayores pero unos costes de transporte menores que la otra y viceversa (como ocurre con la fibra ´optica y el cobre en redes de telecomunicaciones). La formulaci´on es una extensi´on de (F2) con la duplicaci´on de las variables xk ij eyij. As´ı, en (F3), yijt es la variable binaria asociada a la construcci´on del arco (i, j) con la tecnolog´ıa t. An´alogamente, xk ijt es el flujo de la mercanc´ıa ka trav´es de ese arco. Formulaci´on origen ´unico, dos tecnolog´ıas UNDP (F3) Minimizar X (i,j)∈A 2 X t=1 X k∈K ck ijtxk ijt +fijtyijt!(3.8) sujeto a 2 X t=1  X j|(i,j)∈A xk ijt −X j|(j,i)∈A xk jit =                dk, i =O, ∀k∈K, 0, i /∈ {O, D(k)},∀k∈K, −dk, i =D(k),∀k∈K, (3.9) xk ijt ⩽dkyijt,∀(i, j)∈A, ∀k∈K, t = 1,2,(3.10) 2 X t=1 yijt ⩽1,∀(i, j)∈A, (3.11) 20 xk ijt ⩾0,∀(i, j)∈A, ∀k∈K, t = 1,2, yijt ∈ {0,1},∀(i, j)∈A, t = 1,2. En (F3) el objetivo (3.8) es minimizar la suma de los costes fijos y de transporte para ambas tecnolog´ıas. Se deben respetar las cantidades demandadas (3.9) y, para cada tecnolog´ıa, solo puede haber flujo si ese arco est´a abierto (3.10). Adem´as, cada arco utiliza una ´unica tecnolog´ıa (3.11). Observamos que (F3) es la formulaci´on m´as completa de las cuatro presentadas. De hecho, (F1), (F2) y (F0 2) pueden ser considerados casos particulares de (F3). Adem´as, se puede adaptar f´acilmente al caso en el que hay m´as de dos tecnolog´ıas disponibles. Aplicaci´on de la descomposici´on de Benders Randazzo et al. [8] utilizan la descomposici´on de Benders para resolver este problema. El algoritmo es muy similar al presentado en Randazzo y Luna [6] pero sin usar relajaci´on lineal. La primera soluci´on factible se obtiene a trav´es de un algoritmo del camino m´as corto considerando solo los costes de transporte. Esta soluci´on inicial es usada para generar cotas superiores e inferiores iniciales. Se a˜naden restricciones en el problema maestro con el objetivo de garantizar una soluci´on con estructura de ´arbol. El subproblema vuelve a descomponerse en problemas de flujo de red f´aciles, uno para cada mercanc´ıa. 3.2. Problemas de dise˜no de redes con capacidad limitada Consideramos ahora problemas de dise˜no de redes con capacidad limitada o CNDP (capacitated network design problems). Como antes, el flujo en un arco est´a permitido solo si se paga su coste fijo asociado. En este caso la capacidad de flujo de los arcos es limitada. Analizamos algunos modelos en las siguientes subsecciones. 3.2.1. Una ´unica tecnolog´ıa CNDP En este caso hay una ´unica tecnolog´ıa, la cual puede instalarse varias veces en cada arco. Cada unidad instalada tiene un coste y permite una cierta cantidad de flujo en ese arco. 21 Formulaci´on instalaci´on ´unica CNDP (F4) Minimizar X (i,j)∈A X k∈K ck ijxk ij +fijyij! sujeto a X j|(i,j)∈A xk ij −X j|(j,i)∈A xk ji =                dk, i =O(k),∀k∈K, 0, i /∈ {O(k), D(k)},∀k∈K, −dk, i =D(k),∀k∈K, Pk∈Kxk ij ⩽Cyij,∀(i, j)∈A, (3.12) xk ij ⩾0,∀(i, j)∈A, ∀k∈K, (3.13) yij ∈Z+,∀(i, j)∈A. En (F4) hay dos importantes modificaciones con respecto a (F1). En primer lugar, hay una ´unica restricci´on del tipo (3.12) para cada arco (en lugar de krestricciones por arco). Estas restricciones agrupan las variables xk ij como en las restricciones (3.4). Adem´as, en el lado derecho de (3.12), dkse cambia por C, la capacidad que obtenemos al adquirir una unidad de la instalaci´on. La segunda modificaci´on es que las restricciones (3.13) indican que las variables yij son enteras. Estas dos modificaciones permiten seleccionar un n´umero entero de unidades a instalar en cada arco de forma individual, proporcionando al arco una capacidad total de Cyij. Sridhar y Park [9] trabajan con una versi´on de este problema que no tiene costes de transporte. Adem´as de las restricciones que limitan la capacidad de los arcos, su modelo incluye tambi´en restricciones de capacidad para los nodos, de la forma X j|(i,j)∈AX k∈K xk ij +X k|D(k)=i dk≤κi∀i∈N, indicando que la capacidad κidel nodo idebe ser mayor o igual que la cantidad de flujo que pasa a trav´es de ´el, que se origina o que llega a ´el. La capacidad κies un par´ametro a determinar en funci´on del rendimiento de la red deseado. 3.2.2. Varias tecnolog´ıas CNDP Este problema es el an´alogo al presentado en la secci´on 3.1.3 en el caso de capacidad limitada (pero aqu´ı no suponemos origen ´unico). Adem´as de elegir la tecnolog´ıa a utilizar en cada arco, debemos tambi´en elegir la capacidad a instalar. Esta capacidad debe venir 22 dada en m´ultiplos de la capacidad que proporciona instalar una unidad de la tecnolog´ıa elegida. As´ı, dadas dos tecnolog´ıas con diferentes costes fijos unitarios fij1yfij2con diferentes capacidades unitarias C1yC2, la formulaci´on (F5) modela el problema de encontrar la red m´as barata que cumple los requisitos de demanda, cuando cada demanda tiene asociado un destino y un origen que no tiene por qu´e ser el mismo para todas. Formulaci´on dos instalaciones CNDP (F5) Minimizar X (i,j)∈A 2 X t=1 X k∈K ck ijtxk ijt +fijtyijt!(3.14) sujeto a 2 X t=1  X j|(i,j)∈A xk ijt −X j|(j,i)∈A xk jit =                dk, i =O(k),∀k∈K, 0, i /∈ {O(k), D(k)},∀k∈K, −dk, i =D(k),∀k∈K, (3.15) X k∈K xk ijt ⩽Ctyijt,∀(i, j)∈A, t = 1,2,(3.16) yijt ⩽Utzijt,∀(i, j)∈A, t = 1,2,(3.17) 2 X t=1 zijt ⩽1,∀(i, j)∈A, (3.18) xk ijt ⩾0,∀(i, j)∈A, ∀k∈K, t = 1,2, yijt ∈Z+,∀(i, j)∈A, t = 1,2. zijt ∈ {0,1},∀(i, j)∈A, t = 1,2. Las variables zijt son necesarias para limitar el n´umero de tecnolog´ıas en un arco. zijt =     1 si el arco (i, j) tiene tecnolog´ıa tinstalada 0 en caso contrario El coeficiente Utes el m´aximo n´umero de instalaciones de la tecnolog´ıa tposibles en un arco. La funci´on objetivo (3.14) minimiza la suma de los costes fijos y de transporte para ambas tecnolog´ıas. Los requisitos de demanda se cumplen gracias a las restricciones (3.15). Las restricciones (3.16) imponen los l´ımites de capacidad y las restricciones (3.17) y (3.18) aseguran que solo un tipo de tecnolog´ıa puede ser instalada en cada arco. 23 Magnanti et al. [10] proponen un caso muy similar (que aplican al dise˜no de redes de comunicaciones privadas) en el que ambas tecnolog´ıas pueden coexistir en un mismo arco, sumando las capacidades que aportan cada una. As´ı, no son necesarias las variables zijt, no es necesario el ´ındice ten las variables xk ij y las restricciones (3.16) se pueden sustituir por: X k∈K xk ij ≤C1yij1+C2yij2∀(i, j)∈A. Al igual que en la secci´on anterior, se puede convertir (F5) en un problema de origen ´unico a trav´es de modificaciones an´alogas a las del caso de capacidad ilimitada. 3.2.3. CNDP con coste de capacidad escalonado El ´ultimo caso y el m´as general es el problema de capacidad limitada en el que el coste de adquirir capacidad de flujo (el coste de realizar la instalaci´on) para un arco viene dado por una funci´on Coste(t) escalonada no decreciente que depende de la capacidad: Coste :T⊂N−→ R+ As´ı, si asociamos cada t∈Ta una cierta capacidad Cty suponemos que Ct+1 ≥Ct para cada t, t + 1 ∈Tpara que el modelo tenga sentido, el coste de adquirir una capacidad Ct+1 es mayor o igual que el coste de adquirir la capacidad Ct, es decir, Coste(t+ 1) ≥Coste(t). Utilizamos la formulaci´on (F6) para modelar este caso, en el que debido a las discontinuidades de la funci´on de coste, es necesario crear variables binarias adicionales. En esta formulaci´on, Ctes la capacidad permitida en un arco si el arco se encuentra en el nivel tde la funci´on de coste. Formulaci´on del CNDP con coste de capacidad escalonado (F6) Minimizar X (i,j)∈A X k∈K ck ijxk ij + T X t=1 fijtyijt!(3.19) sujeto a X j|(i,j)∈A xk ij −X j|(j,i)∈A xk ji =                dk, i =O(k),∀k∈K, 0, i /∈ {O(k), D(k)},∀k∈K, −dk, i =D(k),∀k∈K, (3.20) 24 X k∈K xk ij ⩽ T X t=1 Ctyijt,∀(i, j)∈A, (3.21) T X t=1 yijt ⩽1,∀(i, j)∈A, (3.22) xk ij ⩾0,∀(i, j)∈A, ∀k∈K, yijt ∈ {0,1},∀(i, j)∈A, t = 1, . . . , T. De nuevo, la funci´on objetivo (3.19) consiste en minimizar los costes fijos y de transporte. Las restricciones (3.20) garantizan que se satisfacen los requisitos de demanda mientras que las restricciones (3.21) limitan el flujo en cada arco de acuerdo con la capacidad adquirida. Las restricciones (3.22) imponen que solo una variable yijt puede ser seleccionada, es decir en cada arco solo es posible instalar una capacidad Ct, la cual supone un coste Coste(t). Es com´un expresar la formulaci´on (F6) equivalentemente como una formulaci´on basada en caminos. En este caso, sea P(k) el conjunto de los posibles caminos entre los nodos O(k) y D(k). El coeficiente akp(i,j)vale 1 si la mercanc´ıa kfluyendo en el camino putiliza el arco (i, j) y 0 en caso contrario. Por otra parte, sea nkp el flujo de mercanc´ıa ken el camino p. La formulaci´on (F0 6) modela esta situaci´on. Formulaci´on del CNDP con coste de capacidad escalonado (F0 6) Minimizar X (i,j)∈A X k∈K ck ijxk ij + T X t=1 fijtyijt! sujeto a xk ij =X p akp(i,j)nkp,∀(i, j)∈A, ∀k∈K, (3.23) X p npk =dk∀k∈K, (3.24) X k∈K xk ij ⩽ T X t=1 Ctyijt,∀(i, j)∈A, (3.25) T X t=1 yijt ⩽1,∀(i, j)∈A, (3.26) nkp ⩾0,∀p∈P,∀k∈K, xk ij ⩾0,∀(i, j)∈A, ∀k∈K, yijt ∈ {0,1},∀(i, j)∈A, t = 1, . . . , T. 25 l´ımites inferiores y superiores de flujo. Por la proposici´on 4.2.1 es suficiente probar que Ces TU: las condiciones suficientes de la proposici´on 4.2.2 se satisfacen con M1=My M2=∅. Estos resultados justifican que si el problema (P), que es un problema de flujo, es factible entonces tiene alguna una soluci´on entera. Adem´as permiten el uso del problema dual (D) incluso cuando se exige la integridad de las variables de flujo. El problema original que resolvemos, que denotaremos por (P∗), tiene como variables de decisi´on las de dise˜no, las de flujo y adem´as los costes cij suponemos que son tambi´en variables. Por ejemplo, podemos modelar que una de las conexiones sufre retraso en su construcci´on mediante un coste de transporte muy elevado, de esta forma repercutir´ıamos los costes por demora. Una vez elegido un dise˜no factible y∈Y, el modelo eval´ua la red mediante el coste de carga fija al que se a˜nade el menor coste de transporte que ser´ıa necesario en el caso en que se diese el peor escenario posible. Por ejemplo, podr´ıamos tomar como costes cij los costes promedios para un cierto periodo y elevar sustancialmente dichos costes en el caso de no estar disponible la conexi´on correspondiente durante parte de dicho periodo (como posiblemente ocurrir´a con los retrasos en las fechas acordadas en el problema de la red ferroviaria de alta velocidad). Formulamos este problema como: (P∗) Minimizar X (i,j)∈A fijyij + m´ax c∈Cm´ın X (i,j)∈A cijxij sujeto a X j xij −X k xki =di∀i∈N, 0≤xij ≤Dyij ∀(i, j)∈A, y∈Y. Esta forma de modelar la funci´on objetivo supone que, dado que los costes de transporte son desconocidos, podemos tomar decisiones ‘conservadoras’ evalu´andolas mediante su coste en el peor de los casos, y por tanto en la funci´on objetivo consideramos el mayor coste que se pueda dar. Asumimos que Cse puede modelar con restricciones lineales en cij, (i, j)∈Ay que es acotado. Los costes de carga fijos fij para cada arco (i, j)∈Ase suponen conocidos, al igual que la demanda dien cada nodo i∈N. Tambi´en podemos incluir en el modelo restricciones lineales para modelar condiciones t´ecnicas, por ejemplo: 32 X (i,j)∈A yij ≤(≥)m,m∈Z, restricci´on que representa una cota superior (inferior) sobre el n´umero de nuevas conexiones. Este tipo de restricci´on podr´ıa ayudar a exigir que no se produzca la desconexi´on de parte de la red. yij ≤ypq, restricci´on que fuerza a construir la conexi´on (p, q) en el caso de que se construya la conexi´on (i, j). Denotaremos por (P∗)0a la parte interior del problema: (P∗)0m´ax c∈Cm´ın X (i,j)∈A cijxij sujeto a X j|(i,j)∈A xij −X k|(k,i)∈A xki =di∀i∈N, 0≤xij ≤Dyij ∀(i, j)∈A. Usando el dual (D) podemos reformular (P∗)0como sigue: (SP) Maximizar X i∈N diui+X (i,j)∈A (Dyij)vij sujeto a ui−uj+vij ≤cij ∀(i, j)∈A, c∈C, uis.r. ∀i∈N, vij ≤0,∀(i, j)∈A. Teorema 4.2.2 (Dualidad fuerte).Si (P)y(D)son factibles, entonces existen soluciones ´optimas de ambos problemas y los valores objetivos ´optimos coinciden. Demostraci´on. Puede encontrarse en Bazaraa et al. Cap´ıtulo 6 [11].  Proposici´on 4.2.4. Los valores objetivos ´optimos de (P∗)0y(SP)coinciden. Demostraci´on. Denotamos por h(c), con c∈C, al valor objetivo ´optimo del problema (P): 33 (P) Minimizar X (i,j)∈A cijxij sujeto a X j|(i,j)∈A xij −X k|(k,i)∈A xki =di∀i∈N, 0≤xij ≤Dyij ∀(i, j)∈A. Sabemos que h(c) est´a bien definido porque en la red original es posible enviar un flujo factible (ya que se trata de mejorar su coste mediante una inversi´on extra). Por tanto (P∗)0≡m´ax c∈Ch(c). Por otro lado, por el teorema anterior, se tiene para cada c∈Cque h(c) = m´ax X i∈N diui+X (i,j)∈A (Dyij)vij s.a. ui−uj+vij ≤cij ∀(i, j)∈A, c∈C, us.r., vij ≤0,∀(i, j)∈A. Esto es, m´ax c∈Ch(c) coincide con el valor objetivo ´optimo de (SP).  Este resultado justifica que, tras resolver el subproblema (SP) en el algoritmo de Benders, si a su valor objetivo le sumamos el gasto en costes fijos, obtenemos una cota superior del problema original. Observamos que el problema (P∗) tiene objetivo cuadr´atico no convexo. Sin embargo, al aplicar dualidad fuerte al problema de optimizaci´on interior (P) el subproblema resultante s´ı es lineal y por tanto se puede resolver f´acilmente. El m´etodo de descomposici´on de Benders nos permite, por tanto, resolver un problema inicialmente de objetivo cuadr´atico no convexo a trav´es de la resoluci´on iterada de problemas lineales. El conjunto factible de este problema no depende de y, por lo que se puede razonar como en el segundo cap´ıtulo. En esta situaci´on, aplicamos el esquema de Benders como sigue: 1. Se elige un dise˜no de la red y0∈Y(puede ser la red original cuya eficiencia se quiere mejorar). 2. Se resuelve el subproblema (SP). 34 3. Sea (u0, v0, c0) la soluci´on ´optima obtenida. Construir el corte de la forma (2.10): X i∈N diu0 i+X (i,j)∈A Dv0 ijyij ≤z y a˜nadirlo al problema maestro. El valor X (i,j)∈A fijy0 ij +X i∈N diu0 i+X (i,j)∈A (Dy0 ij)v0 ij es una cota superior del problema original. 4. Resolver el problema maestro, obteniendo as´ı una cota inferior del problema original. Si las cotas superior e inferior se consideran suficientemente cercanas, se detiene el algoritmo. 5. Volver al segundo paso, resolviendo (SP) con el vector yobtenido en el problema maestro y cambiando el super´ındice 0 por el correspondiente. En cada iteraci´on, el problema maestro ser´ıa un problema lineal entero de la forma Minimizar X (i,j)∈A fijyij +z sujeto a X i∈N diut i+X (i,j)∈A Dvt ijyij ≤z, t = 0,1, . . . y∈Y. Teorema 4.2.3. El algoritmo termina en un n´umero finito de pasos. Demostraci´on. Como el conjunto de puntos extremos de (SP) es finito, el n´umero de cortes introducidos en el problema maestro es finito y cuando se han introducido todos, el problema maestro es equivalente al problema original, que por hip´otesis tiene soluci´on.  4.3. Modelo con distintas tecnolog´ıas En este modelo podemos considerar otro tipo de mejora adem´as de la creaci´on de nuevas conexiones: la selecci´on de la tecnolog´ıa a utilizar en cada arco. Podemos suponer que ahora disponemos de dos tecnolog´ıas, que en la red preexistente se utiliza la misma en todos los arcos y que podemos instalar cualquier tecnolog´ıa en estas conexiones ya fijas. Adem´as, supondremos tambi´en que en cada conexi´on solo se puede utilizar una tecnolog´ıa. Consideramos los conjuntos: 35 Y1⊂A, el conjunto de los arcos de la red preexistente. Y2⊂A, el conjunto de los arcos que no existen en la red a mejorar. En estas condiciones, Y1∪Y2=A. Las variables de dise˜no en este problema ser´an yijt,∀(i, j)∈A,t= 1,2. A las conexiones del conjunto Y1hay que asignarles una tecnolog´ıa y las conexiones del conjunto Y2podr´an o no, estar en la nueva red. Esto puede modelar diferentes tipos de trazado ferroviario de acuerdo a la velocidad m´axima a la que puede circular el tren en el ejemplo del corredor de alta velocidad del principio del cap´ıtulo. Con esto, podemos formular este problema como: (¯ P∗) Minimizar X (i,j)∈A 2 X t=1 fijtyijt + m´ax c∈Cm´ın X (i,j)∈A 2 X t=1 cijtxijt sujeto a 2 X t=1  X j|(i,j)∈A xijt −X k|(k,i)∈A xkit =di∀i∈N, 0≤xijt ≤Dyijt ∀(i, j)∈A;t= 1,2, 2 X t=1 yijt = 1 ∀(i, j)∈Y1, 2 X t=1 yijt ≤1∀(i, j)∈Y2. En este caso, los vectores de dise˜no ¯ypertenecen a ¯ Y⊂ {0,1}2|A|, donde ¯ Yse modela por simplicidad a trav´es de las restricciones lineales 2 X t=1 ¯yijt = 1 ∀(i, j)∈Y1, 2 X t=1 ¯yijt ≤1∀(i, j)∈Y2, aunque se podr´ıan a˜nadir otras restricciones como se ha comentado en la secci´on anterior. Los costes cijt pertenecen al conjunto ¯ C, que suponemos que se puede modelar con restricciones lineales en cijt. As´ı, el esquema de la descomposici´on de Benders correspondiente ser´ıa: 1. Se elige un redise˜no de la red ¯y0∈¯ Y. 2. Se resuelve el subproblema (SP): 36 (SP) Maximizar X i∈N diui+ 2 X t=1 X (i,j)∈A (Dyijt)vijt sujeto a ui−uj+vijt ≤cijt ∀(i, j)∈A, t = 1,2; c∈¯ C, uis.r. ∀i∈N, vijt ≤0,∀(i, j)∈A, t = 1,2. 3. Sea (u0, v0, c0) la soluci´on ´optima del dual obtenida. Construir el corte de la forma (2.10): X i∈N diu0 i+ 2 X t=1 X (i,j)∈A Dv0 ijtyijt ≤z y a˜nadirlo al problema maestro. El valor 2 X t=1 X (i,j)∈A fijty0 ijt +X i∈N diu0 i+ 2 X t=1 X (i,j)∈A (Dy0 ijt)v0 ijt es una cota superior del problema original. 4. Resolver el problema maestro, obteniendo as´ı una cota inferior del problema original. Si las cotas superior e inferior se consideran suficientemente cercanas, se detiene el algoritmo. 5. Volver al segundo paso, resolviendo (SP) con el vector yobtenido en el problema maestro y cambiando el super´ındice 0 por el correspondiente. 37 38 Cap´ıtulo 5 Experimento computacional Trabajaremos con el modelo presentado en el cap´ıtulo anterior: el objetivo del problema ser´a mejorar una red preexistente a trav´es de la creaci´on de nuevas conexiones optimizando los costes de transporte y los de carga fija. Para ello seguiremos el esquema del algoritmo de Benders expuesto en el cap´ıtulo anterior. Lo resolveremos mediante AMPL utilizando el solver Gurobi. 5.1. Planteamiento del problema Consideramos el siguiente grafo dirigido: C1 1500C1 1500 C1 1500C1 1500 C4 1500C4 1500 C1 500C1 500 C1 1500C1 1500 C4 1500C4 1500 C1 500C1 500 C2 500C2 500 C1 500C1 500 C1 500C1 500 C1 500C1 500 C1 500C1 500 C3 500C3 500 C3 7000C3 7000 C3 500C3 500 C3 800C3 800 C3 800C3 800 C3 800C3 800 C3 800C3 800C3 800C3 800 N1 (10)N1 (10) N2N2 N3N3 N4N4 N5N5 N6N6 N7N7 N8 (-7)N8 (-7) N9N9 N14N14 N15N15 N16N16N13 (10)N13 (10) N10 (7)N10 (7) N11 (-5)N11 (-5) N12 (-15)N12 (-15) Figura 5.1: Grafo G(N, A, K) del problema 39 Los elementos del grafo G(N, A, K) son: 16 Nodos: N={N1, N2, . . . , N16}. 20 Arcos: A={(N1, N2),(N2, N3),(N3, N4),(N1, N5),(N3, N7),(N4, N8), (N5, N6),(N6, N7),(N7, N8),(N10, N6),(N7, N11),(N8, N12),(N9, N10), (N10, N11),(N13, N9),(N15, N11),(N16, N12),(N13, N14),(N14, N15), (N15, N16)}. Supondremos por simplicidad una ´unica mercanc´ıa: K={1}. La red preexistente viene definida por 9 de los 20 arcos del grafo y est´a indicada en rojo en la representaci´on gr´afica: {(N1, N5),(N5, N6),(N6, N7),(N7, N8),(N10, N6), (N7, N11),(N8, N12),(N9, N10),(N13, N9)}. Hay tres nodos de flujo positivo (que se corresponde con la salida de mercanc´ıa), representados en azul: N1, N10, y N13, con valores de flujo respectivos 10, 7, y 10. Hay tres nodos de flujo negativo (que se corresponde con la llegada de mercanc´ıa), representados en verde: N8, N11, y N12, con valores de flujo respectivos −7, −5, y −15. El flujo en el resto de nodos lo consideramos nulo. Observamos que la red preexistente es compatible con estos flujos. Los costes fijos de los arcos se indican en la representaci´on gr´afica y para los costes de transporte variables realizamos una partici´on de los arcos en cuatro conjuntos: C1, C2,C3yC4, indicada tambi´en en la representaci´on gr´afica. En cada conjunto los costes var´ıan dentro de un intervalo: Conjunto Intervalo del coste de transporte C1 [600, 950] C2 [2700, 3500] C3 [1000, 3300] C4 [200, 550] El poliedro de costes de transporte Cas´ı definido es un hipercubo en R27. Por la construcci´on del modelo, el punto extremo cuyas componentes son los costes m´aximos de cada intervalo dominar´a a todo el conjunto poli´edrico Cy el algoritmo tomar´a siempre este punto para los costes de transporte del peor escenario, perdi´endose as´ı su variabilidad. Esto no ser´a cierto en general puesto que el modelo asume que el conjunto C puede ser un poliedro arbitrario. Para introducir esta caracter´ıstica de un modo sencillo en nuestro ejemplo, vamos a considerar una restricci´on adicional de la forma: X (i,j)∈A cij ≤M 40 con M∈R+. Podemos visualizar esta situaci´on en R2: RR R'R' ss AA Figura 5.2 si el conjunto poli´edrico de costes de transporte fuera el rect´angulo Rde la figura 5.2, el punto Adominar´ıa todo el conjunto. Si introducimos el corte definido por la recta s y el sentido del vector normal que aparece en la figura, no hay ning´un vector de costes que domine todo el conjunto resultante R0. En nuestro caso introduciremos el corte X (i,j)∈A cij ≤35000. Este corte impide que el algoritmo seleccione para los costes de transporte el punto extremo cuyas componentes son los costes m´aximos posibles (por ejemplo, cij = 950 si el arco (i, j) pertenece al grupo C1) puesto que, considerando cij con el m´aximo valor posible para cada arco (i, j) , se tiene que X (i,j)∈A cij = 39550. 41 objoriginal: el valor objetivo del problema original en esa iteraci´on. sup einf: cota superior y cota inferior respectivamente. R1.dual: valor de las variables duales asociadas a las restricciones R1, que representan el flujo en cada arco. costes: vector de costes obtenido en el subproblema. corte.body: valor que toma la suma de la restricci´on corte al resolver el subproblema, es decir, el valor de X (i,j)∈A cij con los cij obtenidos en el subproblema. Para el test de salida consideramos un gap de 10−5, cuando las cotas superior e inferior se encuentren suficientemente pr´oximas se detiene el algoritmo. Esto lo indicamos en las l´ıneas: if sup > inf + 0.00001 then{...} else break; Si tras resolver el subproblema el bucle no se detiene, introducimos el corte correspondiente para el problema maestro haciendo uso de las variables obtenidas en el subproblema: let ncorte := ncorte +1; let {i in nodos} U[i,ncorte] := u[i]; let {(i,j) in arcos} V[i,j,ncorte] := v[i,j]; En cada iteraci´on introducimos un corte m´as al problema maestro, por lo que aumentamos en una unidad el par´ametro ncorte y en las siguientes dos l´ıneas proporcionamos los coeficientes que definen dicho corte, que se corresponden con las variables obtenidas en el subproblema. Despu´es de esto, resolvemos el problema maestro (solve Maestro) y utilizamos el comando expand para mostrar en pantalla la formulaci´on de este problema, lo que nos permite ver los cortes que se van construyendo (en las ´ultimas iteraciones la formulaci´on ser´a muy extensa puesto que los cortes se van acumulando). Finalmente, actualizamos los valores del vector de par´ametros build con los valores obtenidos en el vector de dise˜no ydel problema maestro, que adem´as mostramos en pantalla (display y). Recordamos que la cota superior la proporciona el valor objetivo original del problema: let objoriginal := SP + sum{(i,j) in variables} y[i,j]*costesfijos[i,j] + costeredprevia; if objoriginal < sup && ncorte > 0 then{ let sup := objoriginal;}; 48 y la cota inferior la proporciona el valor objetivo del problema maestro: if CosteTotal > inf then{ let inf := CosteTotal;}; Finalmente, param solucion{arcos}; let {(i,j) in variables} solucion[i,j] := y[i,j]; let {(i,j) in arcos: valor[i,j] = 1} solucion[i,j] := valor[i,j]; display solucion; Mostramos solucion, que es el vector de las variables de dise˜no(visualizando tambi´en las componentes fijas de los arcos que ya estaban en la red). 5.2.4. Salida Al ejecutar el fichero .run, obtenemos que el algoritmo se detiene tras 66 iteraciones (se construyen 65 cortes), de las cuales mostramos las dos primeras y las dos ´ultimas (en la pen´ultima no expandiremos el problema maestro debido a su extensi´on): D = 27 costeredprevia = 4500 ITERATION 1 SUBPROBLEMA: Gurobi 10.0.0: Gurobi 10.0.0: optimal solution; objective 184300 4 simplex iterations objoriginal = 188800 sup = Infinity inf = 0 : R1.dual costes := N1 N2 10 950 N1 N5 0 600 49 N10 N11 2.5 1850 N10 N6 9.5 950 N13 N14 5 3300 N13 N9 5 3300 N14 N15 5 3300 N15 N11 2.5 1850 N15 N16 2.5 3300 N16 N12 2.5 3050 N2 N3 10 950 N3 N4 10 550 N3 N7 0 600 N4 N8 10 550 N5 N6 0 600 N6 N7 9.5 3500 N7 N11 0 600 N7 N8 9.5 950 N8 N12 12.5 950 N9 N10 5 3300 ; corte.body = 35000 PROBLEMA MAESTRO: Gurobi 10.0.0: Gurobi 10.0.0: optimal solution; objective 188800 0 simplex iterations minimize CosteTotal: 1500*y[’N1’,’N2’] + 1500*y[’N2’,’N3’] + 1500*y[’N3’,’N4’] + 1500*y[’N3’,’N7’] + 1500*y[’N4’,’N8’] + 7000*y[’N10’,’N11’] + 800*y[’N15’,’N11’] + 800*y[’N16’,’N12’] + 800*y[’N13’,’N14’] + 800*y[’N14’,’N15’] + 800*y[’N15’,’N16’] + z + 4500; subject to R2[1]: z >= 184300; y := N1 N2 0 N10 N11 0 50 N13 N14 0 N14 N15 0 N15 N11 0 N15 N16 0 N16 N12 0 N2 N3 0 N3 N4 0 N3 N7 0 N4 N8 0 ; ITERATION 2 SUBPROBLEMA: Gurobi 10.0.0: Gurobi 10.0.0: optimal solution; objective 235550 9 simplex iterations objoriginal = 240050 sup = 240050 inf = 188800 : R1.dual costes := N1 N2 0 950 N1 N5 10 950 N10 N11 0 3300 N10 N6 17 950 N13 N14 0 1000 N13 N9 10 3300 N14 N15 0 1000 N15 N11 0 3300 N15 N16 0 3300 N16 N12 0 3300 N2 N3 0 950 N3 N4 0 550 N3 N7 0 950 N4 N8 0 550 N5 N6 10 950 51 N6 N7 27 3500 N7 N11 5 950 N7 N8 22 950 N8 N12 15 950 N9 N10 10 3300 ; corte.body = 34950 PROBLEMA MAESTRO: Gurobi 10.0.0: Gurobi 10.0.0: optimal solution; objective 189600 0 simplex iterations minimize CosteTotal: 1500*y[’N1’,’N2’] + 1500*y[’N2’,’N3’] + 1500*y[’N3’,’N4’] + 1500*y[’N3’,’N7’] + 1500*y[’N4’,’N8’] + 7000*y[’N10’,’N11’] + 800*y[’N15’,’N11’] + 800*y[’N16’,’N12’] + 800*y[’N13’,’N14’] + 800*y[’N14’,’N15’] + 800*y[’N15’,’N16’] + z + 4500; subject to R2[1]: z >= 184300; subject to R2[2]: 68850*y[’N3’,’N7’] + 90450*y[’N4’,’N8’] + 56700*y[’N10’,’N11’] + 180900*y[’N15’,’N11’] + 117450*y[’N15’,’N16’] + z >= 235550; y := N1 N2 0 N10 N11 0 N13 N14 0 N14 N15 0 N15 N11 1 N15 N16 0 N16 N12 0 N2 N3 0 N3 N4 0 N3 N7 0 N4 N8 0 52 ; ITERATION 65 SUBPROBLEMA: Gurobi 10.0.0: Gurobi 10.0.0: optimal solution; objective 193175 3 simplex iterations objoriginal = 213175 sup = 204450 inf = 204300 : R1.dual costes := N1 N2 10 950 N1 N5 0 600 N10 N11 2.5 2025 N10 N6 9.5 950 N13 N14 5 3300 N13 N9 5 3300 N14 N15 5 3300 N15 N11 2.5 2025 N15 N16 2.5 3050 N16 N12 2.5 3300 N2 N3 10 950 N3 N4 0 200 N3 N7 10 950 N4 N8 0 200 N5 N6 0 600 N6 N7 9.5 3500 N7 N11 0 600 N7 N8 19.5 950 N8 N12 12.5 950 N9 N10 5 3300 ; corte.body = 35000 53 PROBLEMA MAESTRO: Gurobi 10.0.0: Gurobi 10.0.0: optimal solution; objective 204450 60 simplex iterations 1 branching nodes y := N1 N2 1 N10 N11 0 N13 N14 1 N14 N15 1 N15 N11 1 N15 N16 0 N16 N12 0 N2 N3 1 N3 N4 1 N3 N7 0 N4 N8 1 ; ITERATION 66 SUBPROBLEMA: Gurobi 10.0.0: Gurobi 10.0.0: optimal solution; objective 191550 11 simplex iterations objoriginal = 204450 sup = 204450 inf = 204450 : R1.dual costes := N1 N2 10 950 N1 N5 0 600 N10 N11 0 1000 N10 N6 12 950 N13 N14 5 3300 N13 N9 5 3300 54 N14 N15 5 3300 N15 N11 5 3300 N15 N16 0 3300 N16 N12 0 2450 N2 N3 10 950 N3 N4 10 550 N3 N7 0 600 N4 N8 10 550 N5 N6 0 600 N6 N7 12 3500 N7 N11 0 600 N7 N8 12 950 N8 N12 15 950 N9 N10 5 3300 ; corte.body = 35000 solucion := N1 N2 1 N1 N5 1 N10 N11 0 N10 N6 1 N13 N14 1 N13 N9 1 N14 N15 1 N15 N11 1 N15 N16 0 N16 N12 0 N2 N3 1 N3 N4 1 N3 N7 0 N4 N8 1 N5 N6 1 N6 N7 1 N7 N11 1 N7 N8 1 N8 N12 1 N9 N10 1 55 ; R1.dual := N1 N2 10 N1 N5 0 N10 N11 0 N10 N6 12 N13 N14 5 N13 N9 5 N14 N15 5 N15 N11 5 N15 N16 0 N16 N12 0 N2 N3 10 N3 N4 10 N3 N7 0 N4 N8 10 N5 N6 0 N6 N7 12 N7 N11 0 N7 N8 12 N8 N12 15 N9 N10 5 ; 56 En la figura siguiente podemos visualizar el redise˜no de la red obtenido, las nuevas conexiones construidas las representamos en morado. C1 1500C1 1500 C1 1500C1 1500 C4 1500C4 1500 C1 500C1 500 C1 1500C1 1500 C4 1500C4 1500 C1 500C1 500 C2 500C2 500 C1 500C1 500 C1 500C1 500 C1 500C1 500 C1 500C1 500 C3 500C3 500 C3 7000C3 7000 C3 500C3 500 C3 800C3 800 C3 800C3 800 C3 800C3 800 C3 800C3 800C3 800C3 800 N1 (10)N1 (10) N2N2 N3N3 N4N4 N5N5 N6N6 N7N7 N8 (-7)N8 (-7) N9N9 N14N14 N15N15 N16N16N13 (10)N13 (10) N10 (7)N10 (7) N11 (-5)N11 (-5) N12 (-15)N12 (-15) Figura 5.3: Red mejorada Teniendo en cuenta los flujos ´optimos (R1.dual) vemos que las conexiones de la red preexistente (N1,N5) y (N5,N6) quedan sin utilizar, a pesar de que los costes de transporte son los mismos que los de las conexiones que las sustituyen. Esto es debido a que la conexi´on (N6,N7), por la que deber´ıa circular la mercanc´ıa si se utilizasen los dos arcos anteriores tiene costes de transporte muy elevados. Observamos tambi´en que el elevado coste de esa conexi´on fuerza a que la conexi´on (N7,N11) tambi´en quede sin utilizar. Recordemos que, dado un dise˜no de la red, el subproblema (SP) (a trav´es de su versi´on dual) determina el flujo ´optimo y proporciona el gasto en costes de transporte en el peor de los casos para este flujo. Despu´es, el problema maestro genera otro dise˜no de red tratando de minimizar los costes fijos y teniendo en cuenta la informaci´on proporcionada por el subproblema a trav´es de cortes. En nuestro experimento, la red 57 [13] Ahuja RK, Magnanti TL, Orlin JB. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. [14] Wolsey LA. Integer Programming. Wiley, 1998. [15] Balakrishnan N, Wong RT. A network model for the rotating workforce scheduling problem. Networks, 20:25-42, 1990. [16] Cordeau JF. Stojkovic G, Soumis F, Desrosiers J. Benders decomposition for simultaneous aircraft routing and crew scheduling. Transportation Science, 35:375-388, 2001. [17] Fontaine P, Minner S. Benders decomposition for the hazmat transport network design problem. European Journal of Operational Research, 267(1):996-1002, 2018. [18] Zarrinpoor N, Fallanhnezhad MS, Pishvaee MS. The design of a reliable and robust hierarchical health service network using an accelerated Benders decomposition algorithm. European Journal of Operational Research, 265(3):1013-1032, 2018. [19] Benders JF. Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4:238-262, 1962. 64