 |
Center for Nonlinear Studies |
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, we derive valid nonlinear convex inequalities, and we demonstrate that we have characeterized the convex hull of our relaxation. Computational results demonstrate that the inequalities can significantly strengthen the convex relaxations of even the most sophisticated formulations of the pooling problem.
Host: Harsha Nagarajan