Pooling and blending problems occur frequently in the petrochemical industr
y where crude oils, procured from various sources, are mixed together to ma
nufacture several end-products. Finding optimal solutions to pooling proble
ms requires the solution of nonlinear optimization problems with multiple l
ocal minima. We introduce a new Lagrangian relaxation approach for developi
ng lower bounds for the pooling problem. We prove that, for the multiple-qu
ality case, the Lagrangian approach provides tighter lower bounds than the
standard linear-programming relaxations used in global optimization algorit
hms. We present computational results on a set of 13 problems which include
s four particularly difficult problems we constructed.