Relaxations and discretizations for the pooling problem

被引：40

作者：

Gupte, Akshay ^{[1
]}

Ahmed, Shabbir ^{[2
]}

Dey, Santanu S. ^{[2
]}

Cheon, Myun Seok ^{[3
]}

机构：

[1] Clemson Univ, Dept Math Sci, Clemson, SC 29634 USA

[2] Georgia Inst Technol, Sch Ind & Syst Engn, Atlanta, GA 30332 USA

[3] ExxonMobil Res & Engn Co, Annandale, NJ USA

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2017年 / 67卷 / 03期

关键词：

Pooling problem; Bilinear program; Convexification; Lagrange relaxation; Discretization; CONSTRAINED QUADRATIC PROGRAMS; GLOBAL OPTIMIZATION; MIXED-INTEGER; PROCESS NETWORKS; MULTILINEAR FUNCTIONS; BILINEAR PROGRAMS; NONCONVEX; FORMULATIONS; ALGORITHM; EMISSIONS;

D O I：

10.1007/s10898-016-0434-4

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：631 / 669

页数：39

共 70 条

[21]

Burer S, 2012, IMA VOL MATH APPL, V154, P373

[22] CONCAVE EXTENSIONS FOR NONLINEAR 0-1 MAXIMIZATION PROBLEMS [J].