Robust MILP formulations for the two-stage weighted vertex p-center problem - ENSTA Paris - École nationale supérieure de techniques avancées Paris Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2022

Robust MILP formulations for the two-stage weighted vertex p-center problem

Résumé

The weighted vertex p-center problem (PCP) consists of locating p facilities among a set of potential sites such that the maximum weighted distance from any client to its closest open facility is minimized. This paper studies the exact resolution of the two-stage robust weighted vertex p-center problem (RPCP2). In this problem, the opening of the centers is fixed in the first stage while the client allocations are recourse decisions fixed once the uncertainty is revealed. The problem uncertainty comes from both the nodal demands and the edge lengths. It is modeled by box uncertainty sets. We introduce three different robust reformulations based on MILPs from the literature. We prove that considering a finite subset of scenarios is sufficient to obtain an optimal solution of (RPCP2). We leverage this result to introduce a column-and-constraint generation algorithm and a branch-and-cut algorithm to efficiently solve this problem optimally. We highlight how these algorithms can be adapted to solve, for the first time to optimality, the single-stage problem (RPCP1) which is obtained when no recourse is considered. We present a numerical study to compare the performance of these formulations on randomly generated instances and a case study from the literature.
Fichier principal
Vignette du fichier
main.pdf (260.32 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03641690 , version 1 (22-04-2022)

Identifiants

  • HAL Id : hal-03641690 , version 1

Citer

Cristian Durán Mateluna, Zacharie Alès, Natalia Jorquera-Bravo, Sourour Elloumi. Robust MILP formulations for the two-stage weighted vertex p-center problem. 2022. ⟨hal-03641690⟩
119 Consultations
86 Téléchargements

Partager

Gmail Facebook X LinkedIn More