|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||Abstract:||
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.
|Library ID:||AC07806350||Organisation:||E186 - Institut für Computergraphik und Algorithmen||Publication Type:||Thesis
|Appears in Collections:||Thesis|
Show full item record
Files in this item:
|MIP models for hop-constrained connected facility location.pdf||667.91 kB||Adobe PDF|
checked on Feb 18, 2021
checked on Feb 18, 2021
Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.