Relaxations and discretizations for the pooling problem
Relaxations and discretizations for the pooling problem
复制标题
池化问题的松弛和离散化
作者：
A. Gupte;Shabbir Ahmed;Santanu S. Dey;Myun
汇总问题是一个民俗NP-HARD全球优化问题，它在石化炼油，废水处理和采矿等行业中找到了应用。本文吸收了有关该问题的大量文献，该文献分散在不同领域，并就普遍的技术提供了新的见解。我们还提出了通过求解高维线性程序来计算全球最佳限制双重界限的新想法。最后，我们提出了内部近似可行区域并获得良好原始边界的离散方法。有效的不等式是针对离散模型的，该模型被称为混合整数线性程序。在随机测试实例上，我们的放松和有用性的强度得到了证实。我们报告了一些大规模实例的最著名的原始界限。
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.