Title: MIP models for (hop-constrained) connected facility location
Language: English
Authors: Gollowitzer, Stefan 
Qualification level: Diploma
Keywords: Facility Location; Steiner Trees; Hop constrained Steiner trees; Connected Facility Location; Mixed Integer Programming Models; LP-relaxations
Advisor: Ljubic, Ivana
Issue Date: 2010
Number of Pages: 52
Qualification level: Diploma
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.
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.
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\%.
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.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-34363
Library ID: AC07806350
Organisation: E186 - Institut für Computergraphik und Algorithmen 
Publication Type: Thesis
Appears in Collections:Thesis

Files in this item:

File Description SizeFormat
MIP models for hop-constrained connected facility location.pdf667.91 kBAdobe PDFThumbnail
Show full item record

Page view(s)

checked on Feb 18, 2021


checked on Feb 18, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.