Browsing by Author "Raghavan, S."

Now showing 1 - 7 of 7
  • Thumbnail Image
    Item
    Bicriteria Product Design Optimization
    (2001) Raghavan, S.; Ball, Michael O.; Trichur, Vinai S.; ISR
    Competitive imperatives are causing manufacturing firms toconsider multiple criteria when designing products. However,current methods to deal with multiple criteria in product designare ad hoc in nature. In this paper we present a systematicprocedure to efficiently solve bicriteria product designoptimization problems.

    We first present a modeling framework, theAND/OR tree, that permits a simplified representation of productdesign optimization problems. We then show how product designoptimization problems on AND/OR trees can be framed as networkdesign problems on a special graph---a directed series-parallelgraph.

    We develop a solution algorithm for the bicriteria problemthat requires as a subroutine the solution of the parametricshortest path problem. Although this problem is hard on generalgraphs, we show that it is polynomially solvable on theseries-parallel graph. As a result we develop an efficientsolution algorithm for the product design optimization problemthat does not require the use of complex and expensivelinear/integer programming solvers.

    As a byproduct of thesolution algorithm, sensitivity analysis for product designoptimization is also efficiently performed under this framework.We illustrate our model and solution algorithm on a complexdesign problem at a FORTUNE 100 company.

  • Thumbnail Image
    Item
    An Evolutionary Approach to the Multi-Level Capacitated Minimum Spanning Tree Problem
    (2002) Gamvros, Ioannis; Raghavan, S.; Golden, Bruce; ISR; CSHCN
    Capacitated network design is a crucial problem to telecommunications network planners. In this paper we consider the Multi-Level Capacitated Minimum Spanning Tree Problem (MLCMST), a generalization of the well-known Capacitated Minimum Spanning Tree Problem. We present a genetic algorithm, based on the notion of grouping, that is quite effective in solving large-scale problems to within 10% of optimality.
  • Thumbnail Image
    Item
    Instances for the Generalized Regenerator Location Problem
    (2015) Chen, Si; Ljubic, Ivana; Raghavan, S.
  • 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
    Low Connectivity Network Design on Series-Parallel Graphs
    (2001) Raghavan, S.; ISR
    Network survivability is a critical issue for modern fiber-optic telecommunication networks. Networks with alternate routes between pairs of nodes permit users to communicate in the face of equipment failure. In this paper, we consider the following low-connectivity network design (LCND) problem. Given a graph G=(N,E) and a connectivity requirement o(i) in (0,1,2) for each node, design a network at minimum cost that contains at least o(st) = min(o(s),o(t)) disjoint paths between nodes s and t. We present linear time algorithms for both node- and edge-connectivity versions of the problem on series-parallel graphs. Due to the sparsity of telecommunications networks this algorithm can be applied to obtain partial solutions and decompositions, that may be embedded in a heuristic solution procedure as well as exact solution algorithms for the problem on general graphs.
  • Thumbnail Image
    Item
    Strong Formulations for Network Design Problems with Connectivity Requirements
    (1999) Magnanti, Thomas L.; Raghavan, S.; ISR
    The network design problem with connectivity requirements (NDC)models a wide variety of celebrated combinatorial optimizationproblems including the minimum spanning tree, Steiner tree, andsurvivable network design problems. We develop strong formulationsfor two versions of the edge-connectivity NDC problem: unitaryproblems requiring connected network designs, and nonunitaryproblems permitting non-connected networks as solutions.

    We(i) present a new directed formulation for the unitary NDC problemthat is stronger than a natural undirected formulation,(ii) project out several classes of valid inequalities---partitioninequalities, odd-hole inequalities, and combinatorial designinequalities---that generalize known classes of valid inequalitiesfor the Steiner tree problem to the unitary NDC problem, and(iii) show how to strengthen and direct nonunitary problems.

    Our results provide a unifying framework forstrengthening formulations for NDC problems, and demonstratethe strength and power of flow-based formulations fornetwork design problems with connectivity requirements.

  • Thumbnail Image
    Item
    Tabu Search for a Network Loading Problem
    (1999) Berger, David; Gendron, Bernard; Potvin, Jean-Yves; Raghavan, S.; Soriano, Patrick; ISR
    This paper examines a network design problem that arises in the telecommunications industry. In this problem, communication between a gateway vertex and a number of demand vertices is achieved through a network of fiber optic cables.

    Since each cable has an associated capacity (bandwidth), enough capacity must be installed on the links of the network to satisfy the demand, using possibly different types of cables. Starting with a network with no capacity or some capacity already installed, a tabu search heuristic is designed to find a solution that minimizes the cost of installing any additional capacity on the network. This tabu search applies a k-shortest path algorithm to find alternative paths from the gateway to the demand vertices. Numerical results are presented on different types of networks with up to 200vertices and 100 demand vertices.