The Capacitated Facility Location Problem calls for opening a set of facilities with capacity constraints, with the aim of satisfying at the minimum cost the demands of a set of customers. We present a new class of valid inequalities, the Weak Flow Cover inequalities. We show that Weak Flow Cover inequalities can be separated in polynomial time and turned into violated Flow Cover inequalities. In this way, we are able to provide a polynomial separation heuristic for the latter. Embedding the separation procedure into a cut-and-branch approach, we get results significantly better than those reported in the recent literature both for the lower and the upper bounds.

Weak flow cover inequalities for the capacitated facility location problem

Avella P.;Boccia M.;Mattia S.;Rossi F.
2021

Abstract

The Capacitated Facility Location Problem calls for opening a set of facilities with capacity constraints, with the aim of satisfying at the minimum cost the demands of a set of customers. We present a new class of valid inequalities, the Weak Flow Cover inequalities. We show that Weak Flow Cover inequalities can be separated in polynomial time and turned into violated Flow Cover inequalities. In this way, we are able to provide a polynomial separation heuristic for the latter. Embedding the separation procedure into a cut-and-branch approach, we get results significantly better than those reported in the recent literature both for the lower and the upper bounds.
Cut-and-branch
Facility location
Flow cover
Separation
Valid inequalities
File in 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/20.500.12070/46101
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 3
social impact