Optimization Online


Exact algorithms for bi-objective ring tree problems with reliability measures

Alessandro Hill (alessandro.hill***at***uai.cl)
Silvia Schwarze (silvia.schwarze***at***uni-hamburg.de)

Abstract: We introduce bi-objective models for ring tree network design with a focus on network reliability within telecommunication applications. Our approaches generalize the capacitated ring tree problem (CRTP) which asks for a partially reliable topology that connects customers with different security requirements to a depot node by combined ring and tree graphs. While the CRTP aims at optimizing the edge installation costs, we propose four alternative, reliability-oriented objective functions. To that end, we consider network breakdown due to single-edge failures and incorporate the overall number of tree customers and tree edges, the maximal number of subtree customers and the maximal number of tree hops from rings as additional measures. We develop mathematical multi-commodity flow formulations for the corresponding bi-objective problems and identify relationships between the new objectives. For identifying the Pareto fronts, we apply an epsilon-constraint method based on integer programming. To increase the computational efficiency, we employ local search heuristics in order to tighten upper bounds and elaborate valid inequalities to strengthen lower bounds in the subproblems. In a computational study we report results, illustrate solution network topologies and extensively analyze the algorithm performance for instances from the literature.

Keywords: capacitated ring tree problem, bi-objective optimization, Steiner tree, reliable network design, mathematical programming, telecommunications

Category 1: Network Optimization

Category 2: Other Topics (Multi-Criteria Optimization )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 08/15/2016
Entry Accepted: 09/01/2016
Entry Last Modified: 02/22/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society