A cutting plane algorithm for the Capacitated Connected Facility Location Problem

Stefan Gollowitzer (), Bernard Gendron () and Ivana Ljubić ()

Computational Optimization and Applications, 2013, vol. 55, issue 3, 647-674

Abstract: We consider a network design problem that arises in the cost-optimal design of last mile telecommunication networks. It extends the Connected Facility Location problem by introducing capacities on the facilities and links of the networks. It combines aspects of the capacitated network design problem and the single-source capacitated facility location problem. We refer to it as the Capacitated Connected Facility Location Problem. We develop a basic integer programming model based on single-commodity flows. Based on valid inequalities for the capacitated network design problem and the single-source capacitated facility location problem we derive several (new) classes of valid inequalities for the Capacitated Connected Facility Location Problem including cut set inequalities, cover inequalities and combinations thereof. We use them in a branch-and-cut framework and show their applicability and efficacy on a set of real-world instances. Copyright Springer Science+Business Media New York 2013

Keywords: Capacitated network design; Facility Location; Connected Facility Location; Mixed integer programming models; Telecommunications (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-013-9544-9 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:55:y:2013:i:3:p:647-674

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-013-9544-9

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().