  The metric capacitated facility location is a well-studied problem for which,
while constant factor approximations are known, no efficient relaxation with
constant integrality gap is known. The question whether there is such a
relaxation is among the most important open problems of approximation
algorithms \cite{ShmoysWbook}.
  In this paper we show that, if one is restricted to linear programs that use
the natural encoding for facility location, at least an exponential number of
constraints is needed to achieve a constant gap. Our proof does not assume any
special property of the relaxation such as locality or symmetry.
