The generalized minimum edge-biconnected network problem: ef.cient neighborhood structures for variable neighborhood search

Bin Hu*, Markus Leitner, Günther R. Raidl

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We consider the generalized minimum edge-biconnected network problem where the nodes of a graph are partitioned into clusters and exactly one node from each cluster is required to be connected in an edge-biconnected way. Instances of this problem appear, for example, in the design of survivable backbone networks. We present different variants of a variable neighborhood search approach that utilize different types of neighborhood structures, each of them addressing particular properties as spanned nodes and/or the edges between them. For themorecomplex neighborhood structures,weapply efficient techniques-such as a graph reduction-to essentially speedupthe search process. For comparison purposes, we use a mixed integer linear programming formulation based on multi-commodity flows to solve smaller instances of this problem to proven optimality. Experiments on such instances indicate that the variable neighborhood search is also able to identify optimal solutions in the majority of test runs, but within substantially less time. Tests on larger Euclidean and random instances with up to 1,280 nodes, which could not be solved to optimality by mixed integer programming, further document the efficiency of the variable neighborhood search. In particular, all proposed neighborhood structures are shown to contribute significantly to the search process.

Original languageEnglish
Pages (from-to)256-275
Number of pages20
JournalNetworks
Volume55
Issue number3
DOIs
Publication statusPublished - 1 May 2010
Externally publishedYes

Keywords

  • Biconnectivity
  • Mixed integer programming
  • Network design
  • Variable neighborhood search

Fingerprint

Dive into the research topics of 'The generalized minimum edge-biconnected network problem: ef.cient neighborhood structures for variable neighborhood search'. Together they form a unique fingerprint.

Cite this