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