Dans cette thèse, nous étudions différents modèles, déterministes et stochastiques, pour les problèmes de dimensionnement de réseaux. Nous examinons également le problème du sac-à-dos stochastique ainsi que, plus généralement, les contraintes de capacité en probabilité. Dans une première partie, nous nous consacrons à des modèles de dimensionnement de réseaux déterministes, possédant de nombreuses contraintes techniques s'approchant de situations réalistes. Nous commençons par étudier deux modèles de réseaux de télécommunications. Le premier considère des réseaux multi-couches et des capacités sur les arcs, tandis que le second étudie des réseaux mono-couche, sans capacité, où les commodités doivent être acheminées sur un nombre K de chemins disjoint de taille au plus L. Nous résolvons ces deux problèmes grâce à un algorithme de ``branch-and-cut' basé sur la décomposition de Benders de formulations linéaires pour ces problèmes. La nouveauté de notre approche se situe principalement dans l'étude empirique de la fréquence optimale de génération de coupes au cours de l'algorithme. Nous étudions ensuite un problème d'expansion de réseaux de transmission électrique. Notre travail étudie différents modèles et formulations pour le problème, les comparant sur des réseaux brésiliens réels. En particulier, nous montrons que le re-dimensionnement permet des réductions de coût importantes. Dans une seconde partie, nous examinons des modèles de programmation stochastique. Premièrement, nous prouvons que trois cas particuliers du problème de sac-à-dos avec recours simple peuvent être résolu par des algorithmes de programmation dynamique. Nous reformulons ensuite le problème comme un programme non-linéaire en variables entières et testons un algorithme ``branch-and-cut' basé l'approximation extérieure de la fonction objective. Cet algorithme est ensuite transformé en un algorithme de ``branch-and-cut-and-price', utilisé pour résoudre un problème de dimensionnement de réseau stochastique avec recours simple. Finalement, nous montrons comment linéariser des contraintes de capacité en probabilité avec variables binaires lorsque les coefficients sont des variables aléatoires satisfaisant certaines propriétés.

This study addresses the problem of designing a new natural gas transmission network or expanding an existing network while minimizing the total investment and operating costs. A substantial reduction in costs can be obtained by effectively designing and operating the network. A well-designed network helps natural gas companies minimize the costs while increasing the customer service level. The aim of the study is to determine the optimum installation scheduling and locations of new pipelines and compressor stations. On an existing network, the model also optimizes the total flow through pipelines that satisfy demand to determine the best purchase amount of gas. A mixed integer nonlinear programming model for steady-state natural gas transmission problem on tree-structured network is introduced. The problem is a multi-period model, so changes in the network over a planning horizon can be observed and decisions can be made accordingly in advance. The problem is modeled and solved with easily accessible modeling and solving tools in order to help decision makers to make appropriate decisions in a short time. Various test instances are generated, including problems with different sizes, period lengths and cost parameters, to evaluate the performance and reliability of the model. Test results revealed that the proposed model helps to determine the optimum number of periods in a planning horizon and the crucial cost parameters that affect the network structure the most.

Natural disasters and extreme events are often characterized by their violence and unpredictability, resulting in consequences that in severe cases result in devastating physical and ecological damage as well as countless fatalities. In August 2005, Hurricane Katrina hit the Southern coast of the United States wielding serious weather and storm surges. The brunt of Katrina’s force was felt in Louisiana, where the hurricane has been estimated to total more than $108 billion in damage and over 1,800 casualties. Hurricane Rita followed Katrina in September 2005 and further contributed $12 billion in damage and 7 fatalities to the coastal communities of Louisiana and Texas. Prior to making landfall, residents of New Orleans received a voluntary, and then a mandatory, evacuation order in an attempt to encourage people to move themselves out of Hurricane Katrina’s predicted destructive path. Consistent with current practice in nearly all states, this evacuation order did not include or convey any information to individuals regarding route selection, shelter availability and assignment, or evacuation timing. This practice leaves the general population free to determine their own routes, destinations and evacuation times independently. Such freedom often results in inefficient and chaotic utilization of the roadways within an evacuation region, quickly creating bottlenecks along evacuation routes that can slow individual egress and lead to significant and potentially dangerous exposure of the evacuees to the impending storm. One way to assist the over-burdened and over-exposed population during extreme event evacuation is to provide an evacuation strategy that gives specific information on individual route selection, evacuation timing and shelter destination assignment derived from effective, strategic pre-planning. For this purpose, we present a mixed integer linear program to devise effective and controlled evacuation networks to be utilized during extreme event egress. To solve our proposed model, we develop a solution methodology based on Benders Decomposition and test its performance through an experimental design using the Central Texas region as our case study area. We show that our solution methods are efficient for large-scale instances of realistic size and that our methods surpass the size and computational limitations currently imposed by more traditional approaches such as branch-and-cut. To further test our model under conditions of uncertain individual choice/behavior, we create an agent-based simulation capable of modeling varying levels of evacuee compliance to the suggested optimal routes and varying degrees of communication between evacuees and between evacuees and the evacuation authority. By providing evacuees with information on when to evacuate, where to evacuate and how to get to their prescribed destination, we are able to observe significant cost and time increases for our case study evacuation scenarios while reducing the potential exposure of evacuees to the hurricane through more efficient network usage. We provide discussion on scenario performance and show the trade-offs and benefits of alternative batch-time evacuation strategies using global and individual effectiveness measures. Through these experiments and the developed methodology, we are able to further motivate the need for a more coordinated and informative approach to extreme event evacuation.

