Weak Flow Cover Inequalities for the Capacitated Facility Location Problem

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.