  


The Connected Facility Location Polytope: Valid Inequalities, Facets and a Computational Study
Markus Leitner(markus.leitnerunivie.ac.at) Abstract: Connected facility location is a problem that combines the Steiner tree problem with uncapacitated facility location. Given a set of customers, a set of potential facility locations and some intermediate nodes, decide which facilities to open, so that each customer is assigned to an open facility and the open facilities are connected through a Steiner tree. The goal is to find a solution that minimizes the sum of the assignment cost, the facility opening cost and the cost of the Steiner tree. This work is a first study on a polytope associated with the connected facility location problem. Facetinducing inequalities are derived and polynomialtime separation algorithms for some of these inequalities are provided. A computational study that complements the obtained theoretical results is also done. Keywords: valid inequalities, facets, separation algorithms, branchandcut, facility location, Steiner trees Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Combinatorial Optimization (Polyhedra ) Category 3: Network Optimization Citation: Download: [PDF] Entry Submitted: 04/09/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  