No description available.

In this thesis we consider some network design games that arise from common network design problems. A network design game involves multiple players who control nodes in a network, each of which has a personal interest in seeing their nodes connected in some manner. To this end, the players will submit bids to a mechanism whose task will be to select which of the players to connect, how to connect their nodes, and how much to charge each player for the connection. We rely on many fundamental results from mechanism design (from [8], [9] & [5]) in this thesis and focus our efforts on designing and analyzing cost-sharing methods. That is, for a given set of players and their connection requirements, our algorithms compute a solution that satisfies all the players’ requirements and calculates ’fair’ prices to charge each of them for the connection. Our cost-sharing methods use a primal-dual framework developed by Agrawal, Klein and Ravi in [1] and generalized by Goemans &Williamson in [3]. We modify the algorithms by using the concept of death-time introduced by K¨onemann, Leonardi & Sch¨afer in [6]. Our main result is a 2-budget balanced and cross-monotonic cost sharing method for the downwards monotone set cover game, which arises naturally from any downwards monotone 0, 1-function. We have also designed a 2-budget balanced and cross-monotonic cost sharing method for two versions of the edge cover game arising from the edge cover problem. These games are special cases of the downwards monotone set cover game. By a result by Immorlica, Mahdian & Mirrokni in [4] our result is best possible for the edge cover game. We also designed a cross-monotonic cost sharing method for a network design game we call the Even Parity Connection game arising from the T-Join problem that generalizes proper cut requirement functions. We can show our algorithm returns cost shares that recover at least half the cost of the solution. We conjecture that our cost sharing method for the even parity connection game is competitive and thus 2-budget balance.

In this thesis we consider some network design games that arise from common network design problems. A network design game involves multiple players who control nodes in a network, each of which has a personal interest in seeing their nodes connected in some manner. To this end, the players will submit bids to a mechanism whose task will be to select which of the players to connect, how to connect their nodes, and how much to charge each player for the connection. We rely on many fundamental results from mechanism design (from [8], [9] & [5]) in this thesis and focus our efforts on designing and analyzing cost-sharing methods. That is, for a given set of players and their connection requirements, our algorithms compute a solution that satisfies all the players’ requirements and calculates ’fair’ prices to charge each of them for the connection. Our cost-sharing methods use a primal-dual framework developed by Agrawal, Klein and Ravi in [1] and generalized by Goemans &Williamson in [3]. We modify the algorithms by using the concept of death-time introduced by K¨onemann, Leonardi & Sch¨afer in [6]. Our main result is a 2-budget balanced and cross-monotonic cost sharing method for the downwards monotone set cover game, which arises naturally from any downwards monotone 0, 1-function. We have also designed a 2-budget balanced and cross-monotonic cost sharing method for two versions of the edge cover game arising from the edge cover problem. These games are special cases of the downwards monotone set cover game. By a result by Immorlica, Mahdian & Mirrokni in [4] our result is best possible for the edge cover game. We also designed a cross-monotonic cost sharing method for a network design game we call the Even Parity Connection game arising from the T-Join problem that generalizes proper cut requirement functions. We can show our algorithm returns cost shares that recover at least half the cost of the solution. We conjecture that our cost sharing method for the even parity connection game is competitive and thus 2-budget balance.

Configuration capabilities are important for modern advanced network services. Network conditions and user populations have been significantly diversified after decades of evolution of the Internet. Configuration capabilities allow network services to be adapted to spatial, temporal, and managerial variations in application requirements and service operation conditions. Network service providers need to decide on the best configuration. Ideally, a network service should have all of its components optimally configured to most effectively deliver the functionality for which it was designed. The optimal configuration, however, is always a compromise between different metrics. To decide on an optimal configuration, the prominent performance and cost metrics must be identified, modeled, and quantified. Optimization objective functions and constraints that combine these metrics should be formulated and optimization techniques should be developed. More important, in the scenarios where the application requirements and system conditions change over time, the service configuration needs to be dynamically adjusted and strategies that guide the reconfiguration decisions need to be developed. Because the actual process of configuring a network service incurs configuration costs, an optimal reconfiguration strategy should be one that achieves a tradeoff between the (re)configuration costs and static optimization objectives. Furthermore, such tradeoffs must be based on the consideration of long-term benefits instead of short-term interest. This thesis focuses on understanding the strategies for dynamic (re)configuration of advanced network services positioned above the Transport Layer. Specifically, this thesis investigates the configuration and more important dynamic reconfiguration strategies for two types of advanced network services: Service Overlay Networks, and Content Resiliency Service Networks. Unlike those network services whose configuration involves mainly arrangement of hard-wired components, these network services have the ability to change service configuration in small time scales. This makes the modeling of application requirements and system condition dynamics not only possible but also meaningful and potentially useful. Our goal is to develop modeling and optimization techniques for network service configuration and dynamic reconfiguration policies. We also seek to understand how effective techniques can improve the performance or reduce the cost of these advanced network services, thus demonstrating the advantage of allowing configurability in these advanced network services.

