This project was part of Asteroide's thesis, done in collaboration with his academic adviser, Prof. Santanu S. Dey, and Dr. Burak Kocuk.
The pooling problem is an classical problem in production planning which finds application in chemical process and petroleum industries. It's a hard-to-solve non-convex problem. The existence of multiple local optima solutions makes it very challenging to identify a global optimal solution. In practice, if one can find a solution that reduces the cost by just 1%, it can leads to millions of dollars in savings. The pooling problem is also a classical example of a bipartite bilinear program (BBP), for which Asteroide and Prof. Dey have already made significant contributions (click here for more details).
They have implemented strong convex relaxations by using discretization techniques and exploiting the structure of the underlying network. They have also identified new relaxations for BBPs using rank-one conditions on certain variable matrices. They have tested the new relaxations on 61 poling problem instances and showed that these relaxations outperform the previously best relaxations on average. In particular, they were able to reduced the average duality gap from 20.96% (previous approach) and 7.63% (commercial solver BARON) to 1.71% in 17 real-world instances from the mining industry. In addition, they obtained near-optimal feasible solutions for most of these instances by combining their results with mixed integer linear programming (MILP) discretization techniques.
All the details can be found in the paper.
As part of their contribution, 24 new and challenging generalized pooling problem (GPP) instances were generated and included in the computational experiments reported in the paper. These instances were generated in the same way Alfaki and Haugland had generated the instances C2 and D1 in their paper.
The new instances can be downloaded here.