MIP Modeling of Incremental Connected Facility Location

Ashwin Arulselvan, Andreas Bley, Stefan Gollowitzer, Ivana Ljubic, Olaf Maurer

Research output: Chapter in Book/Report/Conference proceedingChapter

6 Citations (Scopus)


We consider the incremental connected facility location problem, in which we are given a set of potential facilities, a set of interconnection nodes, a set of customers with demands, and a planning horizon. For each time period, we have to select a set of facilities to open, a set of customers to be served, the assignment of these customers to the open facilities, and a network that connects the open facilities. Once a customer is served, it must also be served in subsequent periods. Furthermore, in each time period the total demand of all customers served must be at least equal to a given minimum coverage requirement for that period. The objective is to maximize the net present value of the network, which is given by the discounted revenues of serving the customers and by the discounted investments and maintenance costs for the facilities and the network. We study different MIP models for this problem, discuss some valid inequalities to strengthen these formulations, and present a branch and cut algorithm for finding its solution. Finally, we report (preliminary) computational results of our implementation of this algorithm.
Original languageEnglish
Title of host publicationNetwork Optimization
EditorsJ. Pahl, T. Reiners , S. Voß
Place of PublicationBerlin
Number of pages13
Publication statusPublished - 2011
EventInternational Conference on Network Optimization - INOC2011 - Hamburg, Germany
Duration: 13 Jun 201116 Jun 2011

Publication series

NameLecture Notes in Computer Science


ConferenceInternational Conference on Network Optimization - INOC2011
Abbreviated titleINOC2011


  • facility location
  • valid inequality
  • greedy randomize adaptive search procedure
  • facility location problem
  • Steiner tree problem (STP)


Dive into the research topics of 'MIP Modeling of Incremental Connected Facility Location'. Together they form a unique fingerprint.

Cite this