One Relaxation to Rule Them All: Strong Convex Nonlinear Relaxations of the Pooling Problem

Our quest is to derive convex relaxations for the pooling problem, a nonconvex production planning problem in which products are mixed in intermediate pools in order to meet quality targets at their destinations. The story begins with a description of the problem and discussion of state-of-the-art solution approaches. In the second chapter, we derive a tractable, non-convex relaxation to form the basis of our continuing adventure. We characterize the extreme points of the convex hull of our non-convex set, and we derive valid nonlinear convex inequalities. Computational results demonstrate that the inequalities can significantly strengthen the convex relaxations of even the most sophisticated formulations of the pooling problem.

Joint work with Claudia D’Ambrosio (Ecole Polytechnique), Jim Luedtke, (UW Madison), and Jonas Schweiger (IBM/CPLEX)