Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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

Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03641690
Contributor : Cristian Durán-Mateluna Connect in order to contact the contributor
Submitted on : Friday, April 22, 2022 - 10:08:36 AM
Last modification on : Wednesday, May 11, 2022 - 12:06:06 PM

Files

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03641690, version 1

Citation

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

Share

Metrics

Record views

25

Files downloads

18