A Lagrangian approach to the pooling problem

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.