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

Fabio Henrique N. Abe | Zendy; Edna A. Hoshino | Zendy; Alessandro Hill | Zendy; Roberto Baldacci | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Fabio Henrique N. Abe,

Edna A. Hoshino,

Alessandro Hill,

Roberto Baldacci

Publication year - 2019

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2019.08.002

Subject(s) - ring (chemistry) , facility location problem , branch and bound , computer science , algorithm , tree (set theory) , mathematical optimization , mathematics , combinatorics , chemistry , organic chemistry

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research