Skip to main content

Seminar by Prof. Santanu Dey

Title:   Analysis of MILP techniques for the Pooling Problem
Speaker: Santanu Dey, Georgia Institute of Technology
Time:    3pm, 5/12/2013 (Thursday)
Venue:   LCC 11, Lecture Hall Complex

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.
About the speaker: Santanu Dey is an assistant professor at the Georgia Institute of Technology. His 
brief bio is available on his homepage http://www2.isye.gatech.edu/~sdey30/
News Category