Çokyüzlü trafik belirsizliği durumunda gürbüz ağ tasarımı

In this thesis, we study the design of networks robust to changes in demand estimates. We consider the case where the set of feasible demands is de¯ned by an arbitrary polyhedron. Our motivation is to determine link capacity or rout- ing con¯gurations, which remain feasible for any realization in the corresponding demand polyhedron. We consider three well-known problems under polyhedral demand uncertainty all of which are posed as semi-in¯nite mixed integer program- ming problems. We develop explicit, compact formulations for all three problems as well as alternative formulations and exact solution methods. The ¯rst problem arises in the Virtual Private Network (VPN) design ¯eld. We present compact linear mixed-integer programming formulations for the prob- lem with the classical hose tra±c model and for a new, less conservative, robust variant relying on accessible tra±c statistics. Although we can solve these formu- lations for medium-to-large instances in reasonable times using o®-the-shelf MIP solvers, we develop a combined branch-and-price and cutting plane algorithm to handle larger instances. We also provide an extensive discussion of our numerical results. Next, we study the Open Shortest Path First (OSPF) routing enhanced with tra±c engineering tools under general demand uncertainty with the motivation to discuss if OSPF could be made comparable to the general unconstrained routing (MPLS) when it is provided with a less restrictive operating environment. To the best of our knowledge, these two routing mechanisms are compared for the ¯rst time under such a general setting. We provide compact formulations for both routing types and show that MPLS routing for polyhedral demands can be computed in polynomial time. Moreover, we present a specialized branch- and-price algorithm strengthened with the inclusion of cuts as an exact solution iv tool. Subsequently, we compare the new and more °exible OSPF routing with MPLS as well as the traditional OSPF on several network instances. We observe that the management tools we use in OSPF make it signi¯cantly better than the generic OSPF. Moreover, we show that OSPF performance can get closer to that of MPLS in some cases. Finally, we consider the Network Loading Problem (NLP) under a polyhe- dral uncertainty description of tra±c demands. After giving a compact multi- commodity formulation of the problem, we prove an unexpected decomposition property obtained from projecting out the °ow variables, considerably simplifying the resulting polyhedral analysis and computations by doing away with metric in- equalities, an attendant feature of most successful algorithms on NLP. Under the hose model of feasible demands, we study the polyhedral aspects of NLP, used as the basis of an e±cient branch-and-cut algorithm supported by a simple heuristic for generating upper bounds. We provide the results of extensive computational experiments on well-known network design instances. Keywords: Robust network design, polyhedral tra±c uncertainty, Virtual Pri- vate Network, Open Shortest Path First, Network Loading Problem, Branch- and-Price. v