Supply chain network design (SCND) identifies the production and distribution resources essential to maximizing a network’s profit. Once implemented, a SCND impacts a network’s performance for the long-term. This dissertation extends the SCND literature both in terms of model scope and solution approach. The SCND problem can be more realistically modeled to improve design decisions by including: the location, capacity, and technology attributes of a resource; the effect of the economies of scale on the cost structure; multiple products and multiple levels of supply chain hierarchy; stochastic, dynamic, and correlated demand; and the gradually unfolding uncertainty. The resulting multistage stochastic mixed-integer program (MSMIP) has no known general purpose solution methodology. Two decomposition approaches—end-of-horizon (EoH) decomposition and nodal decomposition—are applied. The developed EoH decomposition exploits the traditional treatment of the end-of-horizon effect. It rests on independently optimizing the SCND of every node of the last level of the scenario-tree. Imposing these optimal configurations before optimizing the design decisions of the remaining nodes produces a smaller and thus easier to solve MSMIP. An optimal solution results when the discount rate is 0 percent. Otherwise, this decomposition deduces a bound on the optimality-gap. This decomposition is neither SCND nor MSMIP specific; it pertains to any application sensitive to the EoH-effect and to special cases of MSMIP. To demonstrate this versatility, additional computational experiments for a two-stage mixed-integer stochastic program (SMIP) are included. This dissertation also presents the first application of nodal decomposition in both SCND and MSMIP. The developed column generation heuristic optimizes the nodal sub-problems using an iterative procedure that provides a restricted master problem’s columns. The heuristic’s computational efficiency rests on solving the sub-problems independently and on its novel handling of the master problem. Conceptually, it reformulates the master problem to avoid the duality-gap. Technologically, it provides the first application of Leontief substitution flow problems in MSMIP and thereby shows that hypergraphs lend themselves to loosely coupled MSMIPs. Computational results demonstrate superior performance of the heuristic approach and also show how this heuristic still applies when the SCND problem is modeled as a SMIP where the restricted master problem is a shortest-path problem.

The structure of a company's distribution network is of vital importance for competitiveness but also involves considerable costs. In recent years, competitive pressure as well as regulatory measures, especially in the European Union, have also raised awareness towards the environmental impact of supply chain activities. However, activities associated with the distribution of products are not yet subject to environmental regulations but this might change in the near future. Therefore, companies will have to consider not only economic but also environmental aspects in the design of their supply chains. Based on a case study from the petrochemical industry we present a way to evaluate (strategic) distribution network design decisions, taking into account economic as well as environmental criteria. The results of the analysis show a clear trade-off between (distribution) costs and transport carbon emissions. (author's abstract)

The focus of this thesis is on the design and analysis of algorithms for basic problems in Stochastic Optimization, specifically a class of fundamental combinatorial optimization problems where there is some form of uncertainty in the input. Since many interesting optimization problems are computationally intractable (NP-Hard), we resort to designing approximation algorithms which provably output good solutions. However, a common assumption in traditional algorithms is that the exact input is known in advance. What if this is not the case? What if there is uncertainty in the input? With the growing size of input data and their typically distributed nature (e.g., cloud computing), it has become imperative for algorithms to handle varying forms of input uncertainty. Current techniques, however, are not robust enough to deal with many of these problems, thus necessitating the need for new algorithmic tools. Answering such questions, and more generally identifying the tools for solving such problems, is the focus of this thesis. The exact problems we study in this thesis are the following: (a) the Survivable Network Design problem where the collection of (source,sink) pairs is drawn randomly from a known distribution, (b) the Stochastic Knapsack problem with random sizes/rewards for jobs, (c) the Multi-Armed Bandits problem, where the individual Markov Chains make random transitions, and finally (d) the Stochastic Orienteering problem, where the random tasks/jobs are located at different vertices on a metric. We explore different techniques for solving these problems and present algorithms for all the above problems with near-optimal approximation guarantees. We also believe that the techniques are fairly general and have wider applicability than the context in which they are used in this thesis.