Branch-and-Cut-and-Price for Capacitated Connected Facility Location

Markus Leitner*, Günther R. Raidl

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We consider a generalization of the Connected Facility Location Problem (ConFL), suitable to model real world network extension scenarios such as fiber-to-the-curb. In addition to choosing a set of facilities and connecting them by a Steiner tree as in ConFL, we aim to maximize the resulting profit by potentially supplying only a subset of all customers. Furthermore, capacity constraints on potential facilities need to be considered. We present two mixed integer programming based approaches which are solved using branch-and-cut and branch-and-cut-and-price, respectively. By studying the corresponding polyhedra we analyze both approaches theoretically and show their advantages over previously presented models. Furthermore, using a computational study we are able to additionally show significant advantages of our models over previously presented ones from a practical point of view.

Original languageEnglish
Pages (from-to)245-267
Number of pages23
JournalJournal of Mathematical Modelling and Algorithms
Volume10
Issue number3
DOIs
Publication statusPublished - 1 Sep 2011
Externally publishedYes

Keywords

  • Branch-and-cut
  • Branch-and-cut-and-price
  • Connected facility location
  • Mixed integer programming
  • Network design

Fingerprint Dive into the research topics of 'Branch-and-Cut-and-Price for Capacitated Connected Facility Location'. Together they form a unique fingerprint.

Cite this