  In this paper we generalize to the case of diluted spin models and random
combinatorial optimization problems a technique recently introduced by Guerra
(cond-mat/0205123) to prove that the replica method generates variational
bounds for disordered systems. We analyze a family of models that includes the
Viana-Bray model, the diluted p-spin model or random XOR-SAT problem, and the
random K-SAT problem, showing that the replica method provides an improvable
scheme to obtain lower bounds of the free-energy at all temperatures and of the
ground state energy. In the case of K-SAT the replica method thus gives upper
bounds of the satisfiability threshold.
