Decision, Operations & Information Technologies

Permanent URI for this communityhttp://hdl.handle.net/1903/2230

Prior to January 4, 2009, this unit was named Decision & Information Technologies.

Browse

Subject: search.filters.subject.network design

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Instances for the Recoverable Robust Two-Level Network Design Problem
    (2014) Alvarez-Miranda, Eduardo; Ljubic, Ivana; Raghavan, S.; Toth, Paolo
    We provide the instances used in the paper "The Recoverable Robust Two-Level Network Design Problem", by E. Alvarez-Miranda, I. Ljubic, S. Raghavan and P. Toth, accepted for publication in the INFORMS J. on Computing, 2014 (http://dx.doi.org/10.1287/ijoc.2014.0606). This repository contains both the instances used in the paper as well as the results obtained by the proposed algorithm.
  • Thumbnail Image
    Item
    Dual-Based Local Search for Deterministic, Stochastic and Robust Variants of the Connected Facility Location Problem
    (2011) Bardossy, Maria G.; Raghavan, Subramanian; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    In this dissertation, we propose the study of a family of network design problems that arise in a wide range of practical settings ranging from telecommunications to data management. We investigate the use of heuristic search procedures coupled with lower bounding mechanisms to obtain high quality solutions for deterministic, stochastic and robust variants of these problems. We extend the use of well-known methods such as the sample average approximation for stochastic optimization and the Bertsimas and Sim approach for robust optimization with heuristics and lower bounding mechanisms. This is particular important for NP-complete problems where even deterministic and small instances are difficult to solve to optimality. Our extensions provide a novel way of applying these techniques while using heuristics; which from a practical perspective increases their usefulness.
  • Thumbnail Image
    Item
    Optimization of Contemporary Telecommunications Networks: Generalized Spanning Trees and WDM Optical Networks
    (2005-12-05) Stanojevic, Daliborka; Raghavan, Subramanian; Decision and Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    We present a study of two NP-hard telecommunications network design problems - the prize-collecting generalized minimum spanning tree problem (PCGMST) and the design of optical networks with wavelength division multiplexing. The first problem, the PCGMST problem, involves the design of regional backbone networks, where a set of local area networks (LANs) need to be connected by a minimum cost tree network using exactly one gateway site from each LAN. We present several polynomial time heuristics for the PCGMST problem and show that these algorithms, at best, provide only modest quality solutions. We also present two metaheuristics - a local search procedure and a genetic algorithm, and show that these procedures provide compelling high-quality results on a large set of test problems. Our study of the PCGMST problem is concluded by a presentation of two exact solution procedures that can be used to find optimal solutions in networks of moderate size. The second problem studied in this dissertation is a more complex network design problem that involves optical networks with wavelength division multiplexing (WDM). These networks provide an abundance of transmission bandwidth, but require the use of expensive equipment, which, in turn, mandates careful use of the resources available for their design. The novel aspect of WDM optical networks is that they require simultaneous design of two network layers. The first layer is the virtual topology that requires routing of logical paths over the physical layer of optical fibers. The second layer involves routing and grooming of traffic requests over the logical paths established in the virtual topology. This problem has been extensively studied in the last 10 years, but due to its notoriously hard nature, only few exact solution procedures for relaxed versions of this problem were developed so far. We propose one exact and two approximate branch-and-price algorithms for two versions of the WDM optical network design problem and present results of the computational study involving two different design objectives. Finally, we propose two classes of valid inequalities for our branch-and-price algorithms, and discuss applicability of our algorithms to different versions of the WDM optical network design problem.