Pooling and blending problems occur frequently in the petrochemical industry where crude oils, procured from various sources, are mixed together to manufacture several end-products. Finding optimal solutions to pooling problems requires the solution of nonlinear optimization problems with multiple local minima. We introduce a new Lagrangian relaxation approach for developing lower bounds for the pooling problem. We prove that, for the multiple-quality case, the Lagrangian approach provides tighter lower bounds than the standard linear-programming relaxations used in global optimization algorithms. We present computational results on a set of 13 problems which includes four particularly difficult problems we constructed.