The incremental connected facility location problem

Ashwin Arulselvan, Andreas Bley, Ivana Ljubić

Research output: Contribution to journalArticle

Abstract

We consider the incremental connected facility location problem (incremental ConFL), 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 remain 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 minimize the total cost for building the network given by the investment and maintenance costs for the facilities and the network summed up over all time periods. We propose a mixed integer programming approach in which, in each time period, a single period ConFL with coverage restrictions has to be solved. For this latter problem, which is of particular interest in itself, new families of valid inequalities are proposed: these are set union knapsack cover (SUKC) inequalities, which are further enhanced by lifting and/or combined with cut-set inequalities, which are primarily used to ensure connectivity requirements. Details of an efficient branch-and-cut implementation are presented and computational results on a benchmark set of large instances are given, including examples of telecommunication networks in Germany
LanguageEnglish
Number of pages34
JournalComputers & Operations Research
Publication statusAccepted/In press - 30 Jul 2019

Fingerprint

Facility Location Problem
Customers
Coverage
Integer programming
Branch-and-cut
Telecommunication Network
Valid Inequalities
Cutset
Knapsack
Mixed Integer Programming
Requirements
Costs
Telecommunication networks
Incremental
Location problem
Facility location
Interconnection
Computational Results
Horizon
Maintenance

Keywords

  • mixed integer programming
  • incremental network design
  • multi-period network design
  • branch-and-cut
  • facility location

Cite this

@article{e970cb19142f4fdbbe52d0c94359de86,
title = "The incremental connected facility location problem",
abstract = "We consider the incremental connected facility location problem (incremental ConFL), 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 remain 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 minimize the total cost for building the network given by the investment and maintenance costs for the facilities and the network summed up over all time periods. We propose a mixed integer programming approach in which, in each time period, a single period ConFL with coverage restrictions has to be solved. For this latter problem, which is of particular interest in itself, new families of valid inequalities are proposed: these are set union knapsack cover (SUKC) inequalities, which are further enhanced by lifting and/or combined with cut-set inequalities, which are primarily used to ensure connectivity requirements. Details of an efficient branch-and-cut implementation are presented and computational results on a benchmark set of large instances are given, including examples of telecommunication networks in Germany",
keywords = "mixed integer programming, incremental network design, multi-period network design, branch-and-cut, facility location",
author = "Ashwin Arulselvan and Andreas Bley and Ivana Ljubić",
year = "2019",
month = "7",
day = "30",
language = "English",
journal = "Computers & Operations Research",
issn = "0305-0548",

}

The incremental connected facility location problem. / Arulselvan, Ashwin; Bley, Andreas; Ljubić, Ivana.

In: Computers & Operations Research, 30.07.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The incremental connected facility location problem

AU - Arulselvan, Ashwin

AU - Bley, Andreas

AU - Ljubić, Ivana

PY - 2019/7/30

Y1 - 2019/7/30

N2 - We consider the incremental connected facility location problem (incremental ConFL), 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 remain 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 minimize the total cost for building the network given by the investment and maintenance costs for the facilities and the network summed up over all time periods. We propose a mixed integer programming approach in which, in each time period, a single period ConFL with coverage restrictions has to be solved. For this latter problem, which is of particular interest in itself, new families of valid inequalities are proposed: these are set union knapsack cover (SUKC) inequalities, which are further enhanced by lifting and/or combined with cut-set inequalities, which are primarily used to ensure connectivity requirements. Details of an efficient branch-and-cut implementation are presented and computational results on a benchmark set of large instances are given, including examples of telecommunication networks in Germany

AB - We consider the incremental connected facility location problem (incremental ConFL), 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 remain 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 minimize the total cost for building the network given by the investment and maintenance costs for the facilities and the network summed up over all time periods. We propose a mixed integer programming approach in which, in each time period, a single period ConFL with coverage restrictions has to be solved. For this latter problem, which is of particular interest in itself, new families of valid inequalities are proposed: these are set union knapsack cover (SUKC) inequalities, which are further enhanced by lifting and/or combined with cut-set inequalities, which are primarily used to ensure connectivity requirements. Details of an efficient branch-and-cut implementation are presented and computational results on a benchmark set of large instances are given, including examples of telecommunication networks in Germany

KW - mixed integer programming

KW - incremental network design

KW - multi-period network design

KW - branch-and-cut

KW - facility location

UR - https://www.sciencedirect.com/journal/computers-and-operations-research

M3 - Article

JO - Computers & Operations Research

T2 - Computers & Operations Research

JF - Computers & Operations Research

SN - 0305-0548

ER -