Analyzing the pooling problem

The pooling problem is a non-convex mathematical program that arises in blending materials to produce products, such as the blending of crude or refined petroleum. Each material has a set of attributes with associated qualities, such as percentage sulfur and octane rating. Pool qualities are determined by a flow-weighted average of the source qualities, and product qualities are similarly defined by a flow-weighted average of pool qualities. Product qualities are constrained to lie in specified ranges. The pooling problem is to minimize the total cost of flows, subject to flow and quality constraints. Present solution methods are based on sequential linear programming, and sensitivity analysis relies upon Lagrange multipliers. These methods are not exact and can lead to erroneous conclusions. A new method is presented that is based upon computational geometry, which provides exact answers to questions of sensitivity analysis and infeasibility diagnosis.