TY - JOUR
T1 - The generalized minimum edge-biconnected network problem
T2 - ef.cient neighborhood structures for variable neighborhood search
AU - Hu, Bin
AU - Leitner, Markus
AU - Raidl, Günther R.
PY - 2010/5/1
Y1 - 2010/5/1
N2 - 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.
AB - 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.
KW - Biconnectivity
KW - Mixed integer programming
KW - Network design
KW - Variable neighborhood search
UR - http://www.scopus.com/inward/record.url?scp=77951219397&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77951219397&partnerID=8YFLogxK
U2 - 10.1002/net.20370
DO - 10.1002/net.20370
M3 - Article
AN - SCOPUS:77951219397
SN - 0028-3045
VL - 55
SP - 256
EP - 275
JO - Networks
JF - Networks
IS - 3
ER -