  We investigate new convex relaxations for the pooling problem, a classic
nonconvex production planning problem in which input materials are mixed in
intermediate pools, with the outputs of these pools further mixed to make
output products meeting given attribute percentage requirements. Our
relaxations are derived by considering a set which arises from the formulation
by considering a single product, a single attibute, and a single pool. The
convex hull of the resulting nonconvex set is not polyhedral. We derive valid
linear and convex nonlinear inequalities for the convex hull, and demonstrate
that different subsets of these inequalities define the convex hull of the
nonconvex set in three cases determined by the parameters of the set.
Computational results on literature instances and newly created larger test
instances demonstrate that the inequalities can significantly strengthen the
convex relaxation of the pq-formulation of the pooling problem, which is the
relaxation known to have the strongest bound.
