Contributions to robust and bilevel optimization models for decision-making
Abstract
Los problemas de optimización combinatorios han sido ampliamente estudiados en la literatura especializada desde mediados del siglo pasado. No obstante, en las últimas décadas ha habido un cambio de paradigma en el tratamiento de problemas cada vez más realistas, en los que se incluyen fuentes de aleatoriedad e incertidumbre en los datos, múltiples criterios de optimización y múltiples niveles de decisión. Esta tesis se desarrolla en este contexto. El objetivo principal de la misma es el de construir modelos de optimización que incorporen aspectos inciertos en los parámetros que de nen el problema así como el desarrollo de modelos que incluyan múltiples niveles de decisión. Para dar respuesta a problemas con incertidumbre usaremos los modelos Minmax Regret de Optimización Robusta, mientras que las situaciones con múltiples decisiones secuenciales serán analizadas usando Optimización Binivel. En los Capítulos 2, 3 y 4 se estudian diferentes problemas de decisión bajo incertidumbre a los que se dará una solución robusta que proteja al decisor minimizando el máximo regret en el que puede incurrir. El criterio minmax regret analiza el comportamiento del modelo bajo distintos escenarios posibles, comparando su e ciencia con la e ciencia óptima bajo cada escenario factible. El resultado es una solución con una eviciencia lo más próxima posible a la óptima en el conjunto de las posibles realizaciones de los parámetros desconocidos. En el Capítulo 2 se estudia un problema de diseño de redes en el que los costes, los pares proveedor-cliente y las demandas pueden ser inciertos, y además se utilizan poliedros para modelar la incertidumbre, permitiendo de este modo relaciones de dependencia entre los parámetros. En el Capítulo 3 se proponen, en el contexto de la secuenciación de tareas o la computación grid, versiones del problema del camino más corto y del problema del viajante de comercio en el que el coste de recorrer un arco depende de la posición que este ocupa en el camino, y además algunos de los parámetros que de nen esta función de costes son inciertos. La combinación de la dependencia en los costes y la incertidumbre en los parámetros da lugar a dependencias entre los parámetros desconocidos, que obliga a modelar los posibles escenarios usando conjuntos más generales que los hipercubos, habitualmente utilizados en este contexto. En este capítulo, usaremos poliedros generales para este cometido. Para analizar este primer bloque de aplicaciones, en el Capítulo 4, se analiza un modelo de optimización en el que el conjunto de posibles escenarios puede ser alterado mediante la realización de inversiones en el sistema. En los problemas estudiados en este primer bloque, cada decisión factible es evaluada en base a la reacción más desfavorable que pueda darse en el sistema. En los Capítulos 5 y 6 seguiremos usando esta idea pero ahora se supondrá que esa reacción a la decisión factible inicial está en manos de un adversario o follower. Estos dos capítulos se centran en el estudio de diferentes modelos binivel. La Optimización Binivel aborda problemas en los que existen dos niveles de decisión, con diferentes decisores en cada uno ellos y la decisión se toma de manera jerárquica. En concreto, en el Capítulo 5 se estudian distintos modelos de jación de precios en el contexto de selección de carteras de valores, en los que el intermediario nanciero, que se convierte en decisor, debe jar los costes de invertir en determinados activos y el inversor debe seleccionar su cartera de acuerdo a distintos criterios. Finalmente, en el Capítulo 6 se estudia un problema de localización en el que hay distintos decisores, con intereses contrapuestos, que deben determinar secuencialmente la ubicación de distintas localizaciones. Este modelo de localización binivel se puede aplicar en contextos como la localización de servicios no deseados o peligrosos (plantas de reciclaje, centrales térmicas, etcétera) o en problemas de ataque-defensa. Todos estos modelos se abordan mediante el uso de técnicas de Programación Matemática. De cada uno de ellos se analizan algunas de sus propiedades y se desarrollan formulaciones y algoritmos, que son examinados también desde el punto de vista computacional. Además, se justica la validez de los modelos desde un enfoque de las aplicaciones prácticas. Los modelos presentados en esta tesis comparten la peculiaridad de requerir resolver distintos problemas de optimización encajados.
Full text
Programa de doctorado Matemáticas PhD Dissertation Contributions to robust and bilevel optimization models for decision-making Author Marina Leal Palazón Supervisors Prof. Dr. Eduardo Conde Sánchez Prof. Dr. Justo Puerto Albandoz February 22, 2019
some text to complete some text to complete some text to complete some text to complete some text to complete some text to complete some text to complete some text to complete some text to complete A mis padres y mi hermana. A Jose.
Agradecimientos La vida es cuestión de decisiones. Y esta tesis es la consecuencia de una de las mías. Y de más gente. Hacer un doctorado nunca estuvo entre mis planes. Creo que pocas veces lo había contemplado como una de las opciones. Se convirtió en opción tras un correo que Alfredo Marín me reenvío, en el que buscaban a un estudiante con este propósito. Gracias Alfredo por mostrarme esta puerta que tantas cosas buenas me ha traído cruzarla. Estos cuatro años de doctorado no sólo han sido horas tratando de comprender artículos, escribir modelos o implementar código, que también; han sido aprender de la mano de matemáticos, compartiendo horas delante de folios en blanco encuadernados o de un montón de folios en sucio. Han sido aprender viajando, escuchando el trabajo de otros y compartiendo el mío. Gracias Justo y Eduardo por guiarme, con paciencia. Por sentaros conmigo las horas que hiciesen falta. Por vuestra disposición. Por discutir conmigo cosas que para vosotros ya hacía mucho que estaban claras. Gracias Eduardo por mis primeras conversaciones sobre investigación, por compartir conmigo la emoción de los primeros resultados que empiezan a salir, por tu conanza. Gracias Justo por mostrarme el mundo y al mundo de la investigación a través de tantos investigadores y en tantos lugares; para mí esta es una de las partes más bonitas de este trabajo; y gracias por abrirme esta puerta de la investigación a mí, y a tantos jóvenes. Esta decisión me ha dado la oportunidad de vivir en sitios tan diferentes como Sevilla, Toronto o Bruselas, aprender de sus investigadores, disfrutar de su cultura y compartir con su gente. Gracias al proyecto y al departamento por acogerme con cariño. Al equipo de administración del IMUS por trabajar tan bien y con una sonrisa siempre. Thank you Igor and Oded for your generosity. Martine, merci pour ton hospitalité et ta disponibilité. Estos cuatro años han sido también disfrutar. Por suerte, muchos otros decidieron, como yo, hacer su doctorado en Sevilla. Gracias por el día a día, por tantas risas, tantas comidas, tantas cenas, tantas estas, tanto hablar, tanto escuchar, tantos consejos, tanta paciencia, tanto apoyo. Estos cuatro años habéis sido mi otra familia, la familia del IMUS y la L2. VI
VII La parte menos bonita de cruzar esta puerta ha sido el tiempo que he dejado de dedicarles a los míos. A mi familia (la de casa, la Leal y la Palazón), a mis amigas de toda la vida, a mi Cris, a Esther, a Monta y a algunos más. Gracias por entenderlo. Por alegraros por la oportunidad que suponía para mí. Por, desde lejos, estar. Por hacerme partícipes, como podíais, de todo lo que os iba pasando. Gracias. Gracias a mi abuela Rosa y a mi tía Mari por ser dos mujeres que me inspiran. Jose, esta tesis también es tu decisión. Gracias. Gracias porque tu esfuerzo por esta tesis ha sido incluso mayor que el mío. La vida contigo es innitamente (no numerable) mejor. Y gracias también a los tuyos por entenderlo. Gracias a mis padres y mi hermana por creer en mí más que yo misma. Por estar siempre, para las grandes cosas y para las más pequeñas. Por vuestro apoyo. Gracias Lucía por decirme las cosas como son, por ayudarme mucho más de lo que crees. Gracias Cande y Tono por darme todo y más. Estar los cuatro siempre me hace feliz.
Contents XV 3.3.2 Polyhedral uncertainty set . . . . . . . . . . . . . . . . . . . . 83 3.3.3 Initializing by 2-approximations . . . . . . . . . . . . . . . . . 90 3.4 Computational Experiment . . . . . . . . . . . . . . . . . . . . . . . 92 3.4.1 Hypercube uncertainty set. . . . . . . . . . . . . . . . . . . . 93 3.4.2 Polyhedral uncertainty set. . . . . . . . . . . . . . . . . . . . 98 3.5 Conclusions................................ 99 4 Minmax regret combinatorial optimization problems with investments 102 4.1 Introduction................................ 104 4.2 Modeldescription............................. 106 4.3 Modelformulation ............................ 109 4.3.1 Linear cost bound functions . . . . . . . . . . . . . . . . . . . 111 4.3.2 Piecewise linear cost bound functions . . . . . . . . . . . . . . 112 4.4 Approximations.............................. 116 4.4.1 2-approximation result . . . . . . . . . . . . . . . . . . . . . . 116 4.4.2 Heuristic.............................. 119 4.5 Computational experiment . . . . . . . . . . . . . . . . . . . . . . . . 126 4.6 Conclusions................................ 130 5 Bilevel Portfolio Selection Problem with Pricing decisions on transaction costs 132 5.1 Introduction................................ 134 5.2 Preliminaries ............................... 136 5.3 Models description, formulation and resolution algorithms . . . . . . 139 5.3.1 Bank-Leader Investor-Follower Problem (BLIFP) . . . . . . . 139 5.3.2 Investor-Leader Bank-Follower Problem (ILBFP) . . . . . . . 148 5.3.3 The Maximum Social Welfare Problem (MSWP) . . . . . . . 153 5.4 Computational Experiment . . . . . . . . . . . . . . . . . . . . . . . 157 5.4.1 Comparing solution methods . . . . . . . . . . . . . . . . . . 158 5.4.2 Comparing solutions and risk proles within models . . . . . 161 5.4.3 Comparing solutions across models . . . . . . . . . . . . . . . 165 5.5 Conclusions................................ 168 6 New bilevel models for the location of controversial facilities 170 6.1 Introduction................................ 172 6.2 Modeldescription............................. 174 6.3 Model formulations and resolution algorithms . . . . . . . . . . . . . 176 6.3.1 First approach: Evaluating norms by its primal expression . . 176 6.3.2 Second approach: Evaluating the norm by its dual expression 184
XVI Contents 6.4 Computational Experiment . . . . . . . . . . . . . . . . . . . . . . . 188 6.5 Extensions ................................ 194 6.5.1 The model with K secondary facilities (independent followers) 194 6.5.2 The problem under the `τ -norm ................ 195 6.6 Conclusions................................ 198 7 Conclusions and future research lines 200 References 206
Chapter 1 Introduction 2
4 Chapter 1. Introduction Life is a matter of choices. Every day we face decision-making. Most of the decisions that we make routinely are insignicant but some others can be more relevant. When facing a decision, specially in these more signicant ones, we undertake a careful analysis before deciding, with the aim of making the choice properly, optimally if it is possible. In this decision-making context, Operations Research (OR) brings us the theory and the tools to make better decisions. Among all theories in OR, Optimization is one of the most widely used ones. It drives us to optimal choices in challenging decision-making problems. Optimization is applied in many areas such as location, network design, shortest path, nance, game theory or pricing problems. Optimization problems have been largely studied in the specialized literature; however, in the last decades, there has been a paradigm shift towards the treatment of more realistic problems, in which uncertainty sources in the data and multiple criteria or levels of optimization are included. This trend continues growing due to the economic importance of the existing applications in areas such as location, transportation, or planning. In this thesis, we study optimization models in which uncertainty aects the data, and optimization problems in which there exist several decisions makers, and thus multiple objectives, and a hierarchical decision order. We handle the uncertainty via the minmax regret criterion from Robust Optimization, and the hierarchical decision structure using Bilevel Optimization. In all our considered models, solving the optimization problem entails solving some other nested optimization problems. 1.1 Minmax regret and bilevel approaches for decisionmaking: relationship and theory When trying to nd an optimal decision, it is often possible to formulate the decision problem as one of maximization or minimization of one or several objective functions under a very wide collection of hypotheses. However, with the growth of theory and techniques and with the expansion of applications in Operations Research the variety in the structure of the problems in the eld is immense. For instance, the objective function can be linear or nonlinear, nonlinear with dierentiability or nonlinear without dierentiability, the nature of the variables can be continuous or discrete, the objective of the problem and also the number of involved decision-makers can be single or multiple, some of the parameters of the problem can be uncertain or not, etcetera. Among this large collection of congurations, we can nd a considerable group of optimization problems, from very dierent nature, in which solving the optimization problem entails solving a nested optimization problem. That is, there exists a particular conguration in Optimization where one (or several) problem(s) is embedded
1.1. Minmax regret and bilevel approaches: relationship and theory 5 within another one. These problems can be understood as two (or more) stage problems: a rst decision is made, in a rst stage, taking into account that in a second (or latter) stage(s) other decision(s) will be made by other (s) decision-maker(s). Or equivalently, as problems in which the decision-maker integrates with her decision the decision process of another optimization problem. Examples of this type of problems can be found in areas such as Stochastic Optimization (Heyman and Sobel (2004); Shapiro et al. (2009); Tijms and Tijms (1994)), Robust Optimization (Ben-Tal et al. (2009); Kasperski (2008); Kouvelis and Yu (1997)) or Bilevel Optimization (Bard (2013); Dempe (2002a); Dempe et al. (2015)). We will focus on the last two. Robust Optimization is focused on decision-making problems under uncertainty when no probabilistic information about the uncertain data is assumed. It is an eective way to structure this type of uncertainty and to make a decision in the presence of it. In Robust Optimization, the decision-maker constructs a solution that is feasible or close to the optimal for any realization of the uncertain parameters in a given set. In order to choose among the feasible solutions, there exist in the literature dierent criteria in order to assess the impact of the uncertainty on a given solution. Some of these criteria are based in the denition of what is called the worst-case performance of the assessed solution, such as the minmax, the minmax regret or the relative regret criteria. In these problems, the decision-maker chooses a solution anticipating the worst-case performance of the system for this solution. Sometimes, the worst-case performance of a solution can be related to actions of a real or gurative decision-maker who plays against our solution. That is, the decision-maker chooses an action taking into account that another real or gurative decision-maker, for instance, nature, will decide afterwards the actual performance of the system (the realized value of the uncertain parameters) in such a way that this is the worst possible realization of the uncertain parameters, for the chosen solution, under the selected criterion. The decision-maker acts in a rst stage and the decision about the performance of the system is taken in a second stage. These problems are commonly formulated embedding the worst-case system performance decision problem within the decision-maker objective function. On the other hand, Bilevel Optimization, as described in Bard (2013), addresses problems in which two decision-makers, each one with their own interests, act and react in a noncooperative, sequential manner. This hierarchical decision structure is written in terms of a mathematical program in which the second decision-maker's problem is part of the constraints of the rst decision-maker's problem. Speci- cally, this second decision problem embedded within the constraints of the rst one translates the fact that, some of the variables of the rst problem are an optimal solution of the second decision problem. The rst decision-maker anticipates the second decision-maker's choice. In these problems, there are clearly two decision-
6 Chapter 1. Introduction makers, one acting in a rst stage and another one in a second stage, and a nested optimization problem (within the constraints of the main problem). In the following subsections, we provide a more detailed interpretation of the Robust and Bilevel Optimization, including a more in-depth discussion of formal denitions, applications, and results in the literature regarding these two approaches. In the robust case, we focus on a particular criterion, the minmax regret criterion, and in the bilevel case, we introduce also the widely used application to price setting problems. 1.1.1 Robust Optimization: the minmax regret criterion Real-life is full of uncertainties. Hence, when attempting to build a realistic decision problem, the input data like costs, times, lengths, prices, etcetera, can be very commonly not exactly known in advance. This can be easily appreciated when thinking in concrete decision examples. For instance, when designing a new network, some costs such as those derived from the construction of new infrastructure can be uncertain; or when deciding the best schedule plans in which the cost of processing a task depends on its starting time, the execution times can be imprecise a priori; or in addition, when trying to determine a shortest path, the cost of traversing an arc of such path can be undetermined beforehand, or also the demands in supply chain problems can be unknown; and much more. Researchers became aware of the importance of accepting these uncertainties and managing them when modeling a problem long ago, as a consequence, literature is full of decision problems handling with uncertainty (see e.g. Abeledo et al. (2013); Averbakh and Berman (2003); Karasan et al. (2001); Conde (2004, 2007); Fortz et al. (2013); Marín et al. (2018); Merton (1969); Nickel et al. (2012); Olivares-Nadal and DeMiguel (2018); Pan and Nagi (2010); Puerto et al. (2009, 2011); Takahashi et al. (2001), etc.). The uncertainty can be caused by a lack of information about the data or by the varying nature of the data itself. For instance, in the design of a network that has never been built in the past, the diculty to estimate parameters (costs, times,...) can lie in the lack of historical data for similar projects, or even existing this data, the construction of new infrastructures can render the data obsolete; or for example, in a shortest path problem the travel times can vary depending on external factors as trac. However, sometimes, the set dening the range of possible values for the uncertain parameters can be modeled in dierent forms depending on the available information. In fact, carrying out a proper study of the system, it may be possible to determine a more precise uncertainty set. For instance, in a supply chain problem in which the demand is uncertain, and a wide range of possible values is considered due to the expensiveness of obtaining tighter information, an investment to perform a prospective analysis of the demand may be sometimes carried out to obtain more
1.1. Minmax regret and bilevel approaches: relationship and theory 7 accurate values. Whatever the nature and the structure of the uncertainty, the best way to handle it and to make decisions under its presence is to accept and assimilate this uncertainty and make an eort to incorporate it in the decision-making model (Kouvelis and Yu (1997)). Stochastic Programming and Robust Optimization are two of the most well-known and commonly used frameworks to manage uncertainty. Stochastic Optimization is a natural and useful approach to address uncertainty when it is known the probability distribution of the input data. Under this knowledge, a typical approach is to select a decision that maximizes o minimizes an expected performance measure, under the assumed probability distribution. However, determining these probability distributions can be truly a dicult task, mainly when there exist multiple interdependent uncertain factors. Furthermore, an accepted drawback of Stochastic Programming is, as noticed by Kouvelis and Yu (1997) or Kasperski (2008), that the generated solutions can become meaningless when the process is not repeated several times since it is being optimized an expected performance of the system. Hence, the obtained solution may not be appropriate in problems where the solution is implemented just once; specially in those cases in which the decision-maker has to deal with the consequences on the system performance of the decision made under the realization of the parameters, as for instance when designing a network that will remain the same for a long period. Therefore, paying attention to the behaviour of the solution under any possible realization of the uncertain data can become essential. In contrast, Robust Optimization can be a good approach for uncertainty environments where: • There exists imprecise information about the probabilities of the possible realization of the parameters. • The decision-maker is concerned about the eect of the solution with the realized data, and even existing some probabilities for the possible values, she desires to be prepared for any situation that may occur, not only for the most probable one but also for the least probable realization of the data. In these cases, the probabilistic information can be useful to select a subset of realizations suciently representative. • The processes to implement are from a non-repetitive nature, that is, they are not going to be implemented periodically. • The solutions are evaluated ex-post, that is, as if the actual realization of the parameters had been known before deciding.
8 Chapter 1. Introduction The robust approach is based on the concept of scenario, that is, uncertainty is structured via a scenario-based description of the problem data. The notion of scenario refers to a concrete realization of the possible values of the unknown parameters. Then, as claimed before, the aim of a robust solution is to hedge against parameter variations, that is, to perform well under any of these plausible scenarios. In order to structure the uncertainty via scenarios two main representations have been considered in the literature: the discrete and the interval scenario cases. On the one hand, in the discrete approach, an explicit list of possible congurations of the parameters is given. This representation of the uncertainty allows considering correlations between the parameters; however, the number of possible scenarios must be nite or countable. On the other hand, in the interval case, it is assumed that each parameter can take on any value in a given interval, independently of the values taken by the other parameters. This interpretation of the uncertainty is a natural approach since in a lot of problems it is possible to determine a range of possible values for an uncertain parameter. Furthermore, this approach is not very data demanding. Nevertheless, the independence assumption among the uncertain data is sometimes not realistic or practicable. Thus, there exists a new tendency, still subtle, of allowing dependencies among the parameters in a continuous set of scenarios. This can be done by modeling uncertainty via more general sets of uncertainty. We will consider this uncertainty structure in some of the models we present. Some of the most well-known robust approaches are the absolute robust , the robust deviation and the relative deviation robust criteria. The absolute robust criterion, generally known as minmax criterion, seeks a solution that minimizes the worst possible value among all the scenarios. A highly conservative approach quite useful in decision environments in which anticipating the reaction if the worst case happens is decisive. Less conservative and more compromised solutions are largely generated by the minmax regret criterion, also denoted as robust deviation. The regret of a solution under a scenario measures the cost or the risk of choosing such a solution under such scenario. It compares the performance of a solution with the optimal performance under a given scenario, that is, it compares each solution with the best decision that would have been taken if the scenario had been known in advance. Among all the regrets, one per scenario, the criterion takes the maximum one and tries to minimize it. Then, the minmax regret criterion minimizes the maximum deviation in the cost of a solution from the optimal one in each scenario. Finally, the relative robustness criterion compares, again, a solution with the optimal solution under a scenario, but measuring not the absolute deviation but the relative deviation respect to the optimal value under the scenario. In Chapters 2, 3 and 4 we will adopt the minmax regret criterion to deal with the uncertainty. Since most of the minmax regret theory is developed for 0-1 determin-
1.1. Minmax regret and bilevel approaches: relationship and theory 15 between the price-xer and the consumers, can be modeled via Bilevel Optimization since there exists a hierarchical decision structure, and the values of the decision variables of one level inuence the optimal solution of the other level (Labbé and Violin (2013)). Think for instance in the problem of a bank that must decide the transaction costs for clients investments; the bank can x them trying to maximize its reward, but must take into account that these rates will condition clients' investments and by extension the bank benet. Several examples of price setting problems modeled via Bilevel Optimization can be found for instance in the elds of toll optimization of highways, pricing of express mail delivery or passengers transportation systems, pricing telecommunications packages, etcetera (see for example Labbé and Violin (2013) and the references therein). Formal denition Let x∈Rn1 and y∈Rn2 denote the decision vectors, F:Rn1×Rn2→R and f:Rn1×Rn2 the objective functions and G:Rn1×Rn2→Rm1 and g:Rn1×Rn2→ Rm2 the vector-valued functions of the constraints of the leader and the follower problems, respectively. Let X represent the set of constraints concerning only the x variables. The general Bilevel Programming problem (BP) can be dened as: min x∈X,y F(x, y) (1.1) s.t. G(x, y)≤0, (1.2) y∈arg min yf(x, y), (1.3) s.t. g(x, y)≤0. (1.4) (1.1) and (1.2) constitute the upper level problem, while (1.3) and (1.4) dene the lower level problem. It can be observed that the lower level or follower problem is included in BP as a part of the constraints. That is, in BP constraints (1.3) and (1.4) translate the fact that some of the variables of the problem, the y variables, are an optimal solution of a second and nested optimization problem. The lower level problem must be solvable for global minima. In practice it is assumed to be convex (Colson et al. (2005)). The bilevel and multilevel terms were rstly introduced by Candler and Norton (1977), however, as pointed out by Colson et al. (2005), bilevel problems were introduced before under the designation of mathematical programs with optimization problems in the constraints in a series of papers by Bracken and McGill (1973, 1974, 1978), developed in the context of military and production and marketing decisionmaking. In game theory, the Bilevel Programming problems were introduced by the
16 Chapter 1. Introduction name of Stackelberg games. The above BP formulation can be particularly adapted for price setting problems. Let us assume that there are t1 taxed and t2 untaxed activities, T∈Rt1 is the tax vector, x∈Rt1 and y∈Rt2 are the decision vectors associated with taxed and untaxed activities, respectively, and F and f are the objective functions of the leader and the follower objective values. And let g(x, y) be the vector-valued function of the constraints. The price setting bilevel problem ( P-BP ) can be formulated as the following bilevel problem: max TF(T, x, y) (x, y)∈arg min x,y f(T, x, y), s.t. g(x, y)≤0. In ( P-BP ) a function of the revenue of the price-xer is maximized assuming that, the taxed and untaxed activities are chosen by the user afterwards trying to minimize a function of the cost according to some constraints. We dene now dierent concepts related to Bilevel Programming. The relaxed problem associated to BP consists of removing the restriction that the y variables must be an optimal solution of the follower level problem, that is, removing constraint (1.3). Then, the relaxed feasible region or constrained region is dened as Ω = {(x, y)∈Rn1×Rn2:x∈X, G(x, y)≤0 and g(x, y)≤0}. For a given vector ¯x∈X , the lower level feasible set is Ω(¯x) = {y∈Rn2:g(¯x, y)≤0}, meanwhile the lower level reaction set is LR(¯x) = {y∈Rn2:y∈arg min{f(¯x, ˆy) : ˆy∈Ω(¯x)}} . Every y∈LR(¯x) is a rational response . Finally, the induced region , which include all the feasible points of the BP and corresponds to the feasible set of the leader, is dened as IR ={(x, y)∈Rn1×Rn2:x∈X, G(x, y)≤0 and y∈LR(x)}. This is usually nonconvex and it can be disconnected or even empty.
1.1. Minmax regret and bilevel approaches: relationship and theory 17 In a BP problem, for a given value of x variables, the follower problem may have multiple optimal solutions. Therefore, if it happens, dierent choosing attitudes can be adopted by the follower. The follower's behavior will give rise to dierent modelling approaches. A cooperative attitude leads to an optimistic solution so that when there exist multiple follower solutions, the leader assumes that the follower will choose the most favourable one for the leader. Formally, when LR(x) is not a singleton, a point (x∗, y∗)∈Rn1×Rn2 is called a local optimistic solution for problem BP if x∗∈X, G(x∗, y∗)≤0, y∗∈LR(x∗), F(x∗, y∗)≤F(x∗, y),∀y∈LR(x∗), and there exists an open neighborhood of x∗ , with radius δ > 0 , B(x∗, δ) , such that φ0(x∗)≤φ0(x),∀x∈B(x∗, δ)∩X, where φ0(x) = miny{F(x, y) : y∈LR(x)} . It is called a global optimistic solution if δ=∞ can be chosen. In contrast, an aggressive attitude leads to a pessimistic solution in which the leader assumes that the follower will choose, among the optimal solutions for the follower, the worst possible one for the leader. A point (x∗, y∗)∈Rn1×Rn2 is called a local pessimistic solution for problem BP if x∗∈X, G(x∗, y∗)≤0, y∗∈LR(x∗), F(x∗, y∗)≥F(x∗, y),∀y∈LR(x∗), and there exists an open neighborhood of x∗ , with radius δ > 0 , B(x∗, δ) , such that φp(x∗)≤φp(x),∀x∈B(x∗, δ)∩X, where φp(x) = maxy{F(x, y) : y∈LR(x)} . It is called a global pessimistic solution if δ=∞ can be chosen. For further details we refer the reader to Dempe (2002b); Loridan and Morgan (1996)
18 Chapter 1. Introduction In the bilevel problems that we present, Chapters 5 and 6, we will only assume cooperative behaviour. As referred before, the Bilevel Programming concept can also be extended to Multilevel by considering more than two levels, that is, more than two decisionmakers playing hierarchically and hence, more than one nested problem. Another realistic and useful expansion is to consider that there exist several decision-makers in the same follower level. All these followers observe the leader's decision and react, all at the same time, according to their own interests. The decision of a follower can depend, or not, on the other followers decisions. This extension will be considered in Chapters 5 and 6. General results We gather in this subsection some basic properties and results for linear and binary bilevel problems. These results and the proofs or references can be found in Bard (2013), which can be also used for further details and references. Linear Bilevel Programming includes all bilevel problems in which all the functions, constraints and variables are linear. The following results hold for this type of problems. Theorem 1. The induced region IR of a linear bilevel problem can be written equivalently as a piecewise linear equality constraint comprised of supporting hyperplanes of Ω . From this theorem, the next two results follow. Corollary 1. The linear BP is equivalent to minimizing F over a feasible region comprised of a piecewise linear equality constraint. Corollary 2. A solution to the linear BP occurs at a vertex of IR . The following results show that a solution vertex of IR is also a vertex of Ω . Theorem 2. The solution (x∗, y∗) of the linear BP occurs at a vertex of Ω . Corollary 3. If x is an extreme point of IR , then it is an extreme point of Ω . We consider now the zero-one linear BP, where all or some variables are restricted to binary variables. Let us denote by (01-BP) the case in which all variables are binary and by (01U- BP) and (01L-BP) the cases in which the upper level and lower level variables, respectively, are binary. The following results address the existence of optimal solutions
1.1. Minmax regret and bilevel approaches: relationship and theory 19 Theorem 3. For the linear BP, let Ω be a bounded set, i.e., a polytope. If Ωu:= {(x, y) : G(x, y)≤0)}=Rn1+n2 , then linear BP, (01-BP) and (01U-BP) have an optimal solution if Ω6=∅ . If Ωu6=Rn1+n2 , then linear BP, (01-BP) and (01U-BP) have an optimal solution if there exists an ¯x∈X such that (¯x, ¯y)∈Ωu . This theorem provided sucient conditions for the existence of optimal solutions when Ω is bounded. These conditions are equivalent to the conditions under which the induced region is nonempty. The latter result, provide conditions to guarantee that an existing optimal solution of (01L-BP) is a boundary point of the set Ω . Theorem 4. Let Ωu:= {(x, y) : G(x, y)≤0)}=Rn1+n2 , and Ω6=∅ and suppose that there exists an optimal solution (x∗, y∗) to (01L-BP). Then (x∗, y∗) is a boundary point of Ω . Complexity results Bilevel problems are, from a computational point of view, very dicult to solve. The linear BP was rst shown to be NP-hard by Jeroslow (1985). Hansen et al. (1992) strengthened this result by proving that the linear minmax bilevel problem is strongly NP-hard. An immediate consequence of it was the strongly NP-hardness of the linear BP problem. Later, Vicente et al. (1994) proved that even the problems of checking strict local optimality and local optimality in linear BP are NP-hard. Existing methods Due to the diculty of the bilevel problems it is not surprising that most of the techniques and algorithms on the topic have been focused on the easiest bilevel programs, those with nice properties such as linear, quadratic or convex objective function and/or constraints functions. Even so, over the years, more complex bilevel problems, for instance, with discrete variables or nonlinear programming problems in both levels have also been subject of research (Colson et al. (2005)). We briey gather in this section some of the more successful schemes to deal with bilevel problems. For further details and references on the highlighted methods and other ones we refer the reader to Bard (2013); Colson et al. (2005) and the references therein. For the case of linear BP, making use of Theorem 2, whereby there exist an optimal solution of the problem in the vertex of Ω , a wide class of methods for solving this linear BP have been developed based on vertex enumeration in the context of the simplex method. For instance, the K th-Best Algorithm , proposed by Bialas and Karwan (1982), systematically explores the vertex beginning with
20 Chapter 1. Introduction the basis associated with the optimal solution to the linear program obtained by removing constraint (1.3). The methods stops with a global optima. Other method, possibly the most popular one, applicable when the lower level problem is convex and regular, is the Khun-Tucker approach . We will apply it in Chapters 4 and 5. The rst step is to replace the lower level problem by its Karush- Kuhn-Tucker (KKT) conditions, giving rise to a single level reformulation of the BP. This method is also known as Branch-and-bound , since the basic idea is to apply a branch and bound strategy to deal with the complementary constraint. Alternative approaches proposed in the literature for linear BP are methods based on penalty functions, complementary pivoting or reverse convex programming, or also trying to nd an explicit expression for the optimal solutions of the lower-level problem. Methods for Mixed Integer Bilevel Linear Problems (MIBLP) have also been studied, in fact, it is an appearing current subject of research. The most common approaches to solve this type of problems, under some conditions, are Branch and Bound (see e.g. Moore and Bard (1990)) and Branch and Cut algorithms (see e.g. DeNegre and Ralphs (2009); Fischetti et al. (2018)). Very recently, Fischetti et al. (2017) proposed a new general-purpose branch and cut exact algorithm for MIBLP, with continuous and discrete variables in both levels, based on several new classes of valid inequalities. With this new algorithm, they were able to solve to optimality more than 300 previously unsolved instances from the literature. In addition, decomposition techniques, such as Benders Decomposition, can also be used for MIBLP under some particular conditions. For instance, we will apply an algorithm based on a Benders decomposition to a MIBLP in Chapter 6. Due to the inherent complexity of the Bilevel Optimization, several heuristics have also been developed in the literature to handle BP (see e.g. Bard (2013) and the references therein). The minmax regret problem as a bilevel model As said before, in the minmax regret models, a solution is chosen taking into account the most unfavorable possible reaction of the system. That is, the system chooses , for each feasible solution, the worst possible realization of the uncertain parameters. This can be understood, from the Bilevel Optimization point of view, as the reaction of the system is determined by a follower, who acts in this case against the leader. Hence, the minmax regret model R∗= min x∈Xmax s∈SR(x, s) = min x∈Xmax s∈S y∈X Z(x, s)−Z(y, s),
1.2. Contributions of this thesis 21 can be rewritten as the following bilevel programming problem R∗= min R(x, y, s) s.t. x∈X, (y, s)∈arg max R(x, y, s), s.t. s∈S, y∈X, where R(x, y, s) = Z(x, s)−Z(y, s) . 1.2 Contributions of this thesis The goal of this thesis is to derive optimization models, in the context of decisionmaking, in which uncertainty is incorporated in the parameters dening the problem; and also to build models in which there exist two (or more) decision-makers, with two (or more) objective functions, and a hierarchical decision structure. To give a compromise solution in those problems with uncertain parameters the minmax regret paradigm is considered, whereas the hierarchy in the decision process is managed via Bilevel Optimization. Hence, two main blocks can be distinguished in the thesis, one devoted to the contributions to minmax regret models, addressed in Chapters 2, 3 and 4, and another one with the contributions to bilevel models, addressed in Chapters 5 and 6. In the problems studied in the rst chapters, each feasible decision is evaluated with respect to the most unfavorable possible reaction in the system. In Chapters 5 and 6 we continue using this idea but assuming in this case that, the reaction to the initial feasible decision is carried out by an adversary of a follower. All the models we propose, the minmax regret and the bilevel ones, belong to a class of optimization problems in which solving the optimization problem entails solving some other nested optimization problems. In all these models, formulations, algorithms, and properties of the problems are stated from a Mathematical Programming perspective. The validity of all models is justied from the practical applications point of view and we also analyze computationally the viability of the proposed formulations and optimization algorithms. In Chapter 2, based on the paper by E.Conde and M.Leal (Conde and Leal, 2019), we address the problem of designing a robust supply network, assuming uncertain some of the parameters dening the problem. We examine the cases in which the uncertainty aects the construction and/or operating costs, and/or the existing set of supplier-client pairs, and/or the demand to serve. Our contributions are modeling
22 Chapter 1. Introduction the uncertainty using the minmax regret criterion, and assuming the uncertainty set of parameters is given as a polyhedron, allowing in this way dependence relationships between the uncertain parameters. Benders decomposition techniques are used to solve the models and the proposed algorithms are tested in a computational experiment. In Chapter 3, based on the paper by E.Conde, M.Leal and J.Puerto (Conde et al., 2018), we study the minmax regret version of a time-dependent shortest path problem. In particular, we assume that the cost structure takes into account the position that each arc occupies in the path. Furthermore, we assume uncertainty in the costs dening the time-dependency. Our rst contribution in this chapter is combining the time-dependency and the uncertainty of the costs in the context of the minmax regret criterion. As a consequence of the combination, relationships between the uncertain parameters emerge, and the common independence assumption among the set of costs does not hold. In order to deal with the model, we provide a MILP formulation for the uncertainty interval case, extending the classical duality and worst-case scenario developments to obtain MILP formulations for minmax regret problems, which represents another contribution of this chapter. Then, we extend the model to a new and more general case in which polyhedral sets of uncertainty are considered. This approach can also be extended to the minmax regret timedependent Traveling Salesman Problem. We propose three dierent algorithms based on Benders decomposition to solve the problem. We reinforce the algorithms with constant factor approximations. The formulation and algorithms are tested in a computational experiment. In Chapter 4, based on the paper by E.Conde and M.Leal (Conde and Leal, 2017), we propose a new minmax regret optimization model in which the decisionmaker has some control over the uncertain parameters of the system. Until now in the literature, most of the minmax regret models have ignored the possibility of changes in the uncertainty, or in the degree of knowledge about the attainable values of the parameters due to actions carried out in the system. Hence, in our model, as a contribution, we incorporate this possibility by assuming that in some cases, spending some resources we may be able to change the cost structure of the system and take advantage of it to nd a robust solution. Some properties of the model allow us to construct Mathematical Programming formulations that can be solved by o- the-shelf solvers. We illustrate the model in the shortest path problem in a network in which investments in the system produce variations in the uncertainty intervals for the arc costs. We extend some existing results on constant factor approximation for minmax regret problems without investments, give an approximate algorithm and conduct a computational study. In Chapter 5, based on the paper by M.Leal, D.Ponce and J.Puerto (Leal et al.,
1.2. Contributions of this thesis 23 2018), we propose various price setting models in the context of Portfolio Optimization. We present dierent bilevel portfolio selection models in which the transaction costs, generally assumed given in the portfolio problems, become decision variables, and hence, the nancial intermediary becomes a decision-maker in the problem. This nancial intermediary decides on the unit transaction costs for investing in some securities, maximizing its benets, and the investors choose the portfolio, minimizing risk and ensuring a desired expected return. Therefore, our contributions are turning transaction costs into decision variables, and incorporating two levels of decision-makers in the portfolio problem. We present dierent bilevel programming versions, depending on who makes the decision rst, the investor or the nancial institution, and also analyze the social welfare version. We study the dierent models, analyze some properties, develop MILP formulations and algorithms and report some computational experiments performed on real data taken from the IBEX 35. In Chapter 6, based on the paper by M.Labbé, M.Leal and J.Puerto (Labbé et al., 2018), we address a new bilevel location model motivated by real-life problems in which the location decision generates disagreements among users with opposite interests. We consider two dierent levels of decision-makers. The rst one chooses among a number of xed potential locations some primary facilities to set up; next, the second one chooses the location of a secondary facility in a continuous framework. The leader and the follower have opposite targets; the leader's and follower's goal is to maximize and minimize, respectively, some proxy of the overall weighted distance between the primary and secondary facilities. We develop the bilevel model for one follower and any polyhedral distance, proposing a proof of the NP-hardness of the problem, dierent MILP formulations and algorithms; and later we extend it for several followers and any `p -norm, p∈Q , p≥1 . We also report some computational results. Finally, in Chapter 7, conclusions and some possible future research lines for the dierent proposed models are briey discussed.
Chapter 2 A minmax regret model for the design of supply networks under uncertainty 24
2.2. Model description and deterministic case formulation 31 Remark 2. Formulation (DND) can be stated in a more general format. For instance, we can restrict the set of possible designs by including limited resources aecting the choice of the subset of arcs (the y -variables). On the other hand, with respect to the x -variables, one can consider more general coecients bip =bp, bjp =−bp for p= (i, j)∈P and bkp = 0 otherwise, being bp∈Z+ . In this case, bp can model the amount of the commodity transported from i to j or a weight of the relative importance of the pair p∈P in comparison with the other pairs. However, for the sake of simplicity, while this element does not play a relevant aspect for the optimization model we will maintain all the bp weights equal to one. Remark 3. The binary constraints on the variables xijp can be relaxed to nonnegativity, xijp ≥0 for all (i, j)∈A, p ∈P in the formulation (DND), due to the separability of its objective function respect to the x -variables and y -variables. Note that the unimodular property can be applied to the inner problem on the x -variables. We will end this section setting out a simple example of the (DND) problem which will be used to illustrate later formulations, results and behaviors of the solutions. Example Grid Design Consider the square grid network illustrated in Figure 2.1: a regular support of points (reticle), with 100 nodes, in which from each node arises (if possible) three potential directed arcs, one downward to the node below, one forward to the node on the right, and one diagonally to the node on the right and above. This type of mesh or topology, originally proposed in Cherkassky et al. (1996) and used in Fernández et al. (2014) among others, located on a geography, can model for example pipelines networks or simple circuits. The circles in the gure represent the nodes, the gray circles represent the origins (suppliers), and the numbers inside them tag each origin; the squares represent destinations (demand points), and the numbers inside the squares, the origin from which each demand point should be supplied. The dashed gray arrows represent potential arcs. All the xed and unitary transportation arc costs were assumed to be 1 and 0.3 respectively. The problem consists of choosing the network design that connects all the origin-destination nodes at minimum cost. The arrows highlighted in black color in Figure 2.1 represent an optimal network design after solving the formulation (DND). Note that, since no bounds on the arc capacities are considered, the solution has a very simple design in which several paths overlap. In fact, the optimal network designs under these conditions are frequently spanning trees, arborescences or spanning forests with a few spanning trees.
32 Chapter 2. A minmax regret model for the design of supply networks under uncertainties 2.3 Robust models and Benders resolution algorithms 2.3.1 Uncertain costs In this section a minmax regret version of the (DND) problem is considered under a polyhedral set of cost scenarios. Let S denote the set of possible scenarios which is identied with a polyhedron of costs (cs, fs), s ∈S whose components are cs ij, fs ij for all (i, j)∈A . The regret R(x, y, s) of a given solution (x, y) under the scenario s∈S is dened for this problem as the following positive dierence R(x, y, s) := X (i,j)∈A fs ijyij +X (i,j)∈A,p∈P cs ijxijp −Z∗(s), where Z∗(s) is the optimal value of the (DND) problem under the scenario s∈S . For a given design solution (x, y) it makes sense to compute R(x, y) , the maximum regret over the set of possible scenarios S . This value represents the opportunity loss cost for the solution (x, y) and can be obtained by solving the following optimization problem R(x, y) := max X (i,j)∈A fs ijyij +X (i,j)∈A,p∈P cs ijxijp− −X (i,j)∈A fs ijyij −X (i,j)∈A,p∈P cs ijxijp subject to: X (i,j)∈A xijp −X (k,i)∈A xkip =bip, i ∈N, p ∈P, xijp ≤yij,(i, j)∈A, p ∈P, yij ∈ {0,1},(i, j)∈A, xijp ∈ {0,1},(i, j)∈A, p ∈P, s∈S. (2.1) In order to obtain a complete formulation of the problem (2.1) we will assume that a polyhedral description of the set of xed and unitary transportation arc costs is known, S:= (c, f)≥0 : X (i,j)∈A (af ijkfij +ac ijkcij)≤dk, k ∈K , where we have used the same letter S that already identied the set of scenarios to make the notation simpler. Additionally, it will be assumed the compactness of this polyhedron of costs, thus there are constants c and f such as 0≤cij ≤c and 0≤fij ≤f for all (i, j)∈A . Using this polyhedral representation of the set S of possible cost scenarios, a
2.3. Robust models and Benders resolution algorithms 33 formulation of the optimization problem (2.1) can be given by R(x, y) := max X (i,j)∈A fijyij +X (i,j)∈A,p∈P cijxijp− −X (i,j)∈A fijyij −X (i,j)∈A,p∈P cijxijp subject to: X (i,j)∈A xijp −X (k,i)∈A xkip =bip, i ∈N, p ∈P, xijp ≤yij,(i, j)∈A, p ∈P, X (i,j)∈A (af ijkfij +ac ijkcij)≤dk, k ∈K, yij ∈ {0,1},(i, j)∈A, xijp ∈ {0,1},(i, j)∈A, p ∈P, fij ≥0,(i, j)∈A, cij ≥0,(i, j)∈A. (2.2) The above formulation contains quadratic terms in the objective function which added to the binary nature of some of the variables increase the diculty to solve the problem. Nonetheless, as stated in the following result, this nonlinear mixed integer problem is equivalent to the following MILP formulation R(x, y) := max X (i,j)∈A fijyij +X (i,j)∈A,p∈P cijxijp− −X (i,j)∈A wij −X (i,j)∈A,p∈P zijp subject to: X (i,j)∈A xijp −X (k,i)∈A xkip =bip, i ∈N, p ∈P, xijp ≤yij,(i, j)∈A, p ∈P, X (i,j)∈A (af ijkfij +ac ijkcij)≤dk, k ∈K, cij −c(1 −xijp)≤zijp,(i, j)∈A, p ∈P, 0≤zijp,(i, j)∈A, p ∈P, fij −f(1 −yij)≤wij,(i, j)∈A, 0≤wij,(i, j)∈A, yij ∈ {0,1},(i, j)∈A, xijp ∈ {0,1},(i, j)∈A, p ∈P, fij ≥0,(i, j)∈A, cij ≥0,(i, j)∈A. (PP-RND)
34 Chapter 2. A minmax regret model for the design of supply networks under uncertainties Proposition 5. The optimization problem (2.1) is equivalent to the MILP formulation (PP-RND). Proof. The blocks of constraints of the (PP-RND) formulation cij −c(1 −xijp)≤zijp,(i, j)∈A, p ∈P, 0≤zijp,(i, j)∈A, p ∈P, imply that zijp = max{0, cij −c(1−xijp)} since zijp appears with a minus sign in the objective function that must be maximized. Taking into account that the constant c is an upper bound on the value of the possible unitary transportation arc cost, that is, cij −c≤0 for all (i, j)∈A, one has that max{0, cij −c(1 −xijp)}=cijxijp,(i, j)∈A, p ∈P. The same argument applies for the wij variables for all (i, j)∈A . Remark 4. The binary constraints on the variables xijp cannot, in general, be removed from the (PP-RND) formulation, contrary to what was mentioned in Remark 3 referent to the (DND) formulation. In this case, the separability reasoning of that remark drives us to obtain an inner optimization problem in which a convex piecewise linear function must be minimized. Since its optima need not be an extreme point of the relaxed polyhedron of feasibility, the unimodular property cannot be applied. Formulation (PP-RND) allows us to assess the opportunity loss of a given design according to the above polyhedral model for the uncertainty on the cost structure. Hence, if we need to compare a nite (and small) number of network designs it suces to choose one of them reaching the minimum of these assessments. However, we are interested here in the problem of nding a robust network design when the number of possible choices is too large to assess the opportunity loss cost of each one of them. If we consider all the possible choices of subsets of arcs Ay making possible to connect the pairs of P , the resulting problem to be solved would be the following one R∗:= min R(x, y) subject to: X (i,j)∈A xijp −X (k,i)∈A xkip =bip, i ∈N, p ∈P, xijp ≤yij,(i, j)∈A, p ∈P, yij ∈ {0,1},(i, j)∈A, xijp ∈ {0,1},(i, j)∈A, p ∈P. (RND)
2.3. Robust models and Benders resolution algorithms 35 Note that, we have just replaced the objective function of the deterministic model (DND) by the opportunity loss cost in (RND). This change represents a substantial change in the resolution methodology since R(x, y) is, in general, a nonlinear function for which the MILP formulation (PP-RND) must be solved to assess it in a given point. In order to nd a robust design we will solve the problem (RND) by a Benders decomposition algorithm. It starts with a given design (x0, y0) and assess its maximum regret by solving the problem (PP-RND) which will be the primal problem . Its optimal objective value represents an upper bound on the optimal value of (RND) and one of its optimal solutions denes a worst-case adversary , (x0, y0) , and a worstcase scenario , s0:= (c0, f0) , for the initial design (x0, y0) . In each iteration, we will nd a minmax regret design for the nite set of worst-case scenarios of the designs previously assessed. The minmax regret value of this last solution will be assessed by solving its corresponding primal problem (PP-RND) and the process continues. The new design found in each iteration is a minmax regret solution for the subset of considered scenarios of costs. The corresponding optimization problem is the master problem and its optimum is a lower bound on the optimal objective value of the problem (RND). For a generic iteration n , the master problem has the following formulation r∗:= min r subject to: X (i,j)∈A fq ijyij +X (i,j)∈A,p∈P cq ijxijp −R(xq, yq, sq)≤r, q = 0, ..., n −1, X (i,j)∈A xijp −X (k,i)∈A xkip =bip, i ∈N, p ∈P, xijp ≤yij,(i, j)∈A, p ∈P, yij ∈ {0,1},(i, j)∈A, xijp ∈ {0,1},(i, j)∈A, p ∈P. (MP-RND) Hence, the resolution of the primal and master problems in each iteration allows us to update a pair of lower and upper bounds on the optimal objective of the problem (RND) whose positive dierence is used to stop the procedure which is stated now as Algorithm 1. Proposition 6. If ε= 0 , Algorithm 1 ends in a nite number of iterations with an optimal solution of the minmax regret network design problem (RND). Proof. First observe that we can assume that the list L of worst-case scenarios can be included in the nite set of vertices of the polyhedron of scenarios of costs S . This
36 Chapter 2. A minmax regret model for the design of supply networks under uncertainties Algorithm 1 1: procedure Initialization 2: Let (xε, yε) := (x0, y0) be an initial feasible design. 3: Solve the primal problem (PP-RND) to obtain the opportunity loss cost R(x0, y0) . 4: Let s0:= (c0, f0) be a worst-case cost scenario for (x0, y0) . 5: Initialize the list L:= {(c0, f0)} . 6: Set β:= R(x0, y0) , an upper bound on the optimal value of (RND). 7: Go to the iteration n:= 1 . 8: procedure Iteration ( n= 1,2, . . . ) 9: Solve the master problem (MP-RND) and let (xn, yn) be one of its optimal solutions. 10: Set α:= r∗ the optimal value of the problem (MP-RND). 11: if β−α < ε then 12: (xε, yε) is an ε -approximation to the problem (RND). 13: else 14: Solve the primal problem (PP-RND) to obtain the value R(xn, yn) . 15: Let sn:= (cn, fn) be a worst-case cost scenario for (xn, yn) and (xn, yn) a worst-case adversary. 16: Update the list L:= L∪ {(cn, fn)} . 17: if R(xn, yn)< β then 18: Update the upper bound β:= R(xn, yn) and (xε, yε) := (xn, yn) 19: Go to the iteration n:= n+ 1 . holds since, by (2.2) , the maximum regret R(x, y) of any network design is attained as the maximum of a convex piecewise linear function on a bounded polyhedron. In order to prove the niteness of Algorithm 1 we will show how the cardinality of the list L increases in one unit in each iteration. Since we have seen the set of possible worst-case scenarios can be considered nite, the number of iterations must be nite too. On the contrary, if the cardinality of L remains unchanged after an iteration n , the worst-case scenario found in Line 15 of Algorithm 1 must already belong to the list L , that is, this scenario has been generated in a previous iteration. In this case, R(xn, yn) = R(xn, yn, sn) = max q=0,1,...,n−1{R(xn, yn, sq)}=α≤R∗≤R(xn, yn), where R∗ is the optimal value of the problem (RND) and it has been used that (xn, yn) is an optimal solution of (MP-RND) for the list of scenarios {sq, q = 0,1, . . . , n −1} (see Line 9). Since in the above chain of inequalities, both extreme are equal we have that Algorithm 1 will end in the following iteration n+ 1 with the optimal solution (xn, yn) .
2.3. Robust models and Benders resolution algorithms 37 Example Grid Design (continuation) In the rst part of this example we assumed that the xed and unitary transportation arc costs were known. Now we will consider that some arc costs are aected by uncertainty which can be caused by dierent situations. Let us think, for instance, that we are designing a transportation network in which we are considering to dig a tunnel through a mountain. Its construction cost can be very variable depending, for instance, on whether unexpected materials making more dicult the digging tasks are found or not. In other projects, the source of the uncertainty can be the lack of experience making some of the involved construction tasks. For example, in the Haramain High-Speed Railway recently opened to the public in Saudi Arabia, connecting the Muslim holy cities of Medina and Mecca, the little experience in the construction of rails over sand was one of the main sources of uncertainty about the construction and maintenance costs (in economical and construction length terms). In order to illustrate such features in our toy example we will identify by a rectangular a unsure zone , that is, a set of potential arcs whose xed costs may vary in an uncertain amount. In Figure 2.2 this unsure zone has been depicted by a grey rectangle where the enclosed arcs are those aected by the uncertain costs. We assume that the xed costs for all those arcs can now vary, increasing or decreasing its value around the previously xed cost of 1 unit, holding this value as the mid-point of the interval of variation, [0.4,1.6] . Figure 2.2 shows the network design that minimizes the maximum regret under this new cost structure, after solving the RND problem with Algorithm 1. We can observe that the network structure has changed signicantly in order to avoid the construction of the potential arcs with uncertain xed costs. Then, incorporating uncertain costs to a road design may signicantly change the structure of the solution by trying to dodge, if possible, the construction of the potential arcs having uncertain costs due to the presence of the unsure zone. This change in the network design seems to be a reasonable (robust) answer to the new unpredictable cost structure and shows the sensitiveness of our model to the uncertain costs.
38 Chapter 2. A minmax regret model for the design of supply networks under uncertainties 1 2 3 1 4 3 4 2 1 Figure 2.1: Example of (DND). 1 2 3 1 4 3 4 2 1 Figure 2.2: A robust design avoiding the construction of arcs with high cost uncertainty. 2.3.2 Uncertain costs and linked pairs In this section we will study how to nd a robust design of the network when the list of linked pairs is partially known. In this case, P becomes the list of pairs that could be linked, that is, the set of pairs that eventually could be connected under a possible scenario, but not necessarily all of them will be connected in a realized scenario. Hence, each scenario will dene the subset of these pairs that are eectively connected and the corresponding transportation costs ( cs ij ). In this new context, each feasible design will be dened by a set of arcs Ay , identied through the binary variables y as in the previous model, and a set of ow variables x that must determine how to connect any pair of origin-destination nodes of P independently of whether they must be connected or not under the scenario that nally occurs. That is, since the scenario that nally will occur is not known a priori, the robust solution must include how to connect each pair of P , just in case the connection is given. As discussed in the introduction, the set of possible scenarios of connected pairs may model potential business relations or ow patterns among nodes requiring some type of connection through the network and verifying a given set of technical requirements. To identify these pairs a new set of binary variables up, p ∈P is dened and it will be assumed that all the technical requirements can be modeled using the following constraints X p∈P eprup≤gr, r ∈R, up∈ {0,1},∀p∈P. (2.3)
2.3. Robust models and Benders resolution algorithms 39 For instance, if R={1} and ep1= 1 for all p∈P , any scenario in which at most g1 linkages in P may happen. Hence, for a given design of the network, a worst-case scenario will detect a set of pairs to be linked and a structure of costs such that, we can nd a new design (its worst-case adversary design) connecting those pairs of nodes as cheap as possible, in comparison with the cost incurred by the initially considered design. In order to nd such a worst-case scenario, we will extend the formulation (PP-RND) to this new context. To do this we will integrate in the formulation the new constraints modelling the scenarios of pairs of nodes to be linked as it is shown in (PPUL-RND). R(x, y) := max X (i,j)∈A fijyij +X (i,j)∈A,p∈P ξijpxijp− −X (i,j)∈A wij −X (i,j)∈A,p∈P zijp subject to: X (i,j)∈A xijp −X (k,i)∈A xkip =bip, i ∈N, p ∈P, xijp ≤yij,(i, j)∈A, p ∈P, X (i,j)∈A (af ijkfij +ac ijkcij)≤dk, k ∈K, X p∈P eprup≤gr, r ∈R, cij −c(2 −up−xijp)≤zijp,(i, j)∈A, p ∈P, 0≤zijp,(i, j)∈A, p ∈P, ξijp ≤cij,(i, j)∈A, p ∈P, 0≤ξijp ≤c up,(i, j)∈A, p ∈P, fij −f(1 −yij)≤wij,(i, j)∈A, 0≤wij,(i, j)∈A, yij ∈ {0,1},(i, j)∈A, xijp ∈ {0,1},(i, j)∈A, p ∈P, up∈ {0,1}, p ∈P, fij ≥0,(i, j)∈A, cij ≥0,(i, j)∈A. (PPUL-RND) Now, for a given design (x, y) , the formulation (PPUL-RND) will nd the design of a worst-case adversary network (x, y) , a possible structure of xed costs, f , unitary transportation arc costs, c , and a subset of origin-destination nodes, u , whose linkage is favoured under this scenario of costs compared with the linkage cost needed in the original design. In the formulation (PPUL-RND) the continuous variables ξijp for all (i, j)∈A
40 Chapter 2. A minmax regret model for the design of supply networks under uncertainties and p∈P have been included to identify if the connection cost of the pair p needs to be added, or not, to the overall cost of the design (x, y) . Observe that the constrains ξijp ≤cij,(i, j)∈A, p ∈P, 0≤ξijp ≤c up,(i, j)∈A, p ∈P, ensure that ξijp will only take the unitary transportation arc cost cij when the binary variable up is equal to one, that is, when the pair of potentially linked nodes pointed by p is included in the set of eectively linked nodes under the considered scenario. Otherwise, these variables are zero for every (i, j)∈A . Remark 5. Observe that, the equations X (i,j)∈A xijp −X (k,i)∈A xkip =bip, i ∈N p ∈P, of the formulation (PPUL-RND) make that all the feasible solutions considered as possible worst-case designs for the solution (x, y) must allow the connection of every potential pair of nodes p∈P . In other case, if we compare the solution (x, y) with adversary designs in which it were only guaranteed the eective connections of those pairs appearing in each assessed scenario we would be inserting an asymmetry into the optimization model (PPUL-RND) since the solution (x, y) is required to have the availability of connecting every potential pair on nodes of P . This asymmetry would give rise to positive regrets even for those solutions (x, y) connecting optimally all the possible pairs under every possible scenario of costs due to the fact that its worst case adversary may not require the construction of the arcs which would assure all the possible connections. Hence in order to assess the maximum regret of a given solution using the formulation (PPUL-RND), the xed costs due to the choice of designs guaranteeing all the potential connections are taken into account both in the considered solution as in its worst-case adversary. However, in both cases the connecting costs are only considered among those pairs of P appearing in the worst-case scenario. This fact is modeled through the constraints aecting to the variables ξijp , as it was commented earlier, together with the constraints lower bounding the variables zijp , cij −c(1 −up)≤zijp,(i, j)∈A, p ∈P. Hence, for any given solution (x, y) , the primal problem (PPUL-RND) nds a worst-case design for it and a worst-case scenario of costs together with the pairs that must be linked in order to reach its maximum regret. Algorithm 1 can be modied
2.4. Computational experiment 47 the constraint referring to the maximum number of two eective linkage under any possible scenario. The values considered for the demands could represent the usual trac value as 1 , twice the usual trac value as 2 and so on. The value 0 represents the absence of trac between the pair of nodes. If the constraint of a maximum number of eective linkage is removed the resulting problem should consider all the scenarios corresponding to the eective linkage of the pairs in any subset of the list P . In our case, with the constraint of at most two eective linkages, these values of 0 -demand are redundant. Solving the problem via Benders decomposition, as described in this section, we obtain an optimal design which is shown in Figure 2.4. Since the set of possible scenarios contains all the possible scenarios of the previous considered variant, the optimal regret increases 5.66% the optimal regret of the previous model. Moreover, the optimal design for the example assuming uncertain costs and linked pairs, represented in Figure 2.3, is not optimal in this new variant of (RND) achieving a maximum regret under the new conditions 58.93% higher that the optimal value. This shows, once again, the sensitiveness of the optimal design under variation on the uncertainty sources. 1 2 3 1 4 3 4 2 1 Figure 2.3: Optimal design assuming uncertain costs and linked pairs. 1 2 3 1 4 3 4 2 1 Figure 2.4: Optimal design assuming uncertain costs, linked pairs and demands. 2.4 Computational experiment In this last section we report some numerical experiments conducted to check the scope and speed of the proposed algorithms and to analyze the structure of the solutions in dierent instances of the (RND) problem under:
48 Chapter 2. A minmax regret model for the design of supply networks under uncertainties 1. uncertain costs, 2. uncertain costs and linked pairs and 3. uncertain costs, linked pairs and demands. In order to conduct the computational study, we generated instances of directed acyclic square grid networks as the one used in the Grid Design example. Specically, the process denes the following elements: • A set of n=m×m nodes corresponding to points on the plane with integer coordinates [x, y] , 1≤x≤m , 1≤y≤m . • A set of forward arcs of the form ([x, y],[x+ 1, y]) , 1≤x≤m−1 , 1≤y≤m . • A set of downward arcs of the form ([x, y],[x, y −1]) , 1≤x≤m , 2≤y≤m . • A set of diagonal arcs of the form ([x, y],[x+ 1, y + 1]) , 1≤x≤m−1 , 1≤y≤m−1 . The grid structure of our instances could have certain actual applications but what is more important for our experimental study is that the considered topology allows us to control possible infeasibility due to the inclusion of disconnected pairs of nodes in the list P . In our case, nodes [i, j] , [k, l] can be linked if, and only if, i≤k and j≤l , or, i>k , j≤l and (i−k)≤(l−j) . Using this characterization of the set of potentially linkable pairs of nodes, a list P of cardinality 3 or 6, was generated randomly for the dierent instances. The computational experiment was carried out on a personal computer with Intel R Core (TM) i7-4720HQ, 2.60GHz with 16384 MB RAM. The algorithms were implemented and solved by using Xpress, Version 8.0. 2.4.1 Uncertain costs The structure of the set of uncertain costs was designed following the idea of the uncertainty set of demand data proposed in Lee et al. (2013). The values f− ij and c− ij were generated randomly in the interval [0,1] . For each arc (i, j)∈A , the xed cost fij could take any value in the interval [f− ij , f− ij +df ij] , and the unitary transportation arc cost cij belongs to the interval [c− ij, c− ij +dc ij] , where df ij and dc ij denote the maximum possible deviations from the nominal cost values f− ij and c− ij , respectively. We use two parameters, Γf and Γc , to control the degree of uncertainty of xed and unitary transportation arc costs, which must belong to the sets F=nfij =f− ij +df ijvf ij,X (i,j)∈A vf ij ≤Γf,0≤vf ij ≤1,∀(i, j)∈Ao,
2.4. Computational experiment 49 and C=ncij =c− ij +dc ijvc ij,X (i,j)∈A vc ij ≤Γc,0≤vc ij ≤1,∀(i, j)∈Ao. The values for the parameters Γf and Γc , controlling the uncertainty degree in costs, were obtained from a regular support of the interval (0,0.1) as a fraction of the number of the arcs having uncertain xed cost or uncertain unitary transportation cost, specically Γf∈ {0.01,0.03,0.05,0.07,0.09} × nf, and Γc∈ {0.01,0.03,0.05,0.07,0.09} × nc, where nf and nc represent the number of arcs with uncertainty in each type of cost. These values were chosen after observing that for smaller values of Γf and Γc the regret became almost 0 , and for bigger values it remained almost constant. In fact, the values corresponding to the 0.09 -fraction of nf and nc are not shown in the following tables 2.2 and 2.3 since they are very similar to the values obtained for the 0.07 -fraction. We generated dierent types of instances for the values of the parameters df ij and dc ij . Table 5.1 shows the dierent discrete distributions used to generate instances at random. For example, for instances of type A, df ij will take the value 0 with probability 3 4 , the value f− ij with probability 1 8 or the value 2·f− ij with probability 1 8 and dc ij will take the value 0 with probability 3 4 or the value c− ij with probability 1 4 . Observe that we are allowing more variability in the xed cost fij from their nominal cost value f− ij than in the unitary transportation cost cij , which can share certain similarities with practical applications in which the construction costs are more variable than the maintenance ones. Note also that in the successive types of instances the probability of an arc to have uncertain costs increases.
50 Chapter 2. A minmax regret model for the design of supply networks under uncertainties Instance type df ij dc ij 0·f− ij , with probability 3 40·c− ij , with probability 3 4 A 1·f− ij , with probability 1 81·c− ij , with probability 1 4 2·f− ij , with probability 1 8 0·f− ij , with probability 2 30·c− ij , with probability 2 3 B 1·f− ij , with probability 1 61·c− ij , with probability 1 3 2·f− ij , with probability 1 6 0·f− ij , with probability 1 30·c− ij , with probability 1 3 C 1·f− ij , with probability 1 31·c− ij , with probability 2 3 2·f− ij , with probability 1 3 Table 2.1: Types of instances. We report in Tables 2.2 and 2.3 the type of instance (type), the number of nodes of each instance (n), the cardinality of the list of node pairs to be linked P ( #P ) and the value of Γf= Γc= Γ of the solved problems. For each conguration of instances and parameters we solved 5 dierent problems and reported the average values of the corresponding indicators; the optimal regret (R ∗ ), the CPU time (CPU), the number of iterations of the algorithm (It.), the percentage of arcs with uncertain cost c (among all the arcs with uncertain cost c ) constructed in the optimal design ( %c ) and the percentage of arcs with uncertain xed cost f constructed in the optimal design ( %f ). We can observe that the average CPU time spent in solving each type of instance clearly increases with the increase of the number of nodes, the cardinality of P , and the value of Γ . For instance, in Table 2.3 we can observe that for type C, n= 100 , P= 3 , Γ=0.01 the average CPU time is less than 6 seconds, meanwhile if we increase Γ to 0.07 the CPU time becomes 366 seconds ( 61 times higher). Tables 2.2 and 2.3 also show the eect of the increase in the variability of the random distributions (Table 5.1), used to generate the range of costs, in the time needed to solve the problem. As might be expected the larger variability in the range
2.4. Computational experiment 51 of costs, the larger CPU time needed to solve the problem. It can also be observed in Tables 2.2 and 2.3 that the percentage of arcs having uncertain costs cij which are included in the robust design is bigger than the percentage of arcs with uncertainty in fij ; this is caused by the type of considered instances. It can be seen in Table 5.1 that the range of variability allowed for costs fij is bigger than the one allowed for costs cij , and therefore including arcs with uncertain fij has a higher eect in the regret. For instance, for type B, n= 196 , |P|= 6 , Γ=0.03 the percentage of arcs with uncertain cij included is 38.10% , meanwhile the percentage of arcs with uncertain fij included is 4.33% . This shows again the sensitiveness of the model to the structure of the uncertainty.
52 Chapter 2. A minmax regret model for the design of supply networks under uncertainties type n #P Γ R ∗ CPU It. % c % f A 100 3 0.01 0.35 0.36 2.20 47.37 6.08 A 100 3 0.03 89.82 0.81 4.00 47.37 5.78 A 100 3 0.05 110.78 1.23 5.00 47.68 5.78 A 100 3 0.07 116.00 1.00 5.00 47.69 6.06 A 100 6 0.01 0.19 0.62 2.20 51.29 7.91 A 100 6 0.03 47.99 1.68 4.20 50.72 6.65 A 100 6 0.05 54.52 2.00 4.20 50.72 6.65 A 100 6 0.07 56.00 1.00 4.00 50.00 6.35 A 196 3 0.01 2.74 1.56 2.80 51.55 1.68 A 196 3 0.03 65.95 2.79 4.40 51.86 0.92 A 196 3 0.05 66.21 2.39 4.00 51.39 1.38 A 196 3 0.07 66.00 2.00 4.00 51.16 1.53 A 196 6 0.01 93.82 4.79 5.20 47.64 3.55 A 196 6 0.03 187.68 7.97 8.20 47.96 3.09 A 196 6 0.05 189.82 7.47 7.80 47.96 3.09 A 196 6 0.07 190.00 8.00 8.00 48.03 3.10 A 225 3 0.01 41.14 2.71 4.00 49.59 2.30 A 225 3 0.03 135.33 5.53 7.00 49.59 2.17 A 225 3 0.05 139.61 6.39 7.60 49.59 2.17 A 225 3 0.07 140.00 6.00 8.00 49.66 1.91 A 225 6 0.01 66.82 6.53 5.00 48.63 3.76 A 225 6 0.03 166.72 9.73 6.40 48.63 3.63 A 225 6 0.05 173.84 13.95 7.80 48.50 3.49 A 225 6 0.07 174.00 11.00 7.00 48.37 3.36 B 100 3 0.01 74.73 2.51 7.00 41.18 4.72 B 100 3 0.03 205.79 6.93 12.40 41.39 3.07 B 100 3 0.05 215.08 4.89 10.80 41.39 2.83 B 100 3 0.07 215.00 6.00 11.00 41.30 2.35 B 100 6 0.01 56.13 0.96 3.80 38.29 6.44 B 100 6 0.03 217.71 2.95 8.00 37.78 5.56 B 100 6 0.05 269.03 2.81 8.00 38.29 5.56 B 100 6 0.07 273.00 3.00 8.00 37.97 5.56 B 196 3 0.01 71.99 3.36 4.80 36.13 1.53 B 196 3 0.03 162.90 4.62 6.00 36.02 1.41 B 196 3 0.05 165.09 4.81 5.60 36.02 1.41 B 196 3 0.07 165.00 4.00 5.00 36.21 1.18 Table 2.2: A-B instances solved by Algorithm 1.
2.4. Computational experiment 53 type n #P Γ R ∗ CPU It. % c % f B 196 6 0.01 83.35 4.39 5.00 38.10 4.22 B 196 6 0.03 133.85 7.22 8.00 38.10 4.33 B 196 6 0.05 134.73 6.30 6.80 38.10 4.33 B 196 6 0.07 135.00 6.00 7.00 38.29 4.09 B 225 3 0.01 80.74 2.52 3.80 38.51 2.83 B 225 3 0.03 184.94 4.63 5.80 38.51 2.83 B 225 3 0.05 209.82 12.19 10.40 38.51 2.83 B 225 3 0.07 211.00 13.00 11.00 38.24 2.44 B 225 6 0.01 289.96 25.11 14.40 41.49 4.79 B 225 6 0.03 358.70 131.23 40.40 41.39 4.28 B 225 6 0.05 410.18 162.56 40.80 41.29 4.69 B 225 6 0.07 411.00 287.00 48.00 41.18 4.59 C 100 3 0.01 122.49 5.68 11.00 14.24 5.57 C 100 3 0.03 421.24 96.54 39.40 14.59 5.23 C 100 3 0.05 497.29 366.81 61.00 14.12 5.11 C 100 3 0.07 506.00 366.00 56.00 14.62 5.23 C 100 6 0.01 277.63 3.05 8.40 18.67 8.35 C 100 6 0.03 446.80 13.03 20.80 18.32 8.35 C 100 6 0.05 376.19 13.77 21.60 18.32 8.59 C 100 6 0.07 378.00 11.00 19.00 18.13 8.82 C 196 3 0.01 303.89 11.65 12.00 13.29 3.76 C 196 3 0.03 366.71 34.03 21.80 13.40 3.59 C 196 3 0.05 202.07 31.38 20.60 13.40 3.59 C 196 3 0.07 202.00 29.00 20.00 13.33 3.70 C 196 6 0.01 591.27 63.55 28.80 14.10 5.55 C 196 6 0.03 153.55 631.47 65.60 14.44 5.38 C 196 6 0.05 118.20 957.16 72.60 14.44 5.44 C 196 6 0.07 138.00 952.00 71.00 14.89 5.49 C 225 3 0.01 471.41 155.13 40.00 12.96 2.64 C 225 3 0.03 419.10 475.85 57.00 12.72 2.59 C 225 3 0.05 419.22 361.13 51.60 12.72 2.59 C 225 3 0.07 419.00 396.00 53.00 12.62 2.64 C 225 6 0.01 460.06 169.47 32.20 15.32 5.32 C 225 6 0.03 363.59 410.52 37.00 15.22 5.42 C 225 6 0.05 499.10 413.69 35.60 14.94 5.32 C 225 6 0.07 500.18 397.38 36.20 15.27 5.32 Table 2.3: B-C instances solved by Algorithm 1.
54 Chapter 2. A minmax regret model for the design of supply networks under uncertainties Finally, Tables 2.2 and 2.3 show clearly the positive correlation between the parameter Γ and the value of the optimal regret. For any given conguration of the instances, the increase in this parameter supposes a higher degree of uncertainty in the model, as a consequence of the denition of the polyhedra F and C , giving rise to the increase of the regret of any feasible design. For instance, for the conguration of type A, n= 100 , |P|= 3 , Γ = 0.01 the regret is 0.35 , meanwhile if we increase Γ to 0.05 the average regret is 110.78 . 2.4.2 Uncertain costs and linked pairs The optimization model given by the formulation (RND) was enriched in Section 2.3.2 by enabling the possibility of considering uncertainty about the subset pairs of nodes of the list P that should be linked under a given scenario. Hence, for this model, one must compute the overall cost of constructing a network being able to connect any pair of nodes that potentially could have to be linked, while the transportation cost only has an eect in the objective function for those pairs of nodes for which it is mandatory to make its linkage under the considered scenario. We show in Tables 2.4, 2.5 and 2.6, as in the precedent tables, the type of instance (A,B or C), its parameter conguration and the average of the CPU times, number of iterations and percentages of arcs with uncertain costs appearing in the optimal design. Here again, % c is the percentage corresponding to the arcs with uncertain unitary transportation cost included in the optimal design and % f the one corresponding to the arcs with uncertain xed cost. Furthermore, we show in the column (g), the maximum number of pairs in P that must be linked under a given scenario. The parameter g is the right-hand side of the constraints (2.3) when r= 1 and in our experiment takes the values 1 and 2 if |P|= 3 and 1,2,3 if |P|= 6 . As the degree of uncertainty increases in this model, so does the size of the corresponding formulation. Consequently, the CPU times spent in solving the new instances increase as it can be clearly observed comparing them with the corresponding entries of Tables 2.2 and 2.3. In fact, certain instances can not be solved within a given time limit. To highlight this point, we have added for each parameter conguration, two new values with the number of problems, out of ve, solved to optimality within a limit of 1800 seconds (column # opt), and its average gap (column Gap). For example, in the easiest case, for instances of type A, n= 36 , P= 3 , Γ=0.01 , g= 1 , we could not solve to optimality one of the problems, whereas for instances of type C, the most dicult ones, we could only solve to optimality 21 out of the 200 generated problems. The size of the considered instances stresses this eect, as can be seen comparing the instances with 36 and 49 nodes over the same table. When compared these new two columns among the three tables, it becomes evident the increase in the hardness of the problem as the result of the increase in the variability
2.4. Computational experiment 55 of the generated uncertain costs, according to the probability distributions specied in Table 5.1. Finally, we observed the behaviour that one may expect in what refers to the increase of the CPU times when the parameter g rises. The increase of such a value results in a bigger set of uncertain scenarios for the problem, making it more dicult to be solved. For example, for instances type A, n= 49 , P= 6 , Γ=0.07 , g= 1,2 , three problems out of ve were solved to optimality, with an average gap of 29.60% and for g= 3 only one of the problems was solved and the average gap raised to 55.63% .
56 Chapter 2. A minmax regret model for the design of supply networks under uncertainties type n #P Γ g #opt CPU Gap It. % c % f A 36 3 0.01 1 4 455.47 20.00 311.40 38.86 4.29 A 36 3 0.01 2 4 455.56 11.62 312.20 38.86 5.16 A 36 3 0.03 1 4 455.66 20.00 313.40 38.86 4.29 A 36 3 0.03 2 4 455.70 13.12 312.60 38.86 5.16 A 36 3 0.05 1 4 455.64 20.00 312.60 38.86 4.29 A 36 3 0.05 2 4 455.58 13.50 312.60 38.86 5.16 A 36 3 0.07 1 4 455.50 20.00 313.80 38.86 4.29 A 36 3 0.07 2 4 455.61 7.47 312.80 38.86 6.02 A 36 6 0.01 1 1 1800.00 64.03 712.00 48.67 14.42 A 36 6 0.01 2 2 1458.53 57.27 530.20 48.83 12.15 A 36 6 0.01 3 2 1458.80 60.00 532.20 50.89 11.15 A 36 6 0.03 1 1 1800.00 75.50 717.40 48.67 12.42 A 36 6 0.03 2 1 1816.99 74.77 712.80 49.78 14.25 A 36 6 0.03 3 1 1800.00 64.25 714.80 48.67 13.42 A 36 6 0.05 1 1 1800.00 63.01 719.40 49.78 10.31 A 36 6 0.05 2 1 1800.00 77.30 714.40 51.84 12.31 A 36 6 0.05 3 1 1800.00 72.96 716.80 51.84 11.31 A 36 6 0.07 1 1 1800.00 62.27 719.80 50.73 12.31 A 36 6 0.07 2 1 1800.00 66.49 720.60 50.89 12.31 A 36 6 0.07 3 2 1458.26 52.15 540.80 49.94 11.31 A 49 3 0.01 1 2 1176.00 52.91 848.40 52.05 4.93 A 49 3 0.01 2 2 1175.68 39.46 845.80 50.92 3.73 A 49 3 0.03 1 1 1535.86 68.98 1133.20 51.45 3.93 A 49 3 0.03 2 1 1536.27 59.18 1119.20 52.05 3.13 A 49 3 0.05 1 1 1535.76 70.32 1135.00 52.05 4.73 A 49 3 0.05 2 1 1535.88 58.59 1113.20 52.05 3.93 A 49 3 0.07 1 1 1535.81 68.00 1136.80 51.45 3.93 A 49 3 0.07 2 1 1535.75 60.71 1125.00 52.05 3.93 A 49 6 0.01 1 3 1102.89 33.57 353.00 50.98 11.98 A 49 6 0.01 2 3 1100.08 39.42 349.00 50.98 12.53 A 49 6 0.01 3 2 1458.78 48.56 523.80 50.98 13.16 A 49 6 0.03 1 2 1460.40 31.39 527.40 50.27 11.98 A 49 6 0.03 2 2 1459.32 31.04 526.20 51.38 13.49 A 49 6 0.03 3 1 1800.00 52.99 699.60 50.98 12.53 A 49 6 0.05 1 3 1102.66 29.86 350.60 50.27 11.98 A 49 6 0.05 2 2 1463.51 49.52 527.80 51.38 11.03 A 49 6 0.05 3 1 1800.00 59.20 703.40 52.29 11.65 A 49 6 0.07 1 3 1102.31 25.00 351.40 50.27 11.98 A 49 6 0.07 2 3 1101.47 29.60 348.40 51.38 10.47 A 49 6 0.07 3 1 1800.00 55.63 700.20 51.38 11.03 Table 2.4: Numerical results for Algorithm 2 with instances Type A.
Chapter 3 A minmax regret model for a time-dependent shortest path problem under uncertainties 64
66Chapter 3. A minmax regret model for a time-dependent shortest path problem under uncertainties We consider a shortest path problem where the arc costs depend on their relative position on a given path and there exist uncertain cost parameters. We study a minmax regret version of the problem under dierent types of uncertainty of the involved parameters. First, we provide a Mixed Integer Linear Programming formulation by using strong duality in the uncertainty interval case. Second, we develop three algorithms based on Benders decomposition for general polyhedral sets of uncertainty. In order to speed up the algorithms we use constant factor approximations to initialize them. Finally, we report some computational experiments for dierent uncertainty sets in order to compare the behavior of the proposed algorithms. 3.1 Introduction Certain real applications require deciding the best schedule plans in which the cost of processing a task depends on its starting time. In many cases, we are given a set of planning tasks, usually represented as the arcs of a network that may model precedence relationships between them, while the goal is to determine the instant in which each task (arc) should start its processing (is traversed) in order to optimize some objective function. Natural examples are timetabling and scheduling problems (Borndörfer and Schlechte (2007); Cacchiani et al. (2010); Cacchiani and Toth (2012); Fischer and Helmberg (2014); Gawiejnowicz (2008)), Shortest Path Problems (SPP) in dynamic networks (Ahuja et al. (2003); Aronson (1989); Cooke and Halsey (1966); Fischer and Helmberg (2014); Hashemi et al. (2010)) or Time-Dependent Traveling Salesman Problems (TDTSP) (Bigras et al. (2008); Furini et al. (2016); Pessoa et al. (2010); Picard and Queyranne (1978); Ta³ et al. (2016); Vander Wiel and Sahinidis (1996)), among others. An interesting type of time-dependency that we would like to emphasize here and that appears in some of the above TDTSP models (Bigras et al. (2008); Picard and Queyranne (1978); Vander Wiel and Sahinidis (1996)) is that of dening the travel cost between the two nodes of any arc as a function of the order in which the traveler moves from one of them to the other into the route. More specically, the travel cost from node i to node j depends on the position that the node i occupies in the ordering sequence of visited nodes. This problem with discrete travel times can be viewed as a single machine scheduling problem with sequence-dependent setup times (Bigras et al. (2008); Picard and Queyranne (1978)). The time-dependent SPP (TDSPP) has been considered under dierent optimality criteria and although there are models that can be solved in polynomial time (Ahuja et al. (2003)), their complexity level is usually very high. The size of an associated network called sometimes time-expanded network (Fischer and Helmberg (2014)), multipartite network (Bigras et al. (2008)) or layered graph (Abeledo et al.
3.1. Introduction 67 (2013)) plays an important role in this level of complexity. This network is the basis of one of the most useful modeling approaches for discrete planning. Depending on the number of arcs and discretized time periods, the full time-expanded network easily grows to a huge number of arcs in actual applications. In order to handle this behavior Fischer and Helmberg (2014) developed a general dynamic graph generation framework to control the size of the network, what is crucial in order to obtain ecient algorithms to solve exactly the corresponding problem. In this chapter, we use a time-expanded network as the basis to obtain a Linear Programming (LP) formulation of time-dependent SPP models where the cost structure takes into account the position that each arc occupies in the path, specically, the total cost associated to each arc is the sum of an amount proportional to the position of the arc in the path and another quantity associated to the arc independently of its position. Furthermore, it is assumed that there exists uncertainty in these two cost coecients and we propose a robust -minmax regretoptimization model in order to obtain a good solution. The complexity of the resulting optimization problem will be related to the region modeling the uncertainty and to the type of dependency on time of the cost structure. In most cases, this complexity will be NP-hard, for instance when the uncertain parameters are modeled through uncertainty intervals the TDSPP includes in particular the standard minmax regret SPP, which is known to be NP-hard (see Section 1.1.1). Although time-dependent and robust SPP models have been studied separately in the literature (see e.g. Ahuja et al. (2003) and Karasan et al. (2001); Montemanni and Gambardella (2004), respectively), to the best of our knowledge this is the rst time that a model, combining the time-dependency and the uncertainty of the costs, is addressed in the context of the minmax regret criterion. As we will see, combining both aspects will have as a consequence the emergence of relationships between the uncertain parameters which breaks the independent variation assumption usually considered in this context. In this chapter we will show how to nd a MILP formulation for the problem assuming uncertainty intervals for the unknown parameters. Generalizing the structure of these uncertainty sets will require new developments in order to extend previous results and to accommodate the new conditions on the sources of uncertainty. We will use a Benders decomposition algorithm to solve numerically the resulting minmax regret TDSPP problem. Moreover, the proposed algorithm can easily be adapted to more general contexts as, for instance, that of the minmax regret TDTSP. An interesting application of this last optimization model can be found in the context of scheduling. As said earlier, some authors (Bigras et al. (2008); Picard and Queyranne (1978)) have applied the TDTSP to model the problem of nding the optimal ordering in which a set of jobs must be processed in a single machine
68Chapter 3. A minmax regret model for a time-dependent shortest path problem under uncertainties to minimize the total completion time. In actual scheduling applications, at times, the parameters describing the problem are only partially known. This uncertainty justies nding robust solutions. For instance, in the simple case in which no precedence order between the tasks is considered and the processing times are uncertain, the shortest processing time (SPT schedule), optimal for the total completion time criterion, may vary from scenario to scenario. This is a serious drawback for decision makers since their actions will possibly be evaluated ex-post and it would be really worthy to have an ex-ante robust schedule as the one proposed by the minmax regret criterion. The minmax regret TDSPP model can also have interesting applications in the eld of scheduling under uncertainty. In TDTSP applications one must nd an optimal circuit in a network representing all the feasible processing orderings. Analogously, in the TDSPP model the goal is to determine an ordered sequence of a subset of tasks. In a context of uncertain processing times, a minmax regret TDSPP optimal solution will ensure a competitive total completion time under any of the considered scenarios. This type of solutions can be used as the basis of a procedure that sequentially assigns subsets of tasks to a set of available machines. In such a procedure, once the rst sequence of tasks (a path) has been assigned to one of the machines, they (the tasks) would be removed from further consideration. Then, a new network would be built and the process repeated with the remaining tasks not yet processed. Similar schemes are used in Grid Computing (see, for instance He et al. (2003)) to assign feasible sequences of tasks to a set of available processors. In a grid computing architecture, a set of processors share a set of tasks according to certain technical characteristics. Some of them, as the required processing time of the tasks or the transfer speed together with the required computing recourses, could be uncertain. Most of this problems studied in the literature have a high level of diculty since they are modeled as multiobjective combinatorial optimization problems (see for instance Ma et al. (2011a,b) and the references therein). This inherent diculty increases when the problem is considered in an uncertainty context, which makes the construction of heuristic assignment procedures, like the one suggested above, a valuable tool. In the following Section 3.1.1, we give another application of the TDSPP, based on the design of a searching strategy to nd a hidden object in a nite set of possible locations. We present this application only for illustrative purpose. This optimization model will be used along the chapter as a conductive example to write dierent formulations for its minmax regret version under uncertain costs, to show dependency relations between these cost parameters and to complete some of the numerical experiments reported at the end of the chapter. In Section 3.2 we give an LP formulation of the TDSPP using a time-expanded network. As an application,
3.1. Introduction 69 a formulation of the searching problem is proposed. In Section 3.3.1, it is shown how the dual of this LP problem allows us to obtain a MILP formulation for the minmax regret TDSPP under uncertainty intervals of costs. We extend here previous results on the minmax regret SPP to the specic cost structure in which the two types of involved costs vary independently into their corresponding uncertainty intervals. A new and more general case in which we consider polyhedral sets of uncertainty for these costs is also studied in this section, where three dierent Benders decomposition algorithms are analyzed. Although Benders decomposition has been applied to SPP in the past (see e.g. Montemanni and Gambardella (2005b)), we have developed a specic Branch and Cut procedure with Benders cuts reinforced with a set of initial cuts which are obtained from constant factor approximations to the problem (Conde (2010); Kasperski and Zielinski (2006)). In the last section of this chapter, the computational results of a numerical experiment including dierent uncertainty models for the searching problem are shown. In this experiment we have also compared dierent strategies for the Benders scheme with the exact resolution of the problem using standard optimization software. 3.1.1 An illustrative Example We will describe here a new application of the TDSPP in the form of a game in which a hidden item is searched in a nite set of possible locations. This item could be some material object or not, for example a piece of information searched within a set of databases where one has to decide which databases are processed and which are not. The sequence followed over the locations to search for the item is determined by the accessing costs and the rewards obtained in the case of nding the object. Obviously, practical situations may include additional aspects to this basic optimization model that could substantially increase its diculty. However, even in those cases, the resulting model could still share some of the essential characteristics described here. Suppose that we need to nd an object that can be located in one of n possible positions with probability pi, i = 1, . . . , n . If the object is found at the position i one obtains a given reward ri , otherwise the prot is zero. In the case that the object has been found at the position i , the searching process is stopped, otherwise we can continue searching at another position j or nish the process. In this model, the decision of searching at the position j , given that the object has not been found at the location i , can only be taken if the arc (i, j) exists. In addition, we assume that this decision implies that one must pay dij units to access to this location j from i . The searching problem consists in choosing a sequence of positions in which we will search this object according to the expected reward. This sequence is chosen a priori, that is, we do not use the information of the previously visited nodes in order to modify the searching strategy. Next, we formally describe the searching example.
70Chapter 3. A minmax regret model for a time-dependent shortest path problem under uncertainties Let us consider a connected digraph G= (N, A) with a set of nodes N= {0,1, . . . , n + 1} and a set of arcs A⊆N×N . Nodes 0 and n+ 1 represent, respectively, the starting point and the ending of the searching process. Any other i represents one of the n positions where the object may be searched. We assume that all the arcs (0, i), i = 1, . . . , n + 1 and (j, n + 1), j = 0,1, . . . , n belong to A , each with zero cost, d0i= 0, i = 1, . . . , n + 1 and dj(n+1) = 0, j = 1, . . . , n . The inclusion of these arcs, at zero cost, enables us to start/end the searching process at any node. Any other arc in A has an associated cost dij . As it was described above, under these conditions the searching problem is equivalent to determining a shortest path in G between 0 and n+ 1 with the cost structure induced by the coecients dij and ri , for every possible i and j . For instance, if the resulting path is only composed of the arc (0, n + 1) , then the optimal solution does not search for the object at all. This particular case can occur if the expected reward of nding the object does not compensate the expected cost of any searching process. Let P denote the set of paths in G from 0 to n+ 1 , and let us consider a path (0, i1),(i1, i2),...,(ik−1, ik),(ik, n + 1) . For notational convenience we take i0= 0 , ik+1 =n+ 1 and r0=rn+1 = 0 . Once a path has been chosen, the corresponding cost is a random variable taking the values t X s=0 disis+1 −rit+1 , t = 0,...k−1 with `a priori' probability pit+1 of nding the object at the node it+1 , where p0= pn+1 = 0 , and the value k X s=0 disis+1 , with a probability 1−Pk t=1 pit that the object is located in one of the non-visited nodes. After some algebra, the expected cost can be written as k X s=0 disis+1 −ris+1 pis+1 −disis+1 s X t=1 pit!. (3.1) Hence, the contribution of each arc (is, is+1) to the cost has two parts, an individual cost which is specic for the arc, disis+1 −ris+1 pis+1 minus the amount disis+1 Ps t=1 pit that depends on the nodes visited previously to is in the path. In the case that pi= 1/n , i= 1...n (discrete uniform distribution) the latter contribution depends only on the position of the arc (is, is+1) into the path, that is, the expression (3.1) reduces to 1 n k X s=0 ndisis+1 −ris+1 −sdisis+1 . (3.2)
3.1. Introduction 71 Let us observe that each one of these addends can be written as (n−s)disis+1 −ris+1 . (3.3) Hence, in order to minimize the expression (3.2) a tentative searching path should locate its arcs with larger dij -costs in its last positions. In this way, these accessing costs would penalize the total cost as little as possible since they would be multiplied by the factor (n−s) which is decreasing with respect to the position of the arc in the path. On the other hand, if the reward rj is high enough, the node j , could be included in the searching path even if the cost of accessing this node is considerable, because the path will try to include all the arcs with negative contribution to the cost (3.3) . Note at this point that, although the coecients (3.3) could be negative and could give rise to negative cycles, an optimal solution of the problem can be found by means of a ow problem with unitary upper bounds on the arc ows. For further details on this point, the reader is referred to the discussion in Section 3.2. Thus, taking into account that n is a constant, the proposed optimization problem would consist in determining a shortest path x∈ P , from 0 to n+ 1 , with arc costs cij +αijpositij(x) , where cij =ndij −rj , αij =−dij and positij(x) is the position occupied by the arc (i, j) in the corresponding path x∈ P . We will end this section setting out a very simple numerical instance of this searching problem which will be used to illustrate later formulations and results. Example Searching Game Consider the digraph G={N, A} with N={1,2,3} and A={(1,2),(1,3), (2,3)} . We need to nd an object that is located in one of the 3 nodes of G with probabilities 1 3 .
72Chapter 3. A minmax regret model for a time-dependent shortest path problem under uncertainties 1 r1= 5 2 r2= 5 3r3= 10 d12 = 2 d13 = 5 d23 = 4 Figure 3.1: Searching network. If the object is found at the positions 1 or 2 one obtains rewards r1=r2= 5 , and if it is found at the position 3 a reward of r3= 10 . The costs of crossing the three arcs (1,2),(1,3) and (2,3) of the graph are d12 = 2 , d13 = 5 and d23 = 4 respectively, as shown in Figure 3.1. We add to the network of Figure 3.1, the node 0 representing the starting point of the searching process, the node 4 representing its ending, and the corresponding arcs (0, i) , i= 1,2,3,4 , (j, 4) , j= 1,2,3 , all of them with cost 0 (Figure 3.2). 1 r1= 5 2 r2= 5 3 r3= 10 0 r0= 0 4r4= 0 d12 = 2 d13 = 5 d23 = 4 0 0 0 0 0 0 0 Figure 3.2: Searching problem network. Then, from the denition of the searching problem, the choice of a sequence of positions in which we will search the object according to the expected reward is
3.3. Robust Model formulations and Benders algorithms 79 formulation (Kasperski (2008); Karasan et al. (2001)). However, for a given x∈ P , if the function y7→ max (c,α)∈S[Z(x, c, α)−Z(y, c, α)] can be written as a linear function of y with its coecients also depending linearly on x , it is still possible to apply LP duality in order to obtain a MILP formulation. We will use this property to extend the classical duality development to obtain a MILP formulation when there exists uncertainty about the true values of both sets of costs, cij and αij , that is, the parameters αij are not longer crisp or nominal ( α− ij ≤α+ ij ). Let us dene the following set of linear functions of x∈ P , αw ijk(x) = kα− ij + (α+ ij −α− ij) X t:(i,j,t)∈A min{k, t}xt ij . (3.7) Proposition 9. The costs cw ij(x) and αw ijk(x) for (i, j, k)∈A , dened by (3.6) and (3.7) , verify max (c,α)∈S[Z(x, c, α)−Z(y, c, α)] = X (i,j,t)∈A (c+ ij +tα+ ij )xt ij −X (i,j,k)∈A (cw ij (x) + αw ijk(x))yk ij when the set of cost scenarios S is the hypercube dened by the uncertainty interval [c− ij, c+ ij] and [α− ij, α+ ij] for every (i, j)∈A . Proof. By (DT DSPP) , Z(x, c, α)−Z(y, c, α) = X (i,j,k)∈A cij(xk ij −yk ij) + X (i,j,k)∈A kαij(xk ij −yk ij). (3.8) The rst summation can be written as X (i,j)∈A cij X k:(i,j,k)∈A xk ij − X k:(i,j,k)∈A yk ij therefore, as x, y ∈ P , its maximum in cij ∈[c− ij, c+ ij] is reached when cij =cw ij(x) as dened in (3.6) . Hence, max cij ∈[c− ij , c+ ij ], (i, j)∈AX (i,j,k)∈A cij(xk ij −yk ij) = X (i,j,t)∈A c+ ijxt ij −X (i,j,k)∈A cw ij(x)yk ij, since, for any x∈ P , Pk:(i,j,k)∈Axk ij ∈ {0,1} . On the other hand, in order to maximize in α the second summation of (3.8) we
80Chapter 3. A minmax regret model for a time-dependent shortest path problem under uncertainties can observe that max αij ∈[α− ij , α+ ij ], (i, j)∈A X k:(i,j,k)∈A kαij (xk ij −yk ij ) = α+ ij X t:(i,j,t)∈A txt ij −X k:(i,j,k)∈A kyk ij − (3.9) −(α+ ij −α− ij ) X k:(i,j,k)∈A X t:(i,j,t)∈A min{k, t}xt ij −k yk ij , (3.10) where (3.10) is nonzero only if there exists k > Pt:(i,j,t)∈Atxt ij such that yk ij = 1 . Using this last expression the result follows. Based on the construction of the network G described in the previous section, one can write the dual formulation of the SPP problem (DT DSPP) as Z(c, α) = max u00 −u(n+1)(n+1) st. uik −uj(k+1) ≤cij +kαij,∀(i, j, k)∈A, (3.11) where the variable u00 can be xed to 0 since the structure of this problem makes that any feasible solution can be identied with a ray of solutions obtained by adding the same constant to all its components. On the other hand, the problem (RTDSP P ) can be written as R∗= min x∈P max y∈P max (c,α)∈S[Z(x, c, α)−Z(y, c, α)] . (3.12) Therefore, by using Proposition 9 and the expressions (3.6),(3.7) , and using an approach similar to that in Karasan et al. (2001), a MILP formulation for problem (RTDSP P ) on acyclic networks can be written as follows R∗= min X (i,j,t)∈A (c+ ij +tα+ ij)xt ij −u00 +u(n+1)(n+1) st. X (i,j,k)∈A xk ij −X (l,i,k−1)∈A x(k−1) li =bi,∀(i, k)∈N, uik −uj(k+1) ≤cw ij(x) + αw ijk(x),∀(i, j, k)∈A, xk ij ∈ {0,1},∀(i, j, k)∈A, (3.13) where b0= 1 , bn+1 =−1 and bi= 0 for all i∈N\ {0, n + 1} and cw(x) , αw(x) are given in (3.6),(3.7) . The above MILP formulation does not apply in general to the searching problem described in the section 3.1.1. The reason is the dependency relationship between
3.3. Robust Model formulations and Benders algorithms 81 the set of costs cij and αij when there exists uncertainty about the true values of the distance costs dij . However, the worst-case scenario (3.6) can be adapted to this model when it is only assumed uncertainty about the set of rewards rj . In the latter situation we have the following specications •cij =ndij −rj and αij =−dij , •rj is an uncertain parameter that can take on any value in the interval [r− j, r+ j] for every j= 1,· · · , n , •c− ij =ndij −r+ j and c+ ij =ndij −r− j for all (i, j)∈A , •(0, j)∈A and (j, n + 1) ∈A for all j= 1,· · · , n , •c+ 0j=−r− j , c− 0j=−r+ j and c± j,n+1 =αj,n+1 = 0 for all j= 1,· · · , n , • the remaining parameters are known (crisp or nominal). By using Proposition 2, it is easy to obtain a worst-case scenario for x∈ P given by the linear expression cw ij(x) = ndij −r+ j+ (r+ j−r− j) X i,k:(i,j,k)∈A xk ij . (3.14) Finally, using (3.14) and taking αw ijk(x) = −dij for all k and x∈ P , we obtain with (3.13) a valid MILP formulation for this model. Example Searching Game (continuation) We continue now with our example assuming that each reward is uncertain, and can take any value in the following intervals r1∈[3,6] , r2∈[4,6] and r3∈[10,30] . The corresponding uncertainty intervals cij ∈[ndij −r+ j, ndij −r− j] are shown in Table 3.2. (i, j) (0,1) (0,2) (0,3) (0,4) (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) [c− ij, c+ ij] [-6,-3] [-6,-4] [-30,-10] 0 [0,2] [-15,5] 0 [-18,2] 0 0 αij 0 0 0 0 -2 -5 0 -4 0 0 Table 3.2: Uncertainty intervals for the cij costs and values for αij . Therefore, following (3.14), we can write the next MILP formulation that models
82Chapter 3. A minmax regret model for a time-dependent shortest path problem under uncertainties the minmax regret time-dependent searching problem: R∗= min −3x0 01 −4x0 02 −10x0 03 + 0x1 12 + 0x1 13 −2x1 23 −6x2 23 −u00 +u44 st. x0 01 +x0 02 +x0 03 +x0 04 = 1, x0 01 −x1 12 −x1 13 −x1 14 = 0, x0 02 −x1 23 −x1 24 = 0, x0 03 −x1 34 = 0, x1 12 −x2 23 −x2 24 = 0, x1 13 +x1 23 −x2 34 = 0, x2 23 −x3 34 = 0 −x0 04 −x1 14 −x1 24 −x1 34 −x2 24 −x2 34 −x3 34 =−1, u00 −u11 ≤ −6+3x0 01, u00 −u21 ≤ −6+2x0 02, u00 −u31 ≤ −30 + 20x0 03, u00 −u41 ≤0, u11 −u22 ≤2x1 12 −2, u11 −u32 ≤ −15 + 20x1 13 −5, u21 −u32 ≤ −18 + 20(x1 23 +x2 23)−4, u22 −u33 ≤ −18 + 20(x1 23 +x2 23)−8, u11 −u42 ≤0, u21 −u42 ≤0, u31 −u42 ≤0, u22 −u43 ≤0, u32 −u43 ≤0, u33 −u44 ≤0, xk ij ≥0,∀(i, j, k)∈A, As we have seen in this section, under a specic structure of the uncertain parameters of the model, we can obtain a MILP formulation and hence, we can solve exactly the problem for instances of moderate size. However, the independent variation of the uncertain parameters in the set of scenarios could be unrealistic in some applications. For instance, in the searching problem, as we have just seen, if the rewards rj and the accessing costs dij are all uncertain it is not possible to apply Proposition 9 to get the above MILP formulation. In the following section we will consider an alternative way of solving a more general problem.
3.3. Robust Model formulations and Benders algorithms 83 3.3.2 Polyhedral uncertainty set In this section, we analyze the minmax regret TDSPP problem (RTDSP P ) in a more general context. Now, we will permit that the uncertainty aects and links simultaneously both coecients cij and αij of (3.4) . This new framework allows us, for instance, to consider the searching problem of the section 3.1.1 under simultaneous variations of the rewards rj and accessing costs dij , for every (i, j)∈A . Recall that, in spite of the fact that the following formulations will be given for acyclic graphs, they can be extended to not acyclic graphs by including the unitary upper bound constraints described in Section 3.2. Furthermore, the approach developed in this section can also be applied to the minmax regret TDTSP problem by adapting the constraints of the formulations described here to the structure of the TSP. In order to model the set of possible scenarios, it is assumed that (c, α)∈S , where S⊂R2|A| is a bounded polyhedron. In general, when an arbitrary polyhedron models the set of possible scenarios, one does not have a closed-form for a worst-case scenario that could be used to reformulate the problem. In this situation, we need to determine numerically a worstcase scenario for each given solution x∈ P . Solving the following formulation (3.15), one can nd simultaneously a worst-case scenario for a given x and additionally an optimal solution to the underlying deterministic model for such a scenario, a worst-case adversary , R(x) = max X (i,j,k)∈A xk ij(cij +kαij)−X (i,j,k)∈A yk ij(cij +kαij) st. X (i,j,k)∈A yk ij −X (l,i,k−1)∈A y(k−1) li =bi,∀(i, k)∈N, yk ij ∈ {0,1},∀(i, j, k)∈A, (c, α)∈S, (3.15) where b0= 1 , bn+1 =−1 and bi= 0 for all i∈N\ {0, n + 1} . Under our hypothesis all the constraints of (3.15) are linear functions of the decision variables (y, c, α) . Nevertheless, we have a quadratic objective function and the binary variables yk ij . This last inconvenience comes from the fact that the constraints of (3.15) are, in general, not totally unimodular since we are considering general polyhedra S to model the set of possible cost scenarios. In what follows the quadratic objective function of the problem (3.15) will be linearized using that S is a bounded set. This linearization makes possible to write the problem as a MILP formulation which opens the possibility to apply o-the-shelf solvers in order to have an optimal solution.
84Chapter 3. A minmax regret model for a time-dependent shortest path problem under uncertainties Let us dene M= max (c,α)∈Sk(c, α)k∞. (3.16) Such a constant M exists since S is bounded. We add now the new decision variables zk ij, wk ij,∀i, j, k , and the following constraints −Myk ij ≤zk ij ≤cij +M(1 −yk ij), cij −M(1 −yk ij)≤zk ij ≤Myk ij, −Myk ij ≤wk ij ≤αij +M(1 −yk ij), αij −M(1 −yk ij)≤wk ij ≤Myk ij, ∀i, j, k , to formulation (3.15) . On the one side, observe that if yk ij = 0 the above constraints imply that zk ij = 0 and wk ij = 0 . On the other hand, if yk ij = 1 we obtain that zk ij =cij and wk ij =αij . Therefore, making zk ij =cijyk ij and wk ij =αijyk ij,∀i, j, k in formulation (3.15) we obtain an equivalent MILP formulation. R(x) = max X (i,j,k)∈A xk ij(cij +kαij)−X (i,j,k)∈A (zk ij +kwk ij) st. X (i,j,k)∈A yk ij −X (l,i,k−1)∈A y(k−1) li =bi,∀(i, k)∈N, yk ij ∈ {0,1},∀(i, j, k)∈A, −Myk ij ≤zk ij ≤cij +M(1 −yk ij),∀(i, j, k)∈A, cij −M(1 −yk ij)≤zk ij ≤Myk ij,∀(i, j, k)∈A, −Myk ij ≤wk ij ≤αij +M(1 −yk ij),∀(i, j, k)∈A, αij −M(1 −yk ij)≤wk ij ≤Myk ij,∀(i, j, k)∈A, (c, α)∈S, (PP-RTDSPP) where b0= 1 , bn+1 =−1 and bi= 0 for all i∈N\ {0, n + 1} . Henceforth we will refer to Problem (PP −RTDSP P) as the primal problem . By solving the primal problem we obtain a worst-case scenario (cw(x), αw(x)) ∈S for the solution x∈ P . Furthermore, by solving this primal problem we also obtain the maximum regret for x , R(x) , which denes an upper bound for the optimal objective value of the problem (RTDSP P ) . A lower bound of this optimal value can be obtained through the master problem . In order to dene it, let us suppose we have solved several primal problems (PP −RTDSP P) for a set of feasible solutions xτ, τ ∈T and we have obtained the set of worst-case scenarios (cτ, ατ) for τ∈T . In
3.3. Robust Model formulations and Benders algorithms 85 what follows, for simplicity, we will represent by (cτ, ατ) the specic solution (worstcase scenario) of the primal problem for each iteration τ∈T . The master problem associated to this set T has the following format t∗= min t st. x∈ P, R(x, cτ, ατ)≤t, ∀τ∈T. (3.17) Given the set of scenarios ST={(cτ, ατ) : τ∈T} ⊂ S obtained from the resolution of a family of primal problems, we have max (c,α)∈ST R(x, c, α)≤max (c,α)∈SR(x, c, α) that is t∗= min x∈P max (c,α)∈ST R(x, c, α)≤min x∈P max (c,α)∈SR(x, c, α) = R∗. (3.18) Hence, solving the master problem allows us to bound from below the optimal objective R∗ of the minmax regret TDSPP (RTDSP P ) . In order to solve the master problem by a standard solver we must rewrite its formulation (3.17) . First, note that, after solving the primal problem (PP −RTDSP P) corresponding to a feasible solution xτ, τ ∈T , one obtains its worst-case scenario (cτ, ατ) and its worst-case adversary yτ which is optimal for the deterministic problem under the scenario (cτ, ατ) . Hence, according to the denition of the regret function in (3.5) we have R(x, cτ, ατ) = Z(x, cτ, ατ)−Z(cτ, ατ) = Z(x, cτ, ατ)−Z(yτ, cτ, ατ). This identity allows us to rewrite the corresponding constraints of the master problem as linear inequalities on x using the expression of the function Z(x, c, α) given in (DT DSPP) . Therefore, one has the following MILP formulation for the master problem t∗= min t st. X (i,j,k)∈A xk ij −X (l,i,k−1)∈A x(k−1) li =bi,∀(i, k)∈N, X (i,j,k)∈A (xk ij −ykτ ij )(cτ ij +kατ ij)≤t, ∀τ∈T, xk ij ∈ {0,1},∀(i, j, k)∈A, (MP-RTDSPP)
86Chapter 3. A minmax regret model for a time-dependent shortest path problem under uncertainties where b0= 1 , bn+1 =−1 and bi= 0 for all i∈N\ {0, n + 1} . Let x∗ be an optimal solution of Problem (MP −RTDSP P ) with objective value t∗ . Now the process will continue computing the maximum regret of x∗ by solving the corresponding primal problem (PP −RTDSP P) . Next, its worst-case scenario (c∗, α∗) is added to the set ST after a new index is also added to T and the process is repeated. The optimality of the algorithm is guaranteed due to the niteness of the set P and the following observation. Proposition 10. Let x∗ be an optimal solution of the master problem associated to the set of indices T and (c∗, α∗) an optimal solution of its corresponding primal problem. Then x∗ is an optimal solution for the minmax regret TDSPP (RTDSP P ) if there exists an index τ∈T for which x∗=xτ or (c∗, α∗)=(cτ, ατ) . Proof. Let us rst suppose that x∗=xτ for a given τ∈T . According to the formulation (3.17) we have t∗≥R(x∗, cτ, ατ) = R(xτ, cτ, ατ) = R(xτ), where the last equality follows from the denition of the primal problem (PP −RTDSP P) . Furthermore, we know by (3.18) that t∗ is a lower bound for R∗ , then t∗≤R∗≤R(xτ), hence R(x∗) = R(xτ) = R∗ , that is, x∗ is an optimal solution the minmax regret TDSPP (RTDSP P ) . Let us now suppose that (c∗, α∗) = (cτ, ατ) for a given τ∈T . In that case, considering the constraints of the problem (3.17) , we have R(x∗)≥R∗≥t∗≥R(x∗, cτ, ατ) = R(x∗, c∗, α∗) = R(x∗). Therefore, x∗ solves the minmax regret TDSPP (RTDSP P ) . Using these results, we will propose three algorithms for solving the minmax regret TDSPP (RTDSP P ) . The rst algorithm is based on a Benders Decomposition. A similar algorithm was originally applied to a Robust Shortest Path Problem (RSPP) in Montemanni and Gambardella (2005b). Here, we adapt it to our time-expanded network and in addition we initialize the algorithm with a Benders cut coming from a guaranteed 2-approximated solution.
3.3. Robust Model formulations and Benders algorithms 87 Algorithm 3 Benders 1: procedure Initialization 2: Choose x0∈ P and solve the primal problem (PP −RTDSP P) for x=x0 . 3: Let (c0, α0) be an optimal solution for (PP −RTDSP P) . Take T={0} , R+:= R(x0) , ˆx=x0 and go to iteration ν= 1 . 4: procedure Iteration ( ν= 1,2, . . . ) 5: Solve the master problem (MP −RTDSP P ) and let x∗ be an optimal solution of such problem. 6: Solve the primal problem (PP −RTDSP P) for x=x∗ . Let (c∗, α∗, y∗) be an optimal solution of such problem. If R(x∗)< R+ take R+:= R(x∗) and ˆx=x∗ . 7: if ∃τ∈T verifying x∗=xτ or (c∗, α∗)=(cτ, ατ) then 8: x∗ is an optimal solution for the minmax regret problem (RTDSP P ) . END. 9: else if R+−t∗≤ then 10: the solution ˆx is an -approximation to the optimal solution of the problem (RTDSP P ) . END. 11: else 12: take xν=x∗ , (cν, αν) = (c∗, α∗) , T:= T∪ {ν} , and go to iteration ν:= ν+ 1 . Remark 6. In the rst iteration of the Algorithm 3, ν= 1 , we can always take x∗=y0 , the worst-case adversary obtained in the initialization step when the primal problem (PP −RTDSP P) is solved for x=x0 . This is true because R(x, c0, α0) = Z(x, c0, α0)−Z(cτ, α0) hence, as in the rst iteration it is solved the master problem (MP −RTDSP P ) for T={0} , it is equivalent to minimize Z(x, c0, α0) with x∈ P , that is, y0 is an optimal solution of the master problem according to the denition of the primal problem (3.15) and the formulation (DT DSPP) . Therefore, the statement of the rst iteration of the algorithm could be modied according to the above considerations. However, we have preferred to state all the iterations in the same way in order to ease the description of the procedure. Remark 7. Proposition 10 guarantees that the above Algorithm 3 is nite since the number of dierent paths in P and the number of extreme points of S , the candidates to be worst-case scenarios, are nite. Therefore, the algorithm will end with an optimal solution whenever = 0 . Otherwise, when > 0 we can ensure the proposed solution ˆx , is an -approximation for Problem (RTDSP P ) since t∗ is a lower bound of the optimal objective value R∗ and ˆx is the best solution generated during the execution of the algorithm. Therefore, one has 0≤R(ˆx)−R∗≤R+−t∗≤. It is interesting to point out that the best lower bound t∗ coincides in each iteration
88Chapter 3. A minmax regret model for a time-dependent shortest path problem under uncertainties with the optimal objective value of the corresponding master problem which will be greater than or equal to the above lower bound as can be seen from the denition of the master problem (3.17) . The second algorithm that we will analyze is based on a Branch and Cut approach using Benders cuts. To the best of our knowledge, this method has never been applied to a RSPP; however, a similar approach was used, for instance, by Pereira and Averbakh (2013) on the robust set covering problem. In addition, as mentioned in the introduction, we reinforce our Branch-and-Cut with a set of initial cuts from guaranteed 2-approximate solutions based on mid-point scenario solutions, as developed in Section 3.3.3. In the next algorithm we propose, as referred in the rst chapter, Benders cuts are used in a Branch and Cut scheme. First, our procedure starts using an incomplete description of the feasible set of the problem (3.17) and solving its linear relaxation. This initial description will be reinforced during the process by using separating Benders cuts in each subproblem generated with the branch-decision tree. Whenever an integer solution ˆx of the master problem is found, with objective value ˆ t , the primal problem is solved for the corresponding ˆx -solution. Let (ˆc, ˆα, ˆy) be an optimal solution of such problem. If R(ˆx)−ˆ t≤ , ˆx is a candidate to optimal solution and ˆ t a candidate to the optimal objective value, we keep them if they improve the incumbent solution. Otherwise, the solution is cut by introducing the constraint P(i,j,k)∈¯ A(xk ij −ˆyk ij)(ˆcij +kˆαij)≤t∗ to the master problem in the corresponding node of the branch-decision tree. The cut is propagated to all currently active nodes of the corresponding branch of the decision tree. On the other hand, whenever a fractional solution of the master problem is found, with a depth lower than a prespecied level, one of the above cuts is also added to the master problem in order to separate that fractional solution. Once the branch-decision tree has been explored, the incumbent solutions (if there were more than one) are optimal solutions of the problem. We encode the procedure in Algorithm 4 The advantages of this Branch and Cut approach are that the master problem is loaded only once and the cuts are added without restarting the branching tree after every cut is introduced. The disadvantage is that every cut to be added requires to solve a primal problem (and in some cases this number of primal problems to be solved is larger than in the Benders Algorithm 3). Remark 8. For the case in which the uncertainty set is a hypercube (Section 3.3.1) the primal problem is a shortest path problem. Therefore, these problems can be
3.4. Computational Experiment 95 the parameter α0 takes the value 1 3m and both coecients cij and αij are uncertain (Table 3.4) the Combined Algorithm 5 could solve 9 out of 10 instances for the size 225 , whereas the exact formulation and Algorithms 3 and 4 could only solve 0, 5 and 4 instances, respectively. In the same way, when n increases to 324 , and α0=1 m , the Combined Algorithm 5 could solve 5 out of 10 instances, whereas Algorithms 3 and 4 could only solve 1 instance, and the exact formulation could not even be charged by the solver. Furthermore, in those problems where only the coecients cij are uncertain (Table 3.3), for α0=1 m , the Combined and the Benders algorithms were able to solve 8 and 4 out of 10 instances, respectively, when n= 324 within the bound of 7200 seconds. Similarly, we can observe in Table 3.5 that when we consider the instances for graphs with 400 nodes, the Combined algorithm could solve all the instances while the Branch and Cut algorithm was able to solve only 7 out of 10. Finally, from Tables 3.3 and 3.4 we can also conclude that the smallest average gaps, for the general TDSSP, are achieved by the Combined Algorithm 5.
96Chapter 3. A minmax regret model for a time-dependent shortest path problem under uncertainties Exact Formulation Benders Algor. 1 Branch and Cut Algor. 2 Combined Algor. 3 α0 n # opt CPU gap # opt CPU gap # opt CPU gap # opt CPU gap 1/m 100 10 15.2 0.0 10 30.1 0.0 10 22.2 0.0 10 22.4 0.0 1/m 169 10 293.4 0.0 10 1102.5 0.0 10 270.2 0.0 10 280.5 0.0 1/m 225 10 727.9 0.0 10 1161.1 0.0 10 950.0 0.0 10 579.0 0.0 1/m 324 8 3987.1 2.7 4 5785.5 3.1 7 3925.5 4.8 8 3981.5 2.9 1/m 400 3 6847.2 24.1 2 6895.1 9.0 4 5496.2 9.4 5 5949.1 7.6 1/3m 100 10 64.3 0.0 10 44.0 0.0 10 38.9 0.0 10 41.2 0.0 1/3m 169 10 443.9 0.0 10 399.2 0.0 10 281.3 0.0 10 249.2 0.0 1/3m 225 8 3649.1 2.3 8 3146.2 2.4 8 2952.7 2.3 9 2233.7 1.6 1/3m 324 1 6808.6 30.1 1 7167.7 10.7 1 7011.3 13.0 4 6888.1 8.8 1/3m 400 1 7122.7 47.2 1 7108.9 18.4 1 6798.5 18.6 2 6596.7 11.5 Table 3.3: Computational results for the general minmax regret TDSPP with hypercube uncertainty sets for parameters cij .
3.4. Computational Experiment 97 Exact Formulation Benders Algor. 1 Branch and Cut Algor. 2 Combined Algor. 3 α0 n # opt CPU gap # opt CPU gap # opt CPU gap # opt CPU gap 1/m 100 10 108.4 0.0 10 120.5 0.0 10 85.5 0.0 10 85.1 0.0 1/m 169 10 1159.8 0.0 10 1350.6 0.0 9 2017.2 2.0 10 1123.4 0.0 1/m 225 9 3622.8 13.1 9 2698.4 0.0 8 2688.3 1.8 10 1474.2 0.0 1/m 324 ** ** ** 1 6875.8 9.0 1 6829.6 5 5 6873.0 5.4 1/3m 100 10 187.2 0.0 10 104.3 0.5 10 138.7 0.0 10 100.2 0.0 1/3m 169 10 2358.9 0.0 10 898.9 0.1 10 1258.8 0.0 10 808.5 0.0 1/3m 225 0 7890.2 281.6 5 5303.2 5.5 4 5931.8 10.1 9 3305.4 0.0 1/3m 324 ** ** ** 0 7200.0 13.3 0 7200.0 14.3 2 7084.3 11.2 Table 3.4: Computational results for the general minmax regret TDSPP with hypercube uncertainty sets for parameters cij and αij . ** The solver returns an out of memory code. Exact Formulation Benders Algor. 1 Branch and Cut Algor. 2 Combined Algor. 3 n # opt CPU gap # opt CPU gap # opt CPU gap # opt CPU gap 100 10 40.6 0.0 10 9.9 0.0 10 18.3 0.0 10 10.6 0.0 169 10 273.7 0.0 10 24.2 0.0 10 51.4 0.0 10 24.2 0.0 225 9 1913.4 10.0 10 296.7 0.0 10 505.4 0.0 10 354.1 0.0 324 6 4183.3 44.2 10 584.7 0.0 10 1543.7 0.0 10 551.9 0.0 400 8 4703.4 22.2 10 802.0 0.0 7 3253.2 3.6 10 733.3 0.0 Table 3.5: Computational results for the minmax regret searching problem with hypercube uncertainty sets.
98Chapter 3. A minmax regret model for a time-dependent shortest path problem under uncertainties 3.4.2 Polyhedral uncertainty set. To end this computational experiment we are going to consider the minmax regret problem (RTDSPP) under a polyhedral uncertainty set of scenarios S . The instances of this optimization model will be generated according to the searching problem of Section 3.1.1 in which it will be allowed that the uncertainty aects simultaneously to both types of coecients: the accessing costs dij and the rewards rj . Each one of these coecients is supposed to take on any value in their corresponding uncertainty interval, dij ∈[d− ij, d+ ij] and rj∈[r− j, r+ j]∀(i, j)∈A . This uncertainty translated in terms of the coecients c and α gives rise to the following uncertainty polyhedron S={(c, α) : −d+ ij ≤αij ≤ −d− ij,−r+ j≤cij +nαij ≤ −r− j,∀(i, j)∈A} . Observe that S is a bounded set and the constant M , dened in (3.16), can be easily obtained as αmax = max{|d− ij|,|d+ ij|: (i, j)∈A}, cmax = max{|nαmax −r− j|,|nαmax +r+ j|:j= 1, . . . , n}, M= max{αmax, cmax}. Ten dierent instances of each problem were generated for n= 16,25,36,49 . Note that the number of nodes, n , of the graph has been reduced drastically with respect to the instances solved in the previous subsection due to that the diculty of the problems becomes much higher. For each instance, the vectors d− and d+ were randomly generated from a uniform distribution in (0,1) , and the uncertainty interval bounds for the rewards, r− j and r+ j , were randomly generated in pmid j, m2¯ dj+Lj q for every j , with q= 4 , as in the previous subsection. We report in Table 3.6 the number of problems (out of 10) solved to optimality for each n in less than 7200 seconds (# opt), the average gaps and the average computational times (CPU) for the three algorithms. The initialization of these algorithms was made using the cost scenario given by the mid-points of the uncertainty intervals of the coecients dij and rj according to Proposition 12. Table 3.6 shows that Benders Algorithm 3 is always faster than the other two algorithms. For instance, the average CPU time for 25 nodes instances is 91.9 seconds whereas it is larger than 370 seconds for the other algorithms. The reason is that the primal problem (PP-RTDSPP) is an unstructured general LP problem, and the Branch and Cut algorithm has to solve one of these problems in each node of the branching tree. In contrast to the hypercube uncertainty case, when we consider polyhedral uncertainty sets, the saving obtained by the Branch and Cut algorithm by not solving several master problems does not compensate the number of primal problems that need to be solved.
3.5. Conclusions 99 Furthermore, Table 3.6 also shows that in spite of the fact that Benders Algorithm 3 is faster, Combined Algorithm 5 is able to solve optimally the same number of problems for n= 49 , 6 out of 10, with a smaller average gap, that is, near half of the average gap incurred by Algorithm 3. Benders Algor. 1 Branch and Cut Algor. 2 Combined Algor. 3 n # opt CPU gap # opt CPU gap # opt CPU gap 16 10 19.1 0.0 10 91.7 0.0 10 67.2 0.0 25 10 91.9 0.0 10 496.7 0.0 10 379.3 0.0 36 10 557.2 0.0 10 2673.6 0.0 10 1835.9 0.0 49 6 4770.5 6.3 1 7028.2 20.7 6 7016.5 3.2 Table 3.6: Computational results for the minmax regret searching problem with polyhedral uncertainty sets. 3.5 Conclusions In this chapter we dealt with a SPP model with costs dependent on the position occupied by the corresponding arcs in the path, the time-dependent SPP. The problem has been studied when the cost parameters are unknown using the minmax regret paradigm. Two methodologies have been developed, the rst one consists on solving a MILP formulation, the second one applies Benders cuts in order to have an approximation to the optimal solution. The MILP formulation works for the TDSPP when hypercube uncertainty sets are considered. The second methodology is more general. It allows us to consider the minmax regret time-dependent SPP problem under a polyhedral set of possible cost scenarios. Moreover, including in the primal and master problems the constraint that the desired path passes through every node exactly once, the same framework can also be applied to the minmax regret time-dependent TSP problem. This opens a wider set of real applications in timetabling and scheduling, as mentioned in the introduction. Using linear constraints to model dependency relationships amongst the unknown parameters allows us to face new and more realistic situations. Three algorithms have been proposed to solve the problems. These algorithms make use of Benders cuts that, with some variants, are added to a master problem whose solutions become closer to the optimal solution over successive iterations. As it has been reported in the numerical experiments, the performance of these iterative algorithms has been improved by starting the procedure using cuts associated to constant factor approximations. In this chapter we have used 2-approximations obtained, following the propositions 11 and 12, from an optimal solution under the mid-point scenario. However, these approximations are only dened for the cases in which every uncertain cost varies independently of each other in its corresponding
100 Chapter 3. A minmax regret model for a time-dependent shortest path problem under uncertainties uncertainty interval. It would be interesting to study the possible extension of these results to more general uncertainty sets Conde (2012). This could give rise to a research line consisting on the adaptation of these schemes to improve the Benders cuts algorithm when applied to uncertainty sets where the 2-approximations obtained from mid-point scenarios cannot be used. Another possible improvement of the algorithms proposed in this chapter could come from the application of size reduction techniques to the time-expanded network. The size of this network can easily grow in actual applications limiting the eciency of the algorithms, hence it would be a good idea having some type of preprocessing which prunes the network before applying the numerical approach. For instance, Karasan et al. (2001), and more recently Catanzaro et al. (2011), provided sucient conditions for a node and an arc to be always or never in an optimal solution of the minmax regret SPP. It seems interesting to analyze the possible extension of sucient conditions like the ones proposed in those papers to the minmax regret time-dependent models in order to develop variable xing strategies (pegging tests) to reduce the size of the network.
Chapter 4 Minmax regret combinatorial optimization problems with investments 102
104 Chapter 4. Minmax regret combinatorial optimization problems with investments In this chapter, we propose new minmax regret optimization models in a system with uncertain parameters, in which it is allowed to make investments before a minmax regret solution is implemented in order to modify the source or the nature of the existing uncertainty. Therefore, it is allowed to spend resources in order to change the basic cost structure of the system and take advantage of the modied system to nd a robust solution. Some properties of this model allow us to have proper Mathematical Programming formulations that can be solved by standard optimization packages. As a practical application, we consider the shortest path problem in a network in which it is possible to modify the uncertainty intervals for the arc costs by investing in the system. We also give an approximate algorithm and generalize some existing results on constant factor approximations. 4.1 Introduction Most of the minmax regret optimization models considered in the literature (see e.g. Chapter 1 and the references therein) rule out the fact of having some kind of control over the set of unknown parameters. However, the source of uncertainty could be modied or the degree of knowledge about the possible scenarios could change as a consequence of particular actions carried out in the system. For instance, as pointed out in the introduction, if we consider a problem in which the demand of a customer is modeled as an uncertain parameter and we assume that this parameter can take on any value from an interval xed beforehand, then the length of this uncertainty interval can be reduced by performing a prospective study and obtaining some extra information about its behavior. It can be logically assumed that this kind of actions that modify the uncertainty set of possible scenarios involves certain costs in terms of a set of limited resources. On the one hand, these costs can be considered as an investment in the system with the purpose of gaining insight into the mechanism involved in its behavior and obtaining, in this way, more information about the uncertain elements (costs, capacities, lengths, times, etc.). On the other hand, the investment can also have a dierent purpose, the available resources could be spent to modify the nature of the system itself. For example, if we consider a communication network with uncertain parameters, like transfer speed or capacity of the connections, one can invest in order to increase this transfer speed or the capacity of a given connection or even invest in the construction of new connections. In all these cases we are investing in the system in order to modify the range of possible values of the uncertain parameters. Then, the problem will consist in determining how to invest the available resources in order to obtain a robust solution as close as possible to the optimal one under whatever scenario that may occur in the transformed system. Therefore, the
4.3. Model formulation 111 4.3.1 Linear cost bound functions The simplest shape of a cost bound function is the one describing a variation in cost proportional to the investment carried out, that is, c− ij(t) = c− ij −α− ijtij, c+ ij(t) = c+ ij −α+ ijtij, where α− ij, α+ ij, c− ij, c+ ij ∈R+ and c− ij(t)≤c+ ij(t)∀t∈T . By replacing these cost functions in the formulation (RSPPI) one has the following quadratic problem, min X (i,j)∈A (c+ ij −α+ ijtij)xij −un subject to −X (i,j)∈A xij +X (j,k)∈A xjk =bj, j = 1,2, ..., n, uj≤ui+c− ij −α− ijtij + (c+ ij −α+ ijtij −(c− ij −α− ijtij))xij,∀(i, j)∈A, X (i,j)∈A tij ≤1, u1= 0, xij ∈ {0,1},∀(i, j)∈A, tij ≥0,∀(i, j)∈A, (4.4) where b1= 1, bn=−1, bj= 0 ∀j∈V\ {1, n} . In order to linearize this formulation we dene a new set of variables given by pij = tij if xij = 1, 0 otherwise , ∀(i, j)∈A. (4.5) Therefore, adding the following set of constraints to the previous formulation to ensure that pij is the wished product pij ≤xij, pij ≤tij, pij ≥tij +xij −1, pij ≥0 we can replace each product tijxij by pij obtaining, in this way, a MILP formulation
112 Chapter 4. Minmax regret combinatorial optimization problems with investments for the problem (RCI). Observe that if we consider cost bound functions with the same slope for each arc, that is, c− ij(t) = c− ij −αijtij, c+ ij(t) = c+ ij −αijtij,∀(i, j)∈A, the length of the uncertainty cost intervals remains constant for every t∈T . Using these functions we obtain a simpler Mixed Integer Quadratic Formulation for the problem (RCI) in which only the objective is a quadratic function, that is, min X (i,j)∈A (c+ ij −αijtij)xij −un subject to −X (i,j)∈A xij +X (i,j)∈A xjk =bj, j = 1,2, ..., n, uj≤ui+c− ij −αijtij + (c+ ij −c− ij)xij,∀(i, j)∈A, X (i,j)∈A tij ≤1, u1= 0, xij ∈ {0,1},∀(i, j)∈A, tij ≥0,∀(i, j)∈A. (4.6) Some commercial solvers allow to solve this problem directly (like CPLEX), in any case it can be linearized following the same procedure as before. 4.3.2 Piecewise linear cost bound functions We rst discuss the case in which the lower bound for the cost of each arc is dened by the function c− ij(t) = max{c− ij −α− ijtij, c− ij0} (4.7) where c− ij0 is a constant and the corresponding upper bound function is linear, c+ ij(t) = c+ ij −α+ ijtij , and veries c− ij(t)≤c+ ij(t)∀t∈T . If this last condition was not veried it would be included in the set T , in fact, it would be equivalent to include a bound on the investment tij . In order to linearize this new model, the following auxiliary variables are included clowij = max{c− ij −α− ijtij, c− ij0},∀(i, j)∈A,
4.3. Model formulation 113 and lowij = 1 if c− ij −α− ijtij ≤c− ij0, 0 if c− ij −α− ijtij ≥c− ij0, ∀(i, j)∈A. Using the variables lowij we can rewrite clowij as follows clowij =lowijc− ij0+ (1 −lowij)(c− ij −α− ijtij)∀(i, j)∈A. Finally, we dene the set of constraints that guarantee that lowij takes the correct value lowij(c− ij0−c− ij +α− ijtij) + (1 −lowij)(c− ij −α− ijtij −c− ij0)≥0∀(i, j)∈A. Using this new set of variables and constraints, we can formulate the RSPPI with these piecewise linear lower bound cost functions as min X (i,j)∈A (c+ ij −α+ ijtij)xij −un subject to −X (i,j)∈A xij +X (j,k)∈A xjk =bj, j = 1,2, ..., n, uj≤ui+clowij + (c+ ij −α+ ijtij −clowij)xij,∀(i, j)∈A, clowij =lowijc− ij0+ (1 −lowij)(c− ij −α− ijtij),∀(i, j)∈A, lowij(c− ij0−c− ij +α− ijtij) + (1 −lowij)(c− ij −α− ijtij −c− ij0)≥0,∀(i, j)∈A, c+ ij −α+ ijtij ≥clowij,∀(i, j)∈A, X (i,j)∈A tij ≤1, u1= 0, tij ≥0,∀(i, j)∈A, xij, lowij ∈ {0,1},∀(i, j)∈A, where b1= 1, bn=−1, bj= 0 ∀j∈V\ {1, n} . Observe that once again we obtain a quadratic objective function and quadratic constraints due to products xijtij, clowijxij and lowijtij . By dening a new set of variables as in (4.5) we can obtain a MILP Formulation using previous arguments. The above procedure used to adapt the MILP formulation to this type of piecewise linear cost bound functions can also be generalized to manage general piecewise linear functions. Hence, it can also be used to have an approximate MILP formulation for those models using general cost bound functions after approximating them by piecewise linear functions.
114 Chapter 4. Minmax regret combinatorial optimization problems with investments Example Robust SPP with Investments We will consider here an extension of the example proposed in Montemanni and Gambardella (2004) in which it will be allowed to make investments in order to improve the cost structure of the following network 3 4 1 2 [1,2] [4,6] [1,2] [4,8] [3,5] [1,7] Figure 4.1: Network (V, A) for the Robust Shortest Path Problem. The intervals depicted near the arcs represent the static uncertainty cost intervals. For this input, the robust shortest path optimal solution is (1,2),(2,4) which reaches the minimum maximum regret of 3 units. We will now consider that we can invest a total amount of one unit of a given resource and the cost bound functions are described as in (4.7) with cij0= 0 for all (i, j)∈A and the following slopes α± 12 = 0, α± 13 = 4, α± 23 = 2, α± 24 = 0.4, α± 32 = 3.2, α± 34 = 4 In the following Figure 4.2 it has been depicted the dynamic uncertainty cost intervals which depend on the investment carried out in each arc.
4.3. Model formulation 115 t12 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 1 2 3 4 5 6 7 8Uncertainty cost interval for c12 t13 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 1 2 3 4 5 6 7 8Uncertainty cost interval for c13 t23 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 1 2 3 4 5 6 7 8Uncertainty cost interval for c23 t24 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 1 2 3 4 5 6 7 8Uncertainty cost interval for c24 t32 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 1 2 3 4 5 6 7 8Uncertainty cost interval for c32 t34 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 1 2 3 4 5 6 7 8Uncertainty cost interval for c34 Figure 4.2: Dynamic uncertinty costs intervals depending on the investment. Using solver Cplex, one can obtain the optimal solution t34 = 1, and x12 = 1, x23 = 1, x34 = 1 which illustrates how the cost structure of the network is improved by investing all the available resource in the arc (3,4) , giving rise to the input network depicted in the gure 4.3 for the problem of nding the robust shortest path. Now, the minimum maximum regret reached by the path (1,2),(2,3),(3,4) is 2.
116 Chapter 4. Minmax regret combinatorial optimization problems with investments 3 4 1 2 [1,2] [4,6] [1,2] [4,8] [0,1] [1,7] Figure 4.3: Network (V, A) for the Robust Shortest Path Problem with investment t34 = 1 . Hence, the behavior of the new solution with respect to the optimal path under the worst-case scenario has been improved after the investment made in the system. In other words, the consequence of the investment is the reduction of the risk that the decision maker must face up to the action of implementing a solution without the knowledge of the exact scenario that will occur. RSPPI and other problems tting into the formulation (RCI −D) like assignment problems or general ow problems with investments are Strongly NP-hard, due to the fact that the minmax regret versions of these problems without investments, that is, when T is a singleton, are Strongly NP-hard (Section 1.1.1). This fact highlights the importance of having ecient methods that provide approximate solutions even when there exist mathematical formulations enabling us to solve the problem exactly. 4.4 Approximations 4.4.1 2-approximation result Let us consider the problem (RCI) for a xed t∈T , min x∈X R(x, t) := max s∈St X (i,j)∈A cs ij(t)xij −min y∈XX (i,j)∈A cs ij(t)yij , (4.8) and let ¯c(t) be the cost scenario where all its components are xed as the mid-point of their corresponding uncertainty cost intervals dened by the investment t∈T (midpoint scenario). One can have a 2-approximation (see Section 1.1.1, Proposition 4) of this problem by solving the following one
4.4. Approximations 117 min P(i,j)∈A¯cij(t)xij subject to x∈X, (MRCPI t ) the deterministic problem associated to the mid-point scenario. Under the unimodularity condition on the set of feasible solutions X , imposed in Section 4.2, (MRCPI t ) is a Linear Programming problem that can be eciently solved. Furthermore, there are sucient optimality conditions that can be written in terms of basic feasible solutions allowing us making a parametric study with respect to the vector of investments. Let us consider the function t∈T−→ ¯xt∈X, assigning an arbitrary optimal solution ¯xt of the problem (MRCPI t ) to each vector of investments. Following Kasperski and Zielinski (2006), ¯xt is a 2-approximation of the problem (RCI) for a xed t∈T , that is, R(x∗ t, t)≤R(¯xt, t)≤2R(x∗ t, t), (4.9) where R(x, t) is the objective function minimized in (4.8) and x∗ t is one of its optimal solutions. It is easy to see that, by considering only a nite number of investments, one can have a 2-approximate solution for the problem (RCI) when X has the unimodularity property. In order to prove it, let us dene the following nite family of sets TB=t∈T: ¯cN(t)−¯cB(t)B−1N≥0, B ∈ B, (4.10) where B is the set of all the basic feasible matrices B of X={x:Mx =b, x ∈ [0,1]|A|} . Here, we have used for simplicity, the same notation for X and for its continuous relaxation. For a given matrix B , N is the corresponding nonbasic matrix and ¯cB(t),¯cN(t) are the vectors of basic and nonbasic components of ¯c(t) . The family B allows to write the set of feasible investments as a nite union of TB -sets T=[ B∈B TB. (4.11) The previous equality holds because for any arbitrary investment t∈T , the problem (MRCPI t ) has, at least, a basic optimal solution ( X is a bounded polyhedron) with an associated basic feasible matrix B for which ¯cN(t)−¯cB(t)B−1N≥0 is veried.
118 Chapter 4. Minmax regret combinatorial optimization problems with investments The set TB represents the set of investments t∈T for which the basic feasible solution associated with the matrix B is an optimal solution of the problem (MRCPI t ). Hence, this basic solution is a 2-approximation to the optimal solution of the problem (4.8) for every t∈TB . The nite union of TB -sets (4.11) could eventually have only one nonempty set, let us say, TB16=∅ and let x1 be its corresponding basic feasible solution. Under this situation, any optimal solution (x∗, t∗) of the problem (RCI) must verify that t∗∈TB1 , hence the equation (4.9) guarantees that R(x∗, t∗)≤R(x1, t∗)≤2R(x∗, t∗), that is, x1 would be a 2-approximation for the problem (RCI). If this is not the case, but there is a relatively small set of basis dening a nite union of TB -sets of T , one can still nd eciently a 2-approximation for the problem (RCI) by selecting for any one of the corresponding basic feasible solutions an investment minimizing its maximum regret. To see this, we will label as elements of a set K a minimal subfamily of basic feasible matrices B whose sets TB dene a nite union of TB -sets of T , T=[ k∈K TBk. (4.12) We have a set X0={xk, k ∈K} , where xk is the corresponding basic feasible solution for the matrix Bk , that is, xk is optimal for the problem ( Pt ) for every t∈TBk . For each basic solution xk we compute an investment reaching its minimum maximum regret t(xk) given by min t∈Tmax s∈St R(xk, t, s) = = min t∈T X (i,j)∈A c+ ij(t)xk ij −min y∈XX (i,j)∈Ah(c+ ij(t)−c− ij(t))xk ij +c− ij(t)iyij . Note that, if c+ ij(t) and c− ij(t) are linear functions, the problem of determining t(xi) is equivalent to solve a linear problem according to the formulation ( 4.4 ). If these cost bound functions are piecewise linear one can obtain an equivalent MILP by introducing binary variables as in the subsection 4.3.2. Proposition 14. The pair (¯x, t(¯x)) dened by (¯x, t(¯x)) = argmin k∈KR(xk, t(xk)) is an approximation of constant factor 2 for the minmax regret combinatorial optimization problem with investments (RCI).
4.4. Approximations 119 Proof. If we denote by (x∗, t∗) an optimal solution of the problem (RCI): R(x∗, t∗)≤R(¯x, t(¯x)). As T=Sk∈KTBk , ∃k0∈K such that t∗∈TBk0 , therefore: R(x∗, t∗)≤R(¯x, t(¯x)) ≤R(xk0, t(xk0)) ≤R(xk0, t∗)≤2R(x∗, t∗). 2 Unfortunately, obtaining a nite union of TB -sets of T with a small set of basis {Bk:k∈K} is, in general, a dicult task. Note that, if the cost bound functions c± ij(t) are not linear, the set TB do not need to be a convex set nor even a connected set. Hence, the development of a general method to nd an ecient nite union of TB -sets can not take advantage of good geometrical properties whilst generating all the feasible basis is not an option because it is not a polynomial process and it would be equivalent to solve the problem (RCI) by enumeration. In fact, if all the basic feasible matrices are generated the problem of obtaining an approximate solution is meaningless because, in this case, the pair (¯x, t(¯x)) denes by itself an optimal solution since X has the unimodularity property. In what follows, Proposition 14 will be used as the basis of a heuristic scheme to propose a solution close to a 2-approximate solution and an indicator of the quality of such a solution. 4.4.2 Heuristic The algorithm proposed here generates a random sequence of investments in T , for each generated investment t , the problem (MRCPI t ) is solved and after that, the pair (¯x, t(¯x)) is obtained as in Proposition 14. If, in this sequence of investments, there is at least one of them in one of the TB -sets containing the investment vector t∗ of one of the optimal solution of (RCI) then, the sequence of inequalities of the proof of Proposition 14 can be applied and a 2-approximation solution is guaranteed. In order to ensure that this situation occurs with probability one, when the size of the random sample of investments increases to innity (convergence almost sure ), it is sucient to check that a nite union of TB -sets of T can always be selected in such a way that the probability of generating an investment of the random sample belonging to each TB -set is strictly positive. If this is true and the sample is constituted of independent and identically distributed random vectors, the Strong Law of Large Numbers (SLLN) asserts this procedure will nd a 2-approximation of the problem (RCI) with probability one when the size of the sample increases to innity.
120 Chapter 4. Minmax regret combinatorial optimization problems with investments Before giving some conditions under which this argument can be applied, we will formally state the Algorithm 6 Approximate algorithm 1: Choose a sample of investments T={t1, ..., tr} ⊂ T . 2: Solve the problem ( Pt ) for all t∈T in order to obtain the set X0={x1, ..., xr} , where xi denotes an optimal solution of ( Pti ), ti∈T . 3: For each xi∈X0 obtain its best investment t(xi) or one of them if there are more than one. 4: Choose as a candidate solution: (¯x, t(¯x)) ∈argmin{R(xi, t(xi)) : xi∈X0}. (4.13) Proposition 15. If the sample of investments of the Approximate algorithm is independent and identically distributed according to an absolute distribution over T with strictly positive density and the cost bound functions c± ij(t) are continuous in T for all (i, j)∈A , then the candidate solution (4.13) converges almost sure to a 2-approximation of the problem (RCI). Proof. Let us suppose that the set T has nonempty interior, we will show that there exists a nite union of TB -sets of T like (4.11) with all the TB -sets having nonempty interior. If T has an empty interior one can reason in the same way with the relative interior of T , that is, its interior within the ane hull of T . Once this is shown one has that there exists at least a TB -set, with nonempty interior, containing a vector of optimal investments t∗ for the problem (RCI). By the distributional imposed hypotheses, the probability of generating a vector of investments contained in this set is strictly positive, that is, the SLLN guarantees that almost sure one of this vectors will be generated as the size of the sample increases. Finally, we can use the argument stated in the rst paragraph of this section to assert the almost sure convergence of the candidate solution (4.13) to a 2-approximation of the problem (RCI). Let t be an interior point of T , for > 0 suciently small, one can have t∈ B(t, )⊂ int (T) , where B(t, ) is a ball with its center at t and a radius > 0 with respect to the Euclidean distance in <|A| . Since this is a complete metric space, the union of every countable collection of closed sets with empty interior has empty interior (Baire space). Furthermore the functions c± ij are all continuous, by its denition, (4.10) , the sets TB are closed. Hence the following set has an empty interior [ B0∈B0 TB0 where B0 is the set of basic feasible matrices B0 for which int (TB0) = ∅ . The fact
4.5. Computational experiment 127 the values c− ij0 belong to [0,10] . • If the above subset has h arcs, a random vector is generated according to a uniform distribution in [0,1]h+1 . This vector was normalized to one and h of its components were assigned as the investments in the h arcs included in the subset; the remaining component is considered the slack with respect to the total amount of available resources (one unit). • The investments in the arcs not included in the subset were xed to zero. Note that this procedure verify the conditions of Proposition 15 since the density of the investment vector is a mixture of positive densities in subsets covering the set T . The computational experiment was carried out on a personal computer with Intel R Core (TM) i7-4720HQ, 2.60GHz with 16384 MB RAM. The optimization problems were solved exactly by using CPLEX Version: 12.6.1.0 and the approximate algorithm was written as an IBM ILOG CPLEX Optimization Studio project, Version: 12.6.1.0. In tables 1 to 4 it is shown the results obtained for 280 dierent instances of the problem varying the number of nodes of each network and taking the probability of generating an arc as p= 0.6 . The averages of the number of generated arcs appear in the column ( m ). In each table the parameter s is xed, s∈ {3,10} (see the heading of each table) and the parameter n takes the values 150,300,450,600,750,900 and 1050 . Once α, s and n were xed, each row of the table was completed with the averages of the computational times of the exact algorithm (CPU 1 ), the heuristic algorithm (CPU 2 ) and the resolution of the problem (P0 b) (CPU 3 ) for 10 dierent instances of the problem. It is also shown in each row the average values of the fraction ( r ) of the objective value of the approximate solution (numerator) over the optimal objective value of the problem (RCI) (denominator) and the fraction ( b0 ) of the bound b (numerator) over the optimal value of the problem (RCI) (denominator). s=3 α (type I) EXACT FORM. HEURISTIC (Pb') n m CPU 1 CPU 2 r CPU 3 b' 150 267.4 1.0 3.1 1.012 1.0 0.004 300 561.8 3.5 4.0 1.027 3.0 0.006 450 832.1 11.5 5.6 1.029 6.9 0.006 600 1100.7 49.5 7.5 1.028 13.6 0.007 750 1376.9 36.7 7.7 1.021 19.2 0.007 900 1663.7 167.9 9.6 1.023 28.7 0.007 1050 19506.0 ** 11.2 1.025* 39.2 0.007* Table 4.1: Computational Results for s= 3 , α (type I).
128 Chapter 4. Minmax regret combinatorial optimization problems with investments s=3 α (type II) EXACT FORM. HEURISTIC (Pb') n m CPU 1 CPU 2 r CPU 3 b' 150 282.4 1.1 3.7 1.029 1.0 0.053 300 547.7 3.5 5.3 1.023 4.0 0.055 450 824.2 9.2 7.1 1.026 8.9 0.068 600 1108.4 24.1 9.2 1.024 17.9 0.064 750 1380.1 24.6 9.6 1.029 24.3 0.066 900 1678.6 65.3 10.7 1.026 34.0 0.067 1050 1969.0 ** 12.8 1.018* 50.6 0.062* Table 4.2: Computational Results for s= 3 , α (type II). By * we mean that the corresponding value was obtained considering just the problems solved exactly, fewer than 10 instances. By ** we mean that the exact algorithm was stopped after 30 minutes of CPU without nding an exact solution. From Proposition 18 one has the theoretical bound on the optimal objective value of the problem (RCI) R(¯x, t(¯x)) ≤b+ 2R∗, which guarantees us an upper bound on the indicator r greater or equal to 2. However, experimentally we observe that this bound is very conservative because most of the estimations of the parameter r using the corresponding sample average are lower than 1.06 , this is, in most cases the candidate solution is better than a 1.06 - approximation, which is a solution very close to an optimal one. In the worst observed cases, the candidate solution was better than a 1.12 -approximation. Moreover, these approximations were obtained, on average, in a fraction of 0.21 of the time used by the exact formulation. s=10 α (type I) EXACT FORM. HEURISTIC (Pb') n m CPU 1 CPU 2 r CPU 3 b' 150 826.0 2.2 5.0 1.055 3.0 0.032 300 1726.6 12.0 9.1 1.046 7.7 0.052 450 2635.9 41.8 14.2 1.062 15.1 0.060 600 3522.4 118.4 23.1 1.055 33.2 0.055 750 4495.8 166.4 26.8 1.051 45.6 0.065 900 5371.0 303.7 32.5 1.058 78.2 0.059 1050 6299.1 ** 41.6 1.055* 142.9 0.065* Table 4.3: Computational Results for s= 10 , α (type I). By * we mean that the corresponding value was obtained considering just the problems solved exactly, fewer than 10 instances. By ** we mean that the exact algorithm was stopped after 30 minutes of CPU without nding an exact solution. If we compare the computational times required to solve the exact formulation
4.5. Computational experiment 129 s=10 α (type II) EXACT FORM. HEURISTIC (Pb') n m CPU 1 CPU 2 r CPU 3 b' 150 856.8 2.9 5.4 1.049 3.2 0.758 300 1753.1 20.0 10.4 1.099 11.8 0.798 450 2667.8 43.6 15.9 1.103 23.7 0.809 600 3571.4 99.1 22.9 1.122 50.9 0.884 750 4499.8 168.7 28.8 1.091 72.8 0.857 900 5412.4 274.1 36.4 1.117 104.1 0.868 1050 6294.2 328.2 44.9 1.098 144 0.855 Table 4.4: Computational Results for s= 10 , α (type II). By * we mean that the corresponding value was obtained considering just the problems solved exactly, fewer than 10 instances. By ** we mean that the exact algorithm was stopped after 30 minutes of CPU without nding an exact solution. and the ones required to obtain approximate solutions we observe that, when the number of nodes is greater than 300, the heuristic is always faster than the exact formulation. The dierence between these two computational time averages increases substantially with the rise in the number of nodes in the graph. This good behavior of the heuristic procedure, in terms of its computational times, compared with the exact algorithm allows us to nd approximate solutions for large instances of the problem for which the exact formulation can not be solved within the time limit considered (30 mins of CPU). As it can be seen in the three rst tables, for n= 1050 there are instances whose MILP formulations could not be solved within the limit of 30 minutes of CPU. However, the heuristic spent less than 45 seconds to nd an approximate solution in some of these instances. In fact, although it has not been included in the tables, the heuristic found approximate solutions for instances of the problem with 6000 nodes and more than 13200 arcs in less than 4 minutes. This is very interesting since the approximate solution can also be used as a starting solution for exact methods with the consequent saving in computational time due to the fact that a wide subset of feasible solutions can be cut by bounding the objective function. Finally, we comment the experimental results obtained about the bound b on the optimal value of the problem (Pb) . We can see that the estimations of this indicator are relatively small compared with the optimum of the problem in most instances. However, in the last table one can notice a signicative increase of these estimations. The reason of this fact could be the greater arc density of the generated networks ( s= 10 ) together with the high level of variation allowed in the coecients cij ( α type II). The enlargement in the ranges of variation of the cost coecients dening the feasible scenarios would produce, at least as a trend, the increase in the number of the elements of the nite union of TB -sets (4.11) needed to cover the feasible
130 Chapter 4. Minmax regret combinatorial optimization problems with investments set of investments. As it was said in the previous section, in order to obtain a 2- approximation it is needed to have at least a vector of investments of the set T in the interior of each TB -set with non-empty interior. Hence, the greater number of TB - sets, the worse the bound b (as a trend), for a xed number of generated investments in the set T . 4.6 Conclusions In this chapter we have proposed an optimization model under uncertainty in the cost coecients of a linear objective function. Every conguration of possible costs is called a scenario and it is assumed this vector belongs to a hypercube St which depends on a set of investments t∈T carried out in the system. It was adopted as optimization criterion the minimization of the maximum regret over the set of possible scenarios and possible investments. Hence, this model seeks a set of investments under which there exists at least a solution with a performance close to the optimal one under each possible scenario, that is, the objective of the investments is to reduce the uncertainty about the performance of the implemented solution. Some rationality criteria had been considered in order to model the modications undergone by the set of possible scenarios under every feasible investment. We have obtained exact formulations for dierent choices of the structure of the set of scenarios St that allow us to solve the problem using large-scale optimization software packages. However, according to our numerical experiments, the computational cost increases quickly with the size of the problem. This justies the study of approximate methods that could obtain a good starting solution in order to speed up the execution of a subsequent exact algorithm by eliminating a wide subset of feasible solutions. The proposed approximation is based on the resolution of a sequence of deterministic problems with linear structure, thus eciently solvable by standard optimization algorithms. In addition, it is possible to nd a bound on the incurred error to assess the quality of the approximate solution. This bound extends previous results on constant factor approximations for minmax regret optimization problems where no investment is allowed. The numerical comparison of the approximate algorithm with respect to exact methods points out that these approximations could be eciently applied in the design of specialized algorithms to solve new robust combinatorial optimization problems. The analysis of how any piece of relevant information can be extracted from the data and from the structure of the problem in order to guide the generation of the sample of investments used in the approximate algorithm could give rise to interesting results. This research line will be explored in the short future.
Chapter 5 Bilevel Portfolio Selection Problem with Pricing decisions on transaction costs 132
134 Chapter 5. Bilevel Portfolio Selection Problem with Pricing decisions on transaction costs In this chapter, we present new price setting models in the Portfolio Optimization area. Specically, we assume in our models, as a novelty, that the unit transaction costs, charged for investing in some assets of the portfolio, must be decided in the decision process by the nancial intermediary, instead of assuming them given. Henceforth, there are two dierent decision-makers involved in the Portfolio Problem: the nancial intermediary, setting the transaction costs, and the investor, selecting a portfolio. The transaction costs are set trying to maximize the bank's revenue, and the portfolio is chosen trying to minimize the risk and ensuring an expected prot. We assume a hierarchical decision order, and therefore, we present dierent leader-follower versions of the model: nancial intermediary-leader, investor-leader, and social welfare models; and we analyze their properties. Moreover, we develop Mixed Integer Linear Programming formulations for some of the models and eective algorithms for some others. Finally, we report on some computational experiments performed on real data taken from the IBEX 35, the main benchmark stock exchange index of the Spanish stock market, and analyze and compare the results obtained by the dierent models. 5.1 Introduction The classical model in portfolio optimization was originally proposed by Markowitz (1952). This model has served as the initial point for the development of modern portfolio nancial theory. Over time, portfolio optimization problems have become more realistic, incorporating real-life aspects that make the resulting portfolios more cost eective than the alternatives that do not consider them (Castro et al. (2011); Kolm et al. (2014); Mansini et al. (2014, 2015)). Transaction costs can be seen as one of these important actual features to be included in portfolio optimization. These costs are those incurred by the investors when buying and selling assets on real nancial markets, charged by the brokers or the nancial institutions playing the role of intermediary. Transaction costs usually include banks and brokers comissions, fees, rates, etc. These commissions/fees/rates have a direct impact on the portfolio, specially for individual or small investors, since they will determine the net returns, reducing them and decreasing also the budget available for future investments (Baule (2010); Baumann and Trautmann (2013)). To the best of our knowledge, in the existing literature, transaction costs are assumed to be given (Mansini et al. (2014, 2015)). They can be a xed cost applied to each selected security in the portfolio (see e.g. Baule (2010); Baumann and Trautmann (2013); Kellerer et al. (2000); Mansini et al. (2014, 2015); Valle et al. (2014); Woodside-Oriakhi et al. (2013) and the references therein); or a variable rate to be paid which depends on the amount invested on each security included in the port-
5.1. Introduction 135 folio. This dependence can be proportional or be given by a xed cost that is only charged if the amount invested exceeds a given threshold, or some other functional form (see e.g. Baule (2010); Konno et al. (2005); Le Thi et al. (2009); Mansini et al. (2014, 2015) and the references therein). But in any case, unit transaction costs are known and predetermined in the optimization process. Nevertheless, it is meaningful to analyze the situations where transaction costs can be decision variables on nancial institutions' hands so that they are set trying to maximize its own prot as part of the decision process that leads to optimal portfolios for investors. The portfolio optimization problem considered in this chapter is based on a singleperiod model of investment and incorporates a pricing aspect on the transaction costs. We assume that there are two decision-makers involved in the situation: the investor and the nancial institution (that we will call from now on the bank for simplicity). At the beginning of a period, an investor allocates the capital among various assets and during the investment period, each asset generates a random rate of return. Moreover, we consider that the bank can charge some transaction costs on the securities selected by the investor trying to maximize its benets. This is a pricing phase in which the bank makes the decision on how much is going to charge to the traded securities. Considering transaction costs as a decision variable of the model is a novel element in portfolio optimization and it is one of the main contributions of this chapter. Then, at the end of the period, the result for the investor is a change of the capital invested (increased or decreased) which is measured by the weighted average of the individual rates of return minus transactions costs. On the other hand, the result for the bank is the amount paid by the investor which depends on the prices set on the traded securities and the portfolio selected by the investor. Based on the structure of nancial markets, we assume a hierarchical relationship between the parties involved in the portfolio problem, that is, we consider a natural model in which the bank sets the prices rst, trying to anticipate the rational response of the investor. This hierarchical analysis of the portfolio problem has not been addressed before and it is another contribution of our chapter. Once the prices are xed, the investor chooses her optimal portfolio. For the sake of completeness, we also analyze the case in which the investor chooses her portfolio rst, and after that, the bank sets the transaction costs. In order to model these hierarchical structures, we use a bilevel optimization approach (see Section 1.1.2). Furthermore, we consider a social welfare model, that is, a model in which both, bank and investor, cooperate to maximize their returns. We assume in the dierent models that all economic or nancial information is common knowledge and that all the decision-makers in the problem have access to it. The contributions of this chapter can be summarized in the following: 1. it incorporates for the rst time, the above hierarchical approach with two-levels of
136 Chapter 5. Bilevel Portfolio Selection Problem with Pricing decisions on transaction costs decision-makers on portfolio optimization problems (the bank sets transaction costs trying to maximize its benets, whereas the investor minimizes risk while ensuring a given expected return (Benati (2003, 2015))); 2. it introduces transaction costs as decision variables on nancial institutions' hands; 3. it develops dierent bilevel programming formulations to obtain optimal solutions for the considered models. The rest of the chapter is organized as follows. Section 5.2 states the preliminaries and the notation used throughout the chapter. In Section 5.3 we present the models description, the formulations and the resolution algorithms. Particularly, in Section 5.3.1, we present the model in which the bank is the leader and we develop two dierent MILP formulations to solve such problem; in Section 5.3.2, we introduce the investor-leader model and develop a Linear Programming (LP) formulation for it. In the more general case where additional constraints are required on the portfolio selection, we present a convergent iterative algorithm based on an add hoc decomposition of the model. Next, in Section 5.3.3, it is addressed a social welfare model. There, we propose a MILP formulation and an algorithm based on Benders decomposition for solving the problem. In Section 5.4, we report on the computational study of the dierent models discussed in the previous sections. Our results are based on real data taken from IBEX 35, the main benchmark stock exchange index of the Spanish stock market. Finally, Section 5.5 concludes the chapter. 5.2 Preliminaries Let N={1, ..., n} be the set of securities considered for an investment, and B⊆N a subset of securities in which the bank can charge transaction costs to the investor. In most cases, B=N , but there is no loss of generality to consider that B is a proper subset of N . On the one hand, we assume that the bank can price security j∈B from a discrete set, with cardinality sj , of admissible prices, Pj={cj1, ..., cjsj} , and the bank's goal is to maximize its benet. Further, we consider the case in which the price charged by the bank per security is proportional to the amount invested in such security. In other words, the bank's decision variables are unit transaction costs (commissions, fees, rates, ...) to be charged to the securities. Let x= (xj)j=1,...,n denote a vector of decision variables weighting xj the proportion of the total amount invested on security j in the portfolio. We only suppose that the invested capital can not exceed the available budget, i.e. x: n X j=1 xj≤1, xj≥0, for j= 1, ..., n. This budget constraint is the minimum requirement on the structure of the portfolios.