Abstract
The pqrelaxation for the pooling problem can be constructed by applying McCormick envelopes for each of the bilinear terms appearing in the socalled pqformulation of the pooling problem. This relaxation can be strengthened by using piecewiselinear functions that over and underestimate each bilinear term. Although there is a significant amount of empirical evidence to show that such piecewiselinear relaxations, which can be written as mixedinteger linear programs (MILPs), yield good bounds for the pooling problem, to the best of our knowledge, no formal result regarding the quality of these relaxations is known. In this paper, we prove that the ratio of the upper bound obtained by solving piecewiselinear relaxations (objective function is maximization) to the optimal objective function value of the pooling problem is at most n, where n is the number of output nodes. Furthermore for any ϵ > 0 and for any piecewiselinear relaxation, there exists an instance where the ratio of the relaxation value to the optimal value is at least n − ϵ. This analysis naturally yields a polynomialtime napproximation algorithm for the pooling problem. We also show that if there exists a polynomialtime approximation algorithm for the pooling problem with guarantee better than n1−ϵ for any ϵ > 0, then NPcomplete problems have randomized polynomialtime algorithms. Finally, motivated by the approximation algorithm, we design a heuristic that involves solving an MILPbased restriction of the pooling problem. This heuristic is guaranteed to provide solutions within a factor of n. On largescale test instances and in significantly lesser time, this heuristic provides solutions that are often orders of magnitude better than those given by commercial local and global optimization solvers.
Original language  English 

Pages (fromto)  412427 
Number of pages  16 
Journal  Operations Research 
Volume  63 
Issue number  2 
Early online date  4 Mar 2015 
DOIs  
Publication status  Published  30 Apr 2015 
Fingerprint
Dive into the research topics of 'Analysis of MILP Techniques for the Pooling Problem'. Together they form a unique fingerprint.Profiles

Akshay Gupte
 School of Mathematics  Lecturer in Operational Research
Person: Academic: Research Active (Teaching)