-

 

 

 




Optimization Online





 

Analysis of MILP Techniques for the Pooling Problem

Santanu S. Dey (santanu.dey***at***isye.gatech.edu)
Akshay Gupte (agupte***at***clemson.edu)

Abstract: The $pq$-relaxation for the pooling problem can be constructed by applying McCormick envelopes for each of the bilinear terms appearing in the so-called $pq$-formulation of the pooling problem. This relaxation can be strengthened by using piecewise-linear functions that over- and under-estimate each bilinear term. The resulting relaxation can be written as a mixed integer linear programming (MILP) model. While there is significant amount of empirical evidence to show that such piecewise-linear relaxations yield `good' bounds for pooling problems, 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 piecewise-linear relaxations (without loss of generality we assume that the pooling problem has a `maximizing' objective function) 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 $\epsilon > 0$, and for any piecewise-linear relaxation of pooling problems, there exists an instance of the pooling problem where the ratio of the optimal objective function value of the relaxation to that of the pooling problem is at least $n - \epsilon$. This analysis naturally yields a polynomial-time $n$-approximation algorithm for the pooling problem. We also show that if there exists a polynomial-time approximation algorithm with guarantee better than $n ^{1 - \epsilon}$ (for any $\epsilon >0$) for the pooling problem, then NP-hard problems have randomized polynomial time algorithms. Finally, motivated by the approximation algorithm, we design a heuristic for solving pooling problems which involves solving a MILP based restriction of the pooling problem. This heuristic is guaranteed to provide solutions within a factor of $n$. On large-scale test instances, this heuristic performs surprisingly well in comparison to commercial global optimization solvers. In significantly lesser time, the heuristic provides solutions that are often orders of magnitude better than those given by commercial solvers.

Keywords: Pooling Problem, Bilinear Programming, Approximation Algorithm, Mixed Integer Programming, Piecewise Linear, Relaxations and Restrictions

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Global Optimization

Category 3: Combinatorial Optimization (Approximation Algorithms )

Citation: Operations Research, vol. 63, issue 2, pp. 412- 427, 2015.

Download: [PDF]

Entry Submitted: 04/28/2013
Entry Accepted: 04/28/2013
Entry Last Modified: 10/27/2017

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society