MILP formulations for continuous set-covering on networks

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. slides

This talk is presented at session 24ème édition du congrès annuel de la Société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF2023).