A Branch-and-Price Algorithm for the Ring-Tree Facility Location Problem

Fabio H.N. Abe; Edna A. Hoshino; Alessandro Hill; Roberto Baldacci

doi:10.1016/j.entcs.2019.08.002

A Branch-and-Price Algorithm for the Ring-Tree Facility Location Problem

Fabio H.N. Abe, Edna A. Hoshino, Alessandro Hill, Roberto Baldacci

Research output: Contribution to journal › Conference article › peer-review

2 Citations (Scopus)

Abstract

The ring-tree facility location problem is a generalization of the capacitated ring-tree problem in which additional cost and capacity related to facilities are considered. Applications of this problem arise in the strategic design of bi-level telecommunication networks. We investigate an extended integer programming formulation for the problem and different approaches to deal with the NP-hardness of the pricing problem that appears in a branch-and-price algorithm to solve it. Computational experiments show how heuristics and relaxations improved the performance of a branch-and-price algorithm.

Original language	English
Pages (from-to)	3-14
Number of pages	12
Journal	Electronic Notes in Theoretical Computer Science
Volume	346
DOIs	https://doi.org/10.1016/j.entcs.2019.08.002
Publication status	Published - 2019
Externally published	Yes
Event	10th Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019 - Belo Horizonte, Brazil Duration: 2 Jun 2019 → 7 Jun 2019

Keywords

capacitated ring-tree problem
column generation
integer programming
network design
q-routes

Access to Document

10.1016/j.entcs.2019.08.002

Cite this

@article{b1be3898dd77482197562ba9b9375665,

title = "A Branch-and-Price Algorithm for the Ring-Tree Facility Location Problem",

abstract = "The ring-tree facility location problem is a generalization of the capacitated ring-tree problem in which additional cost and capacity related to facilities are considered. Applications of this problem arise in the strategic design of bi-level telecommunication networks. We investigate an extended integer programming formulation for the problem and different approaches to deal with the NP-hardness of the pricing problem that appears in a branch-and-price algorithm to solve it. Computational experiments show how heuristics and relaxations improved the performance of a branch-and-price algorithm.",

keywords = "capacitated ring-tree problem, column generation, integer programming, network design, q-routes",

author = "Abe, {Fabio H.N.} and Hoshino, {Edna A.} and Alessandro Hill and Roberto Baldacci",

note = "Publisher Copyright: {\textcopyright} 2019 The Author(s).; 10th Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019 ; Conference date: 02-06-2019 Through 07-06-2019",

year = "2019",

doi = "10.1016/j.entcs.2019.08.002",

language = "English",

volume = "346",

pages = "3--14",

journal = "Electronic Notes in Theoretical Computer Science",

issn = "1571-0661",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A Branch-and-Price Algorithm for the Ring-Tree Facility Location Problem

AU - Abe, Fabio H.N.

AU - Hoshino, Edna A.

AU - Hill, Alessandro

AU - Baldacci, Roberto

PY - 2019

Y1 - 2019

N2 - The ring-tree facility location problem is a generalization of the capacitated ring-tree problem in which additional cost and capacity related to facilities are considered. Applications of this problem arise in the strategic design of bi-level telecommunication networks. We investigate an extended integer programming formulation for the problem and different approaches to deal with the NP-hardness of the pricing problem that appears in a branch-and-price algorithm to solve it. Computational experiments show how heuristics and relaxations improved the performance of a branch-and-price algorithm.

AB - The ring-tree facility location problem is a generalization of the capacitated ring-tree problem in which additional cost and capacity related to facilities are considered. Applications of this problem arise in the strategic design of bi-level telecommunication networks. We investigate an extended integer programming formulation for the problem and different approaches to deal with the NP-hardness of the pricing problem that appears in a branch-and-price algorithm to solve it. Computational experiments show how heuristics and relaxations improved the performance of a branch-and-price algorithm.

KW - capacitated ring-tree problem

KW - column generation

KW - integer programming

KW - network design

KW - q-routes

UR - http://www.scopus.com/inward/record.url?scp=85076257907&partnerID=8YFLogxK

U2 - 10.1016/j.entcs.2019.08.002

DO - 10.1016/j.entcs.2019.08.002

M3 - Conference article

AN - SCOPUS:85076257907

SN - 1571-0661

VL - 346

SP - 3

EP - 14

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

T2 - 10th Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019

Y2 - 2 June 2019 through 7 June 2019

ER -

A Branch-and-Price Algorithm for the Ring-Tree Facility Location Problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this