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 language | English |
---|---|
Pages (from-to) | 245-267 |
Number of pages | 23 |
Journal | Journal of Mathematical Modelling and Algorithms |
Volume | 10 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1 Sept 2011 |
Externally published | Yes |
Funding
This work is supported by the Austrian Science Fund (FWF) under contract P20342-N13
Keywords
- Branch-and-cut
- Branch-and-cut-and-price
- Connected facility location
- Mixed integer programming
- Network design