Analysis of MILP techniques for the Pooling Problem

Santanu S. Dey

Date and Time: 

Wednesday, November 13, 2013 - 4:00pm

Event Location: 

Mohler Lab #453

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.

Bio Sketch: 

Santanu S. Dey is currently a Fouts Family Assistant 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.