A Semidenite Programming Relaxation Approach for the Pooling Problem
A Semidenite Programming Relaxation Approach for the Pooling Problem
复制标题
池化问题的半定规划松弛方法
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
T. Nishi
中科院分区：
文献类型：
--
作者：
T. Nishi
池化问题是确定原油和燃气等原材料炼油过程中多个储罐之间的流量调度。炼油公司首先进口原材料，然后通过在中间罐中精炼或混合材料来生产最终产品，最后将其发送给消费者。消费者要求最终产品达到一定的质量水平。池化问题被视为网络流问题的一种。然而，与通常的线性网络流问题相比，它有两个困难。一是存在管道约束，它是通过使用二进制变量来表示的。另一个是将材料的混合过程表述为非线性方程。因此，池化问题是一个混合整数非线性规划。而且，即使二元变量是固定的，问题也是非凸的，因此仍然非常困难。因此，我们不能将通用求解器应用于混合整数线性规划或混合整数非线性规划。在本文中，我们将半定规划（SDP）松弛应用于相当于池化问题的多项式优化问题（POP）。已知将SDP放宽到POP的解决方案是合理的解决方案。然而，SDP的规模往往非常大，其解决方案对于原始POP不一定可行。因此，我们首先提出了一种没有二元变量的池化问题的公式，以减少问题的规模。然后，为了加强放松，我们考虑添加一些有效的不等式。有效不等式是原问题的冗余约束。然而，它可能会减少SDP的可行区域的体积，因此我们可以期望得到更好的解决方案。最后，为了得到原始池化问题的可行解，我们制定了一个解可行的混合整数线性问题。由于所表述的问题包括SDP松弛的解的信息，因此其解预计是合理可行的解。我们提出了一些数值实验的结果来证明所提出方法的有效性。
The pooling problem is to determine a scheduling of flows among several tanks in refinery processes of raw materials, such as crude oil and fuel gas. The refinery company first imports raw materials, and then produces final products by refining or mixing the materials in intermediate tanks, and finally send them to their consumers. The consumers require a certain level of quality of the final product. The pooling problem is regarded as a kind of the network flow problem. However, it has two difficulties as compared to the usual linear network flow problem. One is an existence of pipeline constraints, which is formulated by using binary variables. The other is that the process of mixing materials are formulated as nonlinear equations. Thus, the pooling problem is a mixed-integer nonlinear programming. Moreover, even if the binary variables are fixed, the problem is nonconvex, and hence still very difficult. Therefore, we cannot apply the general-purpose solvers for the mixed-integer linear programming or the mixed-integer nonlinear programming. In this paper, we apply semidefinite programming (SDP) relaxations for the polynomial optimization problem (POP) equivalent to the pooling problem. A solution of the SDP relaxation to the POP is known to be a reasonable solution. However, the size of the SDP tends to be very large and its solution is not necessarily feasible for the original POP. Therefore, we first propose a formulation of the pooling problem without the binary variables in order to reduce the problem size. Then, to tighten the relaxation, we consider to add some valid inequalities. The valid inequality is a redundant constraint of the original problem. However, it may reduce the volume of the feasible region of the SDP, and hence we can expect to get a better solution. Finally, in order to get a feasible solution of the original pooling problem, we formulate a mixed-integer linear problem whose solution is feasible. Since the formulated problem includes information of the solution of the SDP relaxation, its solution is expected to be a reasonable feasible solution. We present some results of numerical experiments to show the validity of the proposed approach.