Home > Research > Publications & Outputs > A branch-and-cut algorithm for two-level surviv...

Research

Links

Text available via DOI:

Keywords

View graph of relations

A branch-and-cut algorithm for two-level survivable network design problems

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

A branch-and-cut algorithm for two-level survivable network design problems. / Rodriguez-Martin, Inmaculada; Salazar-Gonzalez, Juan-Jose; Yaman, Hande.
In: Computers and Operations Research, Vol. 67, 03.2016, p. 102-112.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Rodriguez-Martin, I, Salazar-Gonzalez, J-J & Yaman, H 2016, 'A branch-and-cut algorithm for two-level survivable network design problems', Computers and Operations Research, vol. 67, pp. 102-112. https://doi.org/10.1016/j.cor.2015.09.008

APA

Rodriguez-Martin, I., Salazar-Gonzalez, J-J., & Yaman, H. (2016). A branch-and-cut algorithm for two-level survivable network design problems. Computers and Operations Research, 67, 102-112. https://doi.org/10.1016/j.cor.2015.09.008

Vancouver

Rodriguez-Martin I, Salazar-Gonzalez J-J, Yaman H. A branch-and-cut algorithm for two-level survivable network design problems. Computers and Operations Research. 2016 Mar;67:102-112. Epub 2015 Sept 28. doi: 10.1016/j.cor.2015.09.008

Author

Rodriguez-Martin, Inmaculada ; Salazar-Gonzalez, Juan-Jose ; Yaman, Hande. / A branch-and-cut algorithm for two-level survivable network design problems. In: Computers and Operations Research. 2016 ; Vol. 67. pp. 102-112.

Bibtex

@article{20e6a5392b9b4285a471e736bf101e7c,
title = "A branch-and-cut algorithm for two-level survivable network design problems",
abstract = "This paper approaches the problem of designing a two-level network protected against single-edge failures. The problem simultaneously decides on the partition of the set of nodes into terminals and hubs, the connection of the hubs through a backbone network (first network level), and the assignment of terminals to hubs and their connection through access networks (second network level). We consider two survivable structures in both network levels. One structure is a two-edge connected network, and the other structure is a ring. There is a limit on the number of nodes in each access network, and there are fixed costs associated with the hubs and the access and backbone links. The aim of the problem is to minimize the total cost. We give integer programming formulations and valid inequalities for the different versions of the problem, solve them using a branch-and-cut algorithm, and discuss computational results. Some of the new inequalities can be used also to solve other problems in the literature, like the plant cycle location problem and the hub location routing problem. (C) 2015 Elsevier Ltd. All rights reserved.",
keywords = "Network design, Survivability, Hierarchical networks, Valid inequalities, Branch-and-cut, TELECOMMUNICATIONS NETWORKS, LOCATION, RINGS, REQUIREMENTS, SUBGRAPHS, POLYHEDRA",
author = "Inmaculada Rodriguez-Martin and Juan-Jose Salazar-Gonzalez and Hande Yaman",
year = "2016",
month = mar,
doi = "10.1016/j.cor.2015.09.008",
language = "English",
volume = "67",
pages = "102--112",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Ltd",

}

RIS

TY - JOUR

T1 - A branch-and-cut algorithm for two-level survivable network design problems

AU - Rodriguez-Martin, Inmaculada

AU - Salazar-Gonzalez, Juan-Jose

AU - Yaman, Hande

PY - 2016/3

Y1 - 2016/3

N2 - This paper approaches the problem of designing a two-level network protected against single-edge failures. The problem simultaneously decides on the partition of the set of nodes into terminals and hubs, the connection of the hubs through a backbone network (first network level), and the assignment of terminals to hubs and their connection through access networks (second network level). We consider two survivable structures in both network levels. One structure is a two-edge connected network, and the other structure is a ring. There is a limit on the number of nodes in each access network, and there are fixed costs associated with the hubs and the access and backbone links. The aim of the problem is to minimize the total cost. We give integer programming formulations and valid inequalities for the different versions of the problem, solve them using a branch-and-cut algorithm, and discuss computational results. Some of the new inequalities can be used also to solve other problems in the literature, like the plant cycle location problem and the hub location routing problem. (C) 2015 Elsevier Ltd. All rights reserved.

AB - This paper approaches the problem of designing a two-level network protected against single-edge failures. The problem simultaneously decides on the partition of the set of nodes into terminals and hubs, the connection of the hubs through a backbone network (first network level), and the assignment of terminals to hubs and their connection through access networks (second network level). We consider two survivable structures in both network levels. One structure is a two-edge connected network, and the other structure is a ring. There is a limit on the number of nodes in each access network, and there are fixed costs associated with the hubs and the access and backbone links. The aim of the problem is to minimize the total cost. We give integer programming formulations and valid inequalities for the different versions of the problem, solve them using a branch-and-cut algorithm, and discuss computational results. Some of the new inequalities can be used also to solve other problems in the literature, like the plant cycle location problem and the hub location routing problem. (C) 2015 Elsevier Ltd. All rights reserved.

KW - Network design

KW - Survivability

KW - Hierarchical networks

KW - Valid inequalities

KW - Branch-and-cut

KW - TELECOMMUNICATIONS NETWORKS

KW - LOCATION

KW - RINGS

KW - REQUIREMENTS

KW - SUBGRAPHS

KW - POLYHEDRA

U2 - 10.1016/j.cor.2015.09.008

DO - 10.1016/j.cor.2015.09.008

M3 - Journal article

VL - 67

SP - 102

EP - 112

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -