Skip to content Skip to main navigation Report an accessibility issue

Analysis of MILP Techniques for the Pooling Problem


Santanu S. Dey, Ph.D.
Industrial and Systems Engineering
Georgia Institute of Technology
October 10th, 2014, 2:30 – 3:30 PM
410 John D. Tickle Engineering Building

Dr. Santanu S. Dey is currently a Fouts Family Associate Professor in the Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology. Dr. Dey holds a Ph.D. in Industrial Engineering from Purdue University. Prior to joining Georgia Tech, he worked as a post-doctoral fellow at the Center for Operations Research and Econometrics (CORE) of the Catholic University of Louvain in Belgium. His research interest is in the area of optimization, specifically mixed integer linear and non-linear programming. Dr. Dey has been the winner of the INFORMS George Nicholson Student Paper Competition, and has received the IBM Faculty award and the NSF CAREER award.

Talk Abstract: The pooling problem is a challenging non-convex optimization problem that is motivated by refinery processes in the petroleum industry, and also finds application in other areas such as waste water treatment, emissions regulation and agricultural industry among others. In this talk, we will present an analysis of mixed integer linear programming (MILP) based techniques to solve the pooling problem. In particular, the talk will focus on three results: (1) We will analyze the quality of dual bounds produced by solving MILP based relaxations of the pooling problem. These MILP relaxations are derived using piecewise-linear approximations for bilinear terms appearing in the model for the pooling problem. (2) We will present an approximation algorithm for the pooling problem and show that unless NP-hard problems have randomized polynomial time algorithms, this algorithm obtains the best possible approximation ratio. (3) Motivated by the approximation algorithm we will present a MILP based heuristic for the pooling problem. This heuristic is guaranteed to provide solutions within a factor of n, where n is the number of output nodes. On medium and large-scale test instances, this MILP based heuristic performs surprisingly well. In particular, it finds the best known solutions for many instances reported in the literature. This is joint work with Akshay Gupte.