In this paper, we introduce a mixed integer quadratic formulation for the congested variant of the partial set covering location problem, which involves determining a subset of facility locations to open and efficiently allocating customers to these facilities to minimize the combined costs of facility opening and congestion while ensuring target coverage. To enhance the resilience of the solution against demand fluctuations, we address the case under uncertain customer demand using Γ-robustness. We formulate the deterministic problem and its robust counterpart as mixed-integer quadratic problems. We investigate the effect of the protection level in adapted instances from the literature to provide critical insights into how sensitive the planning is to the protection level. Moreover, since the size of the robust counterpart grows with the number of customers, which could be significant in real-world contexts, we propose the use of Benders decomposition to effectively reduce the number of variables by projecting out of the master problem all the variables dependent on the number of customers. We illustrate how to incorporate our Benders approach within a mixed-integer second-order cone programming (MISOCP) solver, addressing explicitly all the ingredients that are instrumental for its success. We discuss single-tree and multi-tree approaches and introduce a perturbation technique to deal with the degeneracy of the Benders subproblem efficiently. Our tailored Benders approaches outperform the perspective reformulation solved using the state-of-the-art MISOCP solver Gurobi on adapted instances from the literature.

Benders decomposition for congested partial set covering location with uncertain demand / Calamita, Alice; Ljubić, Ivana; Palagi, Laura. - (2024). [10.48550/arXiv.2401.12625]

Benders decomposition for congested partial set covering location with uncertain demand

Alice Calamita
;
Laura Palagi
2024

Abstract

In this paper, we introduce a mixed integer quadratic formulation for the congested variant of the partial set covering location problem, which involves determining a subset of facility locations to open and efficiently allocating customers to these facilities to minimize the combined costs of facility opening and congestion while ensuring target coverage. To enhance the resilience of the solution against demand fluctuations, we address the case under uncertain customer demand using Γ-robustness. We formulate the deterministic problem and its robust counterpart as mixed-integer quadratic problems. We investigate the effect of the protection level in adapted instances from the literature to provide critical insights into how sensitive the planning is to the protection level. Moreover, since the size of the robust counterpart grows with the number of customers, which could be significant in real-world contexts, we propose the use of Benders decomposition to effectively reduce the number of variables by projecting out of the master problem all the variables dependent on the number of customers. We illustrate how to incorporate our Benders approach within a mixed-integer second-order cone programming (MISOCP) solver, addressing explicitly all the ingredients that are instrumental for its success. We discuss single-tree and multi-tree approaches and introduce a perturbation technique to deal with the degeneracy of the Benders subproblem efficiently. Our tailored Benders approaches outperform the perspective reformulation solved using the state-of-the-art MISOCP solver Gurobi on adapted instances from the literature.
2024
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1700940
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact