Optimization Online


Relaxations and discretizations for the pooling problem

Akshay Gupte (agupte***at***clemson.edu)
Shabbir Ahmed (shabbir.ahmed***at***isye.gatech.edu)
Santanu S. Dey (santanu.dey***at***isye.gatech.edu)
Myun Seok Cheon (myuns***at***gmail.com)

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 unifying arguments and new insights on prevalent techniques. We also present new ideas for computing lower bounds on the global optimum by solving high-dimensional linear programs. Finally, we pro- pose discretization methods for inner approximating the feasible region and obtaining good upper 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 upper bounds on some of the large-scale instances.

Keywords: pooling problem, bilinear program, convexification, Lagrange relaxation, Discretization

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

Category 2: Global Optimization

Citation: Journal of Global Optimization, vol. 67, issue 3, pp. 631-669, 2017.

Download: [PDF]

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

Modify/Update this entry

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


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