The first part of this thesis comprises the first theoretical and computational study on mixed integer programming (MIP) models for the connected facility location problem (ConFL). ConFL combines facility location and Steiner trees: Given a set of customers, a set of potential facility locations and some inter-connection nodes, ConFL searches for the minimum-cost way of assigning each customer to exactly one open facility, and connecting the open facilities via a Steiner tree. The costs needed for building the Steiner tree, facility opening costs and the assignment costs need to be minimized.<br />We model ConFL using eight compact and two exponential mixed integer programming formulations. We also show how to transform ConFL into the Steiner arborescence problem. A full hierarchy between the models is provided. An extensive computational study is based on two benchmark sets of randomly generated instances with up to 1,300 nodes and 115,000 edges.<br />We empirically compare the presented models for ConFL with respect to the quality of obtained bounds and the corresponding running time. We report optimal values for all but 16 instances for which the obtained gaps are below 0.6\%.<br />In the second part of this work we extend the definition of ConFL to model reliability constraints of the end-user's connections. We develop 15 mixed integer programming models for this problem. Some of these models are extensions from corresponding models for the ConFL, some extend ideas for related problems like the Minimum Spanning or Steiner Tree problem with hop constraints. We provide a hierarchy of the proposed models by comparing the relative quality of the corresponding linear programming lower bounds. We also show how the Hop Constrained ConFL can be modelled as ConFL or Steiner Tree problem on a layered graph.<br />
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Facility Location
de
dc.subject
Steiner Trees
de
dc.subject
Hop constrained Steiner trees
de
dc.subject
Connected Facility Location
de
dc.subject
Mixed Integer Programming Models
de
dc.subject
LP-relaxations
de
dc.title
MIP models for (hop-constrained) connected facility location
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Stefan Gollowitzer
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen