Premium
Exactly solving a two‐level location problem with modular node capacities
Author(s) -
Addis Bernardetta,
Carello Giuliana,
Ceselli Alberto
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20486
Subject(s) - dimensioning , computer science , facility location problem , modular design , node (physics) , set (abstract data type) , mathematical optimization , discretization , network planning and design , network topology , distributed computing , topology (electrical circuits) , operations research , computer network , mathematics , engineering , mathematical analysis , structural engineering , combinatorics , programming language , aerospace engineering , operating system
Abstract In many telecommunication networks, a given set of client nodes must be served by different sets of facilities—providing different services and having different capabilities—which must be located and dimensioned in the design phase. Network topology must be designed as well, by assigning clients to facilities and facilities to higher level entities, when necessary. We tackle a particular location problem, where two sets of facilities have to be located, and in which different devices can be installed at each site, providing different capacities at different costs. We optimize location and dimensioning of these facilities simultaneously. We introduce a compact formulation of that problem, we use discretization and Dantzig–Wolfe reformulation techniques to improve models, and we design an exact optimization algorithm. We test our approach on a set of instances derived from existing literature on facility location. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012