The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

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

Jeff Linderoth, Professor, Department of Industrial and Systems Engineering, Department of Computer Sciences, UW-Madison

Date and Time: Jan 27, 2016 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building


Video Recording:

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)