Optimization Online


The Connected Facility Location Polytope: Valid Inequalities, Facets and a Computational Study

Markus Leitner(markus.leitner***at***univie.ac.at)
Ivana Ljubic(ivana.ljubic***at***univie.ac.at)
Juan-Jose Salazar-Gonzalez(jjsalaza***at***ull.es)
Markus Sinnl(markus.sinnl***at***univie.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. Facet-inducing inequalities are derived and polynomial-time 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, branch-and-cut, facility location, Steiner trees

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Network Optimization


Download: [PDF]

Entry Submitted: 04/09/2014
Entry Accepted: 04/09/2014
Entry Last Modified: 04/09/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society