network design

STRONG LOWER BOUNDS FOR THE PRIZE COLLECTING STEINER PROBLEM IN GRAPHS

  • Abílio Lucena
  • Mauricio G.C. Resende
    • Categories Combinatorial Optimization, Network Optimization, Telecommunications Tags , , ,

    Given an undirected graph G with nonnegative edges costs and nonnegative vertex penalties, the prize collecting Steiner problem in graphs (PCSPG) seeks a tree of G with minimum weight. The weight of a tree is the sum of its edge costs plus the sum of the penalties of those vertices not spanned by the tree. … Read more

    Hierarchical Network Design Using Simulated Annealing

  • Jens Clausen
  • Tommy Thomadsen
    • Categories Meta Heuristics, Network Optimization, Telecommunications Tags ,

    The hierarchical network problem is the problem of finding the least cost network, with nodes divided into groups, edges connecting nodes in each groups and groups ordered in a hierarchy. The idea of hierarchical networks comes from telecommunication networks where hierarchies exist. Hierarchical networks are described and a mathematical model is proposed for a two … Read more

    Two-connected networks with rings of bounded cardinality

  • Bernard Fortz
  • Martine Labbé
    • Categories Branch and Cut Algorithms, Telecommunications Tags ,

    We study the problem of designing at minimum cost a two-connected network such that each edge belongs to a cycle using at most K edges. This problem is a particular case of the two-connected networks with bounded meshes problem studied by Fortz, Labbé and Maffioli. In this paper, we compute a lower bound on the … Read more

    Mesh Topology Design in Overlay Virtual Private Networks

  • Nail Akar
  • Oya Ekin Karasan
  • Mustafa C. Pinar
  • Ezhan Karasan
    • Categories 0-1 Programming, Network Optimization, Telecommunications Tags , , ,

    We study the mesh topology design problem in overlay virtual private networks. Given a set of customer nodes and associated traffic matrix, tunnels that are connecting node pairs through a public service provider network subject to degree constraints are determined so as to minimize total multihopped traffic. Valid inequalities strengthening the LP relaxation and a … Read more

    Polyhedral results for two-connected networks with bounded rings

  • Bernard Fortz
  • Martine Labbé
    • Categories Branch and Cut Algorithms, Polyhedra, Telecommunications Tags ,

    We study the polyhedron associated with a network design problem which consists in determining at minimum cost a two-connected network such that the shortest cycle to which each edge belongs (a “ring”) does not exceed a given length K. We present here a new formulation of the problem and derive facet results for different classes … Read more

    Branch-and-cut for the k-way equipartition problem

  • John E. Mitchell
    • Categories Cutting Plane Approaches, Polyhedra Tags , , , ,

    We investigate the polyhedral structure of a formulation of the k-way equipartition problem and a branch-and-cut algorithm for the problem. The k-way equipartition problem requires dividing the vertices of a weighted graph into k equally sized sets, so as to minimize the total weight of edges that have both endpoints in the same set. Applications … Read more