MILP formulations for continuous set-covering on networks
Xu Liding  1@  , Mercedes Pelegrín  2@  
1 : Laboratoire dínformatique de l\'École polytechnique [Palaiseau]
Centre National de la Recherche Scientifique, Ecole Polytechnique, Centre National de la Recherche Scientifique : UMR7161
2 : Laboratoire d'informatique de l'école polytechnique
CNRS : UMR7161, Polytechnique - X

Covering problems are well-studied in the domain of Location Science. When the location space is a network, the most frequent assumption is to consider the candidate facility locations, the points to be covered, or both, to be finite sets. In this work, we study the set-covering location problem when both candidate locations and demand points are continuous on a network. This variant generalizes several problems, including set-covering, and uncapacitated facility location problems. However, this problem has received little attention, and the scarce existing approaches have focused on particular cases, such as tree networks and integer covering radius. Here we study the general problem through an integer programming approach, and propose two MILP formulations for the problem with several reduction techniques. We implement the existing and new MILP formulations in JuMP modeling language. Our computational experiments show the strengths and limitations of our exact approach to both real-world and random networks. Our formulations are also tested against an existing exact method.


Personnes connectées : 163 Vie privée
Chargement...