Pooling Problem: Alternate Formulations and Solution Methods
Pooling Problem: Alternate Formulations and Solution Methods
复制标题
DOI：
10.1287/mnsc.1030.0207
复制
发表时间：
2000-05
期刊：
影响因子：
--
通讯作者：
Charles Audet;J. Brimberg;P. Hansen;Sébastien Le Digabel;N. Mladenović
中科院分区：
文献类型：
--
作者：
Charles Audet;J. Brimberg;P. Hansen;Sébastien Le Digabel;N. Mladenović
对石油行业至关重要的集合问题描述了一种情况，在一系列池中，具有不同属性质量的产品混合在一起，以使得终端池混合产品的属性质量必须满足，并且给定要求。众所周知，可以通过双线性和非凸二次编程来建模合并问题。在本文中，我们研究了如何最好地应用新的分支和切割二次编程算法来解决汇总问题。为此，我们考虑了两个标准模型：一个主要基于流量变量，而另一个依赖于进入池的流量的比例。提出了这两个模型的混合体，以解决一般的集合问题。对流量和比例模型的计算特性的比较是在文献中获得的几个问题实例中进行的。此外，开发了一个简单的交替过程和可变的邻里搜索启发式方法来解决大型实例，并与众所周知的连续线性编程方法进行了比较。从文献中解决困难的测试问题的解决方案基本上是加速的，并且较大的解决方案被精确或大致解决。
The pooling problem, which is fundamental to the petroleum industry, describes a situation in which products possessing different attribute qualities are mixed in a series of pools in such a way that the attribute qualities of the blended products of the end pools must satisfy given requirements. It is well known that the pooling problem can be modeled through bilinear and nonconvex quadratic programming. In this paper, we investigate how best to apply a new branch-and-cut quadratic programming algorithm to solve the pooling problem. To this effect, we consider two standard models: One is based primarily on flow variables, and the other relies on the proportion of flows entering pools. A hybrid of these two models is proposed for general pooling problems. Comparison of the computational properties of flow and proportion models is made on several problem instances taken from the literature. Moreover, a simple alternating procedure and a variable neighborhood search heuristic are developed to solve large instances and compared with the well-known method of successive linear programming. Solution of difficult test problems from the literature is substantially accelerated, and larger ones are solved exactly or approximately.