Relaxations and discretizations for the pooling problem

Akshay Gupte (), Shabbir Ahmed, Santanu S. Dey and Myun Seok Cheon
Additional contact information
Akshay Gupte: Clemson University
Shabbir Ahmed: Georgia Institute of Technology
Santanu S. Dey: Georgia Institute of Technology
Myun Seok Cheon: ExxonMobil Research and Engineering Company

Journal of Global Optimization, 2017, vol. 67, issue 3, No 9, 669 pages

Abstract: Abstract The pooling problem is a folklore NP-hard global optimization problem that finds applications in industries such as petrochemical refining, wastewater treatment and mining. This paper assimilates the vast literature on this problem that is dispersed over different areas and gives new insights on prevalent techniques. We also present new ideas for computing dual bounds on the global optimum by solving high-dimensional linear programs. Finally, we propose discretization methods for inner approximating the feasible region and obtaining good primal bounds. Valid inequalities are derived for the discretized models, which are formulated as mixed integer linear programs. The strength of our relaxations and usefulness of our discretizations is empirically validated on random test instances. We report best known primal bounds on some of the large-scale instances.

Keywords: Pooling problem; Bilinear program; Convexification; Lagrange relaxation; Discretization (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-016-0434-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:67:y:2017:i:3:d:10.1007_s10898-016-0434-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-016-0434-4

